- Introduction to the Theory of Computation
- 4 Sisällys
- Johdanto
- 5
- formaalin Kieliteorian perusteet
- 2.1 joidenkin matematiikan perustietojen tarkastelu ja
- n,Z,Q,R,C.
- {
- }
- 7
- 8 luku 2. Formaalin KIELITEORIAN perusteet
- 10 Luku 2. PERUSASIAT VIRALLISEN KIELEN TEORIA
- +=
- ⋃
- R∗=
- ⋃
- 2.2. Aakkoset, merkkijonot, kielet 11
- 2.2. Aakkoset, kielet, kielet 13
-
-
-
- 14 luku 2. Formaalin KIELITEORIAN perusteet
- 16 luku 2. Formaalin KIELITEORIAN perusteet
- 2.2. Aakkoset, kielet, kielet 17
- 2.3. Kieliin liittyvät operaatiot 19
- 20 luku 2. PERUSASIAT VIRALLISEN KIELEN TEORIA
Introduction to the Theory of Computation
Jean GallierDepartment of Computer and Information ScienceUniversity of PennsylvaniaPhiladelphia, PA 19104, USAe-mail:[email protected]
©C Jean GallierPlease, älä julkaise ilman tekijän lupaa
maaliskuu 5, 2020
4 Sisällys
- 6.4 pumppaava Lemma
- 6.5 nopea algoritmi tilan vastaavuuden tarkistamiseksi
- 7 asiayhteydestä vapaat kieliopit ja Kielet
- 7.1 Kontekstivapaat kieliopit
- 7.2 johdokset ja Kontekstivapaat kielet
- 7.3 Normaalimuodot Kontekstivapaille kielille
- 7.4 säännölliset kielet ovat Kontekstivapaita
- 7.5 hyödyttömät tuotokset Kontekstivapaissa Kielioppilaitoksissa
- 7.6 Greibachin normaalimuoto
- 7.8 Kontekstittomat kielet vähiten kiinteitä pisteitä
- 7.9 vähiten kiinteitä pisteitä ja Greibachin normaalimuoto
- 7.10 puutaloja ja Gorn-puita
- 7.11 Derivointipuita
- 7.12 Ogdenin Lemma
- 7.13 Pushdown Automata
- 7.14 Kontekstivapaista Kielioireista PDA: n
- 7.15 PDA: n Kontekstivapaista Kielioireista
- 7.16 Chomsky-Schutzenbergerin lause
- 8 A Survey of LR-Jäsennysmenetelmät
- 8.1 LR(0)-ominaisuus Automata
- 8, 2 Shift/reduce parsers
- 8, 3 ensimmäisen laskenta
- 8, 4 intuitio Shift/reduce algoritmin takana
- 8, 5 kiinteiden pisteiden laskentamenetelmä
- 8, 6 seuraavan laskenta
- 8, 7 algorithmtraverse
- 8.8 More onLR(0)-Characteristic Automata
- 8.9 LALR (1)-Lookahead Set
- 8.10 Computing FIRST, FOLLOW, etc. ǫ-sääntöjen läsnä ollessa
- 8.11 Lr(1)-ominainen Automata
7.7 vähiten kiinteitä pisteitä
Johdanto
laskennan teoria koskee algoritmeja ja algoritmisia järjestelmiä: niiden suunnittelua ja esittämistä, niiden täydellisyyttä ja monimutkaisuutta.
näiden huomautusten tarkoituksena on ottaa käyttöön joitakin teorian perusajatuksia, mukaan lukien käsitteet muodollisista kielistä ja automata-teoriasta, theory ofcomputability, joitakin perusasioita rekursiivisesta funktioteoriasta ja johdatus kompleksisuusteoriaan. Muita aiheita, kuten ohjelmien oikeellisuutta, ei käsitellä täällä (siellä ei ole tarpeeksi aikaa!).
nuotit on jaettu kolmeen osaan. Ensimmäinen osa on omistettu virallisille kielille ja automaateille. Toinen osa käsittelee malleja laskenta, rekursiiviset toiminnot, andundecidability. Kolmas osa käsittelee laskennallinen monimutkaisuus, inericular classesPandNP.
5
formaalin Kieliteorian perusteet
2.1 joidenkin matematiikan perustietojen tarkastelu ja
n,Z,Q,R,C.
Luonnonluvut, N={ 0 , 1 , 2 ,…}.
Theintegers, Z = {…,− 2 ,− 1 , 0 , 1 , 2 ,…}.
Therationals,
Q=
{
pq
/ p,q∈Z, q 6 = 0
}
null
Therals, R. Thecomplex numbers, C={A+ib / a,b∈r}.
millä tahansa setxillä, thepower setofXis kaikkien osajoukkojen Xand merkitään 2x. notaatio f: X→Y
merkitsee afunctionwithdomainXandrange (orcodomain)Y.
graph (F) ={(x,f(x)}|X∈X}⊆X×Y
on graphoff.
7
8 luku 2. Formaalin KIELITEORIAN perusteet
Im(F) =f(X) ={Y∈Y |∃x∈X, y=f(x)}⊆y
on theimageoff.
yleisemmin ifA⊆X, niin
f(A) ={Y∈Y |∃x∈A, y=f(x)}⊆y
on (suora) imageofA.
IfB⊆Y, niin f-1(B) ={x∈X|f(x)∈B}⊆X
on B: n käänteiskuva (orpullback).
f-1 (B) on joukko; se saattaa olla tyhjä, vaikka b 6 =¿.Kun otetaan huomioon kaksi funktiota F: X→Y jag: Y→Z, funktio GPC F: X→Zgiven by
(g GB f) (x) =g(f (x)) allx∈x
on kompositionoff jag.
funktio idX: X→Xgiven by
idX(x) =x allx∈x
on theidentity-funktio (ofX).
funktio f: X→Y isinjektiivinen (vanha terminologia-to-one), jos allx 1, x 2 ∈X,
iff (x 1) =f (x 2), thenx 1 =x 2 ;
vastaavasti ifx 16 =x 2, thenf (x 1) 6 =f(x 2).
fakta: IfX 6 = ø (ja soija 6 = Ø), funktio f: X →Y on injektiivinen iff on funktio R: Y →X (aleft inversio) sellainen, että
r GB f = idX.
Huom.Funktio f:X→Y issurjektiivinen(vanha terminologia)jos liittymälle∈Y on olemassa jokin X∈Xsuch thaty=f(x), ifff(X) =Y.
fakta: IfX 6 =¿(ja soija 6 = ¿), funktio f:X→Y on surjektiivinen iff on funktio:Y →X(aright inversiorsection) sellainen, että
f idy.
10 Luku 2. PERUSASIAT VIRALLISEN KIELEN TEORIA
A relationR⊆X×Xissymmetricif varten allx,y∈X, jos (x,y)∈R, niin (y,x)∈R
A relationR⊆X×Xis symmetrinen iffR− 1 ⊆R.
GivenR⊆X×X(suhteessa onX), defineRnby
R 0 =IXRn+1=R◦Rn.
Transaktiivinen klosureeri+ofRis, annettu
+=
⋃
n≥ 1
Rn.
fakta.R+on pienin transitiivinen relaatio, joka sisältää r: n.
Thereflexive ja transitiivinen closureR∗ofRis antama
R∗=
⋃
n≥ 0
Rn=R + ∪IX.
fakta.R∗on pienin transitiivinen ja refleksiivinen relaatio, joka sisältää r: n.
relaatio⊆X×X on ekvivalenssirelaatio, jos se on refleksiivinen, symmetrinen ja transitiivinen.
fakta. Pienin ekvivalenssirelaatio, joka sisältää relaation⊆X×Xis, jonka antaa
(R∪R− 1 )∗.
a relationR⊆X×Xisantisymmetricif for allx, y∈X, if (x,y)∈Rand (y,x)∈R,thenx=y.
a relationR⊆X×Xisymmetric if it is reflexive, transitiivinen, and antisymmetric.
osittainen järjestys ⊆X×X on kokonaisjärjestys, jos allx,y ∈X, joko (x,y)∈ Ror(y,x)∈R.
2.2 aakkoset, Jouset, kielet
meidän käsityksemme kielistä on, että kieli on joukko merkkijonoja. Merkkijono on puolestaan joidenkin aakkosten kirjainten äärellinen muoto. Nämä käsitteet on määritelty tiukasti seuraavasti.
määritelmä 2.1.AnalphabetΣ on anyfiniteset.
2.2. Aakkoset, merkkijonot, kielet 11
kirjoitamme usein Σ ={A 1,…ak. Niitä kutsutaan aakkosten syiksi.Esimerkiksi:Σ = {A}Σ = {a,b,c}Σ ={0 , 1 }Σ = {α,β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,π,ζ}merkkijono on äärellinen symbolien jono. Teknisesti, se on kätevä määritellä merkkijonojatoimintoja. Kaikkien kokonaislukujen≥1, olkoon
={ 1 , 2 ,…, n},
ja forn = 0, let = ¿.
määritelmä 2.2. Koska aakkoset Σ, astring overΣ (tai yksinkertaisesti merkkijono) pituus nisany funktio
u: →Σ.
kokonaisluku on stringun pituinen, ja sitä merkitään|u/. Whenn= 0, thespecial stringu: →Σ pituuden 0 kutsutaan theempty merkkijono, tai null merkkijono, ja on denotedasǫ.
koska stringu: → Σ pituuden n≥1, u (i) on stringun TH kirjain. Sim-plicity of notation, we writeuinstead of ofu (i), and we container the stringu=u(1) u(2)···u(n) as
u=u 1 u 2 ···un,
with eachui Σ Σ.
esimerkiksi, jos Σ ={A, B}andu: → Σ määritellään siten, että U(1) =A,u(2) =b, andu (3) =a, kirjoitetaan EU=aba.
muita esimerkkejä merkkijonoista ovat
work, fun, gabuzomeuh
merkkijonot, joiden pituus on 1, ovat funktioita: →Σ yksinkertaisesti poimitaan jokin elementti (1) =aiin Σ.Siten tunnistamme jokaisen symbolin∈Σ vastaavalla merkkijonolla Pituus 1.
kaikkien merkkijonojen joukko kirjaimella Σ, mukaan lukien tyhjä merkkijono,merkitään Σ∗.
2.2. Aakkoset, kielet, kielet 13
kantakasenilla = 0, sinceu 0 = ǫ, meillä on
u 0 u=ǫu=u=uǫ = uu 0.
induktiovaiheessa meillä on
un + 1U = (unu)u määritelmän ofun+ =(uun)u induktiohypoteesin =u (unu) mukaan assosiatiivisuus = uun+1 määritelmän ofun+1.
määritelmä 2.4.Koska kirjaimisto Σ, koska tahansa kaksi stringsu, V∈Σ∗määrittelemme seuraavat not seuraavasti:
uis etuliite ofviff on some Σ Σ∗siten, että
v=uy.
uis ofviff on some x Σ Σ∗sellainen, että
v=xu.
uis substraatti ofviff on some X, y Σ Σ∗sellainen, että
v=xuy.
sanomme, että viffuis on oikea etuliite (pääte, substraatti) ofvandu 6 =v.
esimerkiksi gais a etuliite ofgabuzo,zois a suffix ofgabuzoandbuzis a substring ofgabuzo.Muistuttaa, että osittainen tilaus≤ on asetettu on binary suhde≤⊆ S×S, joka onreflexive, transitiivinen, ja antisymmetrinen.
etuliitteen, suffiksin ja substraatin käsitteet määrittelevät Binäärisuhteet Σ∗: llä obviouswaylla. Voidaan osoittaa, että nämä suhteet ovat osittaisia järjestyksiä.
toinen tärkeä käsky merkkijonoilla on lexicographic (tai dictionary) – käsky.
määritelmä 2.5. Koska aakkoset Σ ={A 1,…, ak}oletettu täysin tilattu sellainen thata 1 < a 2 <···< ak, koska mikä tahansa kaksi stringsu, V∈Σ∗, määrittelemme thelexicographic orderingas seuraavasti:
uv
(1) ifv=uy, jos some∈Σ∗, tai (2) ifu=xaiy,v=xajz,ai< aj,withai,aj Σ Σ, ja somex,y,z Σ Σ∗.
14 luku 2. Formaalin KIELITEORIAN perusteet
ajatuksena on, että skannaamme ja vertaamme samansuuntaisesti vasemmalta oikealle, vertaamalla themthsymboluminuto themth symbolvminv, alkaen M= 1. If no confliction arises, thatis, if them-TH symboluminuagreeswith them-TH symbolvminvform= 1,…, / u|, thenuis etuliite ofvand me julistamme, että uprecedesvin lexicographic Order. Muuten, jonkin aikaa euandvagree pitkin yhteistä prefixx(mahdollisesti tyhjä merkkijono), ja sitten on aleftmost ristiriita, mikä tarkoittaa, että se on formu=xaiyandvis,formv=xajz,withai 6 =aj (andx, y, z Σ Σ∗mielivaltainen). Sitten meidän on katkaistava tie, ja tehdäksemme tämän käytämme sitä, että symboli 1 < a 2 <···< ak oletetaan (täysin)järjestetyksi, joten näemme kumpi ofaiandajcomes ensimmäinen, sayai< aj, ja julistamme, ettäu=xaiyprecedesv=xajzin lexicographic järjestyksessä.
huomaa, että tapaukset (1) ja (2) sulkevat toisensa pois. Tapauksessa (1) U on OFV-etuliite. Tapauksessa (2) v6uandu 6 =v.
esimerkiksi abb, gallhagergallier.
on melko työlästä todistaa, että leksikografinen tilaus on itse asiassa apartiaalinen tilaus.Itse asiassa se on atotal järjestyksessä, mikä tarkoittaa,että minkä tahansa kahden stringsu, V Σ Σ∗, eitheruv, orvu.
Stringw määritellään induktiivisesti seuraavasti:
ǫR = ǫ, (ua)R=auR,
missä Σ Σ Ja Σ Σ∗.
esimerkiksi reillag=gallierR.
By settingu=ǫin (ua)R=auR,
sinceǫR=ǫanda=ǫa, saamme
aR= (ǫa)R=aǫR=aǫ=a,
namelyaR=sillä alla∈Σ.
induktiolla|v|voidaan osoittaa, että
(uv)R=vRuR.
hyödyllinen temppu, joka vähentää hankalaa merkintää, kun tehdään induktiota stringillä, on havainto, että anonempty stringw∈Σ∗pituudesta+ 1 (N≥0) voidaan kirjoittaa
w=ua, jollekin∈Σ∗ja jollekin symbolille Σ Σ, jossa|u|=n.
16 luku 2. Formaalin KIELITEORIAN perusteet
jos ei tyhjä joukko, koska: X→Nis injektio iff on surjektior:n→Xsuch thatr ◦ng f= idX, setXis numeroituva iff on asurjektio nontoxista.
fakta. Voidaan osoittaa, että setXis on numeroituva, jos se on joko äärellinen tai jos se on bijectionwithn(jolloin se on ääretön).
näemme myöhemmin, että n×Nis lasketaan. Tämän seurauksena rationaalilukujen setqon laskettavissa.
joukko on laskettavissa, jos sitä ei voida laskea.
esimerkiksi R (reaalilukujen joukko) on laskematon.Samoin
(0,1) ={x∈R / 0 < x < 1 }
ei voi laskea. On kuitenkin bijection välillä (0,1) andR(etsi yksi!) Asettaa 2Nof kaikki subsets ofNis uncountable. Tämä on Cantorin lauseen erikoistapaus alla.
oletetaan / Σ / =Kwith Σ ={A 1,…ak. Ensinnäkin on huomioitava, että on olemassa pituusnand(kn+1-1)/(k−1) – merkkijonoja, joiden pituus on mostnover Σ; whenk= 1, toinen kaava olisi korvattava byn+ 1. Todellakin, koska merkkijono on funktio: {1,…, n} →Σ, thenumber of strings of lengthnis the number of functions from{ 1,…, n}Σ, Ja koska Σ isk: n kardinaalisuus, on olemassa knsuch-funktioita (tämä osoitetaan välittömästi induktiolla onn). Sitten merkkijonojen lukumäärä pituus mostnis
1 + k+k 2 +···+kn.
jos k = 1, tämä luku on n+ 1, ja jos k ≥ 2, geometrisen sarjan summana, se on(kn+1-1)/(k−1).
jos Σ 6 = λ, niin kaikkien merkkijonojen Σ∗on ääretön ja numeroituva, kuten nyt osoitamme rakentamalla eksplisiittisen Bijektion Σ∗ontonista.
Ifk= 1 writea=a 1, ja sitten
{a}∗={ǫ, a, aa, aa,…,jonkin,…}.
meillä on bijektionn7→anfromNto{a}∗.Ifk≥2, niin voimme ajatella merkkijonon
u = ai 1 ···ain
esittävän kokonaislukua(u) basekshiftattuna (kn−1)/(k−1), jossa
2.2. Aakkoset, kielet, kielet 17
ν (u) = i 1 kn− 1 + i 2 kn− 2 +···+in – 1 k+in
=
kn – 1 k− 1
- (1-1) kn− 1 +···+ (in-1-1) k+in− 1.
(ja withv (ǫ) = 0), jossa 1≤ij≤kforj= 1,…,
jätämme sen harjoitukseksi osoittaaksemme, Ettäv: Σ∗→Nis on bijektio. Findingyksinkertaisesti (thatis, kaava) käänteiselle ofvis yllättävän vaikeaa.
itse asiassa ν vastaa Σ∗: n suuruusluokkaa, jossa uprecedesv if|u|< |v|, ja vastaavasti lexicographic order if|u|=|v|. On helppo tarkistaa, että aboverelation (upreedesv) on yhteensä järjestyksessä.
esimerkiksi ifk= 2 ja jos kirjoitetaan Σ = {A,B}, niin arvojoukko alkaa kirjaimella
ǫ,0a, b,1 , 2 ,aa, ab, ba,bb , 3 , 4 , 5 ,6, aaa, aab, aba, abb, abb, baa, bab, bba, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14
saat seuraavan rivin, concatenateaon vasemmalla, ja sitten concatenatebon vasemmalla. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.
se toimii!
sitä vastoin, jos Σ 6 = ¿, Σ∗: n kaikkien osajoukkojen(kaikki kielet) joukko 2σ∗on laskettavissa.Todellakin, voimme osoittaa, että ei ole surjection fromNonto 2σ ∗ ensimmäinen, me osoittaa, että that there is no surjection From Σ∗onto 2σ∗. Tämä on Cantorin lauseen erikoistapaus.Väitämme, että jos ei ole olemassa Surjektiota Σ∗onto 2σ ∗ , niin ei ole surjektiota from Nonto 2σ∗myöskään.
Proof. Oletetaan ristiriitaisesti, että on olemassa surjektiog:N→ 2 Σ ∗ . Mutta, jos Σ 6 = λ, niinσ∗on ääretön ja numeroituva, niin meillä on Bijektiov: Σ∗→N. Silloin koostumus
Σ∗ ν // n
g / / 2 Σ ∗
on surjektio, koska bijektio on surjektio,gis surjektio ja surjektioiden koostumus on surjektio, mikä on ristiriidassa sen hypoteesin kanssa, että ei ole surjektiota osoitteestaσ∗päälle 2σ ∗ .
2.3. Kieliin liittyvät operaatiot 19
2.3 kieliin liittyvät operaatiot
yksinkertaisemmista kielistä voidaan rakentaa monimutkaisempia kieliä yhdistämällä ne eri operaatioiden avulla. Ensinnäkin, tarkastelemme set-theoretic operations unionin, risteysalueiden, andcompementation.
Koska jotkut aakkoset Σ, tahansa kaksi languagesL 1 ,L 2 yli Σ, theunionL 1 ∪L 2 ofL 1andL 2 on kieli
L 1 ∪L 2 ={w∈Σ∗|w∈L 1 tai w∈L 2 }.
TheintersectionL 1 ∩L 2 ofL 1 ja 2 on kieli
L 1 ∩L 2 ={w∈Σ∗|w∈L 1 ja w∈L 2 }.
L 1: n ja L 2: n Differencel 1 −L 2 on kieli
L 1 −L 2 ={W∈Σ∗|w∈L 1 ja W /∈L 2 }.
erotusta kutsutaan myös therelatiiviseksi komplementiksi.
erotuksesta saadaan erikoistapaus, kun L 1 = Σ∗, jolloin määritellään komplementlof a languageLas
L = {W∈Σ∗|w / ∈l}.
edellä mainituissa operaatioissa ei käytetä merkkijonojen rakennetta. Seuraavissa operaatioissa käytetään yhteistoimintaa.
määritelmä 2.8.Koska aakkoset Σ, tahansa kaksi languagesL 1 ,L 2 yli Σ, theconcatenationL 1 L 2 ofL 1 ja 2 on kieli
L 1 L 2 ={w∈Σ∗|∃u∈L 1 ,∃v∈L 2 , w=uv}.
mille tahansa kielelle määrittelemme seuraavan määritelmän:
L 0 = {ǫ}, Ln+1 = LnL (N≥0).
settingn= 0 inLn+1=LnL, sinceL 0 ={ǫ}, saadaan
L 1 =L0+1=L 0 L={ǫ}L=l,
soL 1 =L.
20 luku 2. PERUSASIAT VIRALLISEN KIELEN TEORIA
seuraavat ominaisuudet ovat helposti todennettavissa:
L∅=∅,∅L=∅,L{ǫ}=L{ǫ}L=L(L-1 ∪{ǫ})L 2 =L 1 L 2 ∪L 2 ,L-1 (L-2 ∪{ǫ}) =L 1 L 2 ∪L 1 ,LnL=LLn.
yleisesti, L 1 L 26 =L 2 L 1.So far, operaatiot, jotka olemme ottaneet käyttöön, paitsi täydentäminen (sinceL= Σ∗ – Lis ääretön ifLis äärellinen ja Σ on nonempty), säilyttää äärellisyyden kielten. Näin ei ole kahdessa seuraavassa operaatiossa.
määritelmä 2.9.Koska kirjaimisto Σ, mille tahansa kielelle Σ, theKleene∗ – closureL∗ofLis kieli
l∗ =