CIS 262 nyelvek

Bevezetés a Számításelméletbe

Jean Gallierszámítógép-és Információtudományi Tanszék Pennsylvaniai Egyetemaphiladelphia, PA 19104, USAe-mail:[email protected]

ca Jean Gallierkérem, ne reprodukáljaa szerző engedélye nélkül

március 5, 2020

4 Tartalomjegyzék

• 6.4 a pumpáló Lemma
• 6.5 gyors algoritmus az állapot ekvivalencia ellenőrzésére
• 7 Kontextusmentes nyelvtanok és Nyelvek
• 7.1 Kontextusmentes nyelvtanok
• 7.2 származékok és Kontextusmentes Nyelvek
• 7.3 normál formák Kontextusmentes Nyelvtanokhoz
• 7.4 a reguláris Nyelvek Kontextusmentesek
• 7.5 haszontalan produkciók Kontextusmentes Nyelvtanokban
• 7.6 A Greibach normálforma
• 7.7 legkevésbé rögzített pontok
• 7.8 Kontextusmentes nyelvek a legkevésbé rögzített pontok
• 7.9 legkevésbé rögzített pontok és a Greibach normál forma
• 7.10 fa domének és Gorn fák
• 7.11 származékok fák
• 7.12 Ogden Lemma
• 7.13 Pushdown automaták
• 7.14 a Kontextusmentes Nyelvtanoktól a PDA-kig
• 7.15 a PDA-któl a Kontextusmentes Nyelvtanokig
• 7.16 a Chomsky-Schutzenberger-tétel
• 8 A LR-elemzési módszerek felmérése
• 8.1 LR(0) – jellemző automaták
• 8.2 Shift/csökkentése értelmezők
• 8.3 kiszámítása az első
• 8.4 az intuíció mögött a Shift/csökkentése algoritmus
• 8.5 a gráf Módszer Számítási fix pontok
• 8.6 számítása nyomon
• 8.7 ALGORITHMTRAVERSE
• 8.8 további onLR (0)-jellemző automaták
• 8.9 LALR(1) – Lookahead készletek
• 8.10 számítástechnika első, kövesse, stb. a
• 8.11 LR(1)-jellemző automaták

Bevezetés

a számítás elmélete algoritmusokkal és algoritmikus rendszerekkel foglalkozik: azok tervezésével és ábrázolásával, teljességével és összetettségével.

ezeknek a megjegyzéseknek az a célja, hogy bemutassák a számításelmélet néhány alapvető fogalmát, beleértve a formális nyelvek és az automaták elméletét, a számíthatóság elméletét, a rekurzív függvényelmélet néhány alapját és a komplexitáselmélet bevezetését. Más témák, mint például a programok helyessége, itt nem lesznek kezelve (csak nincs elég idő!).

a jegyzetek három részre vannak osztva. Az első rész szenteltformális nyelvekés automaták. A második rész a számítási modellekkel, a rekurzív függvényekkel éshatározhatatlanság. A harmadik rész a számítási komplexitással foglalkozikkülönösen az osztályokpandnp.

5

a formális Nyelvelmélet alapjai

2.1 néhány alapvető matematikai jelölés áttekintése és

N,Z,Q,R, C.

természetes számok, N={ 0, 1, 2,…}.

Theintegers, Z={…,− 2 ,− 1 , 0 , 1 , 2 ,…}.

Nemzeti,

Q=

{

pq

}

null

Thereals, R. Thecomplex számok, C={A + ib / a, b ++ r}.

adott setX, thepower setofXis az összes részhalmaz halmaza xés jelöljük 2x.a jelölés f:X ons y

jelöli afunctionwithdomainXandrange(orcodomain)Y.

graph(f) ={(x,f(x)}|x kb x} ~ x ~ y

jelentése thegraphoff.

7

8 2. fejezet. A formális NYELVELMÉLET alapjai

Im(f) =f(X) ={Y 6 |x x, y=f (x)} 6439>

a kép.

általánosabban, IFA(X), akkor

f(A) ={y(Y) x (x)} (y) y

a (közvetlen) imageofA.

IfB, akkor F− 1 (B) ={x 6|f(x) B} A X X

a fordított kép(vagy hátlap) B.

f− 1 (B) egy halmaz; lehet, hogy üres, még akkor is, hab 6=++.Adott két functionsf:X→Y andg:Y→Z, a functiong◦f:X→Zgiven a

(g◦f)(x) =g(f(x)) a allx∈X

az thecompositionoffandg.

a függvény idX:X 6x által megadott

idX(x) =x minden x 6 x x

a functionf: X 6 Y izinjektív (régi terminológiaegy az egyhez)ha az összeshezx 1, x 2, x 3439>

iff (x 1) =f (x 2), akkorx 1 = x 2 ;

ekvivalens ifx 16 = x 2, majdf(x 1 ) 6 =f (x 2 ).

tény: IfX 6 =(és szója 6 = 6), a függvényf:X 6 Y injektív, ha van egy függvényr:Y 6(aleft inverz) oly módon, hogy

r= f = idX.

Megjegyzés:ris surjektív.Egy functionf:X→Y issurjective(régi terminologyonto), ha az ally∈Y, van somex∈Xsuch thaty=f(x), ifff(X) =Y

Tény: IfX 6 =∅(valamint szója 6 =∅), egy functionf:X→Y surjective ha van egy funkciója van:Y →X(legutóbb inverseorsection) olyan, hogy

f◦s= idY.

10 2.fejezet. ALAPOKAT A HIVATALOS NYELV ELMÉLET

EGY relationR⊆X×Xissymmetricif a allx,y∈X, ha (x,y)∈R, akkor (y,x)∈R

Egy relationR⊆X×Xis szimmetrikus iffR− 1 ⊆R.

GivenR⊆X×X(egy kapcsolatban onX), defineRnby

R 0 =IXRn+1=R◦Rn.

Thetranstive closureR+ofRis által adott

R+=

⋃

n 6

Rn.

tény.R+a legkisebb tranzitív kapcsolat, amely tartalmazzar.

a

r által megadott Flexív és tranzitív zárójelben szereplő∗=

⋃

n 0

Rn=R + 6X.

tény.R a legkisebb tranzitív és reflexív reláció, amely r-t tartalmaz.

Egy relationR⊆X×Xis anequivalence relationif ez reflexív, szimmetrikus, illetve tranzitív.

tény. A legkisebb ekvivalencia reláció, amely relationR⊆X×Xis által megadott

(R∪R− 1 )∗.

Egy relationR⊆X×Xisantisymmetricif a allx,y∈X, ha (x,y)∈Rand (y,x)∈R,thenx=y.

Egy relationR⊆X×Xis apartial érdekében, ha reflexív, tranzitív, valamint antisymmetic.

részleges orderR ⊆X×X-ó, annak érdekében, ha a allx,y ∈X, vagy (x,y)∈ Ror(y,x)∈R.

2.2 Ábécé, Húrok, Nyelvek

A kilátás, a nyelvek, az egy nyelv, egy szálat. A karakterlánc viszont végesbetűk sorozata néhány ábécéből. Ezeket a fogalmakat szigorúan a következőképpen határozzák meg.

meghatározás 2.1.Analphabet (analphabet) az anyfiniteset (anyfiniteset).

2.2. Ábécék, karakterláncok, nyelvek 11

gyakran írunk Xhamstereket = {a 1,…, ak}. Az Alphabet szimbólumainak hívják.Példák:Σ ={a}Σ ={a,b,c}Σ ={ 0 , 1 }Σ ={α,β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν a pillanatnyi,ρ,σ,η,ξ,z}Egy karakterlánc egy véges sorozata, szimbólumok. Technikailag kényelmes a karakterláncok meghatározásafunkciókat. Bármely egész számra 1, legyen

={ 1 , 2 ,…, n},

és forn= 0, let=++.

meghatározás 2.2. Adott egy ábécé, amely a nisany függvény

u hosszúságúakat(vagy egyszerűen csak egy karakterláncot) összehúzza: (u).

az egészhossz a stringu, és ez jelöli a|u|. Amikor N= 0, a speciális stringu: a 0 hosszúságú xhamstereket üres stringnek vagy null stringnek nevezzük, és a jelölésükdecontinible.

adott stringu: hosszúságún 1,u(i) az i-edik betű a stringu-ban. A jelölések sim-plicitására írunkeuiinstead ofu(i), és jelöljük a stringu=u(1)u(2)···u (n)mint

u=u 1 u 2 ···un,

mindenui-val.

például,ha a (Z) ={A, b}Ésu: a(z) a(1) =A,U(2) =b, andu (3) =a, írjukeu=Aba.

további példák a húrok

munka, szórakozás, gabuzomeuh

húrok hossza 1 vannak functionsu: ++ egyszerűen szedés néhány elementu(1) =aiin++.Így minden szimbólumot azonosítunkai a megfelelő hosszúságú 1-es karakterlánccal.

az ábécé fölötti összes karakterlánc halmazát, beleértve az üres karakterláncot is,a következőképpen jelöljük:++.

2.2. Ábécék, karakterláncok, nyelvek 13

az alap casen= 0, sinceu 0 =ons, van

u 0 u=onlinu=u=u ++ =u 0.

az indukciós lépéshez

un+1u= (unu)u definíció szerintun+ = (uun)u az indukciós hipotézis szerint =u(unu) asszociativitás szerint =uun+1 definíció szerintun+1.

meghatározás 2.4.Ha van egy ábécé, akkor a két karakterláncot is megadjuk, v a következők a következők:

UIS a viff előtagja van valami oly módon, hogy

v=uy.

uis egy utótag ofviff van somex 6 oly módon, hogy

v=Xu.

ua viff egy részstringje van néhányx,y oly módon, hogy

v=xuy.

azt mondjuk, hogyuis a megfelelő előtagja (utótag, alszöveg) ofviffuis előtagja (utótag,alszöveg)ofvandu 6 =v.

például gais előtagja gabuzo,zois utótagja gabuzoésbuzis egy alszöveg ofgabuzo.Emlékezzünk arra, hogy a részrendezés egy halmazon egy bináris reláció, amely rugalmas, tranzitív és antiszimmetrikus.

az előtag, az utótag és az alszöveg fogalmai bináris viszonyokat határoznak meg az Obviousway-N. Megmutatható, hogy ezek a kapcsolatok részleges megrendelések.

egy másik fontos sorrend a karakterláncokon a lexikográfiai (vagy szótár) sorrend.

meghatározás 2.5. Adott ábécé ={A 1 ,…, ak}feltételezve, hogy teljesen rendezett ilyen1 < a 2 <···< ak, bármely két stringsu, v, mi definiáljuk alexikográfiai sorrendaz alábbiak szerint:

UV







(1) ifv = uy, néhány esetben, vagy(2) IfU=xaiy,v=xajz,AI< aj,withai,aj 6613, s néhány esetben X,Y,Z esetén.

14 2.fejezet. A formális NYELVELMÉLET alapjai

az ötlet az, hogy egyszerre szkenneljük balról jobbra, összehasonlítva thsymboluminuto themth symbolvminv, kezdve M= 1. Ha nem merül fel eltérés, thatis, ha ők-TH symboluminuagreesvelük-TH symbolvminvform= 1,…,| u/, thenuis előtagjaés ezt kijelentjükpéldátlanul a lexikográfiai sorrendben. Ellenkező esetben egy ideiguandvagree egy közös prefixx(esetleg az üres karakterlánc) mentén, majdvan aleftmost eltérés, ami azt jelentiuis a formu=xaiyandvis aformv=xajz, withai 6 =aj (andx,y,z tetszőleges). Akkor meg kell szakítanunk a nyakkendőt, ésehhez használjuk azt a tényt, hogy a szimbólumoksa 1 < a 2 <···< feltételezzük, hogy az ak (teljesen)rendezett, tehát meglátjuk, hogy melyik aaiandajjön először, sayai< AJ, és kijelentjük, hogyu=xaiyporedesv=xajzin a lexikográfiai sorrend.

vegye figyelembe, hogy az (1) és (2) esetek kölcsönösen kizárják egymást. Az (1) esetben uis előtag ofv. A(2)esetben v6uandu 6 =v.

például ABB, gallhagergallier.

meglehetősen unalmas bizonyítani, hogy a lexikográfiai rendezés valójában apartiális rendezés.Valójában, ez atotal rendelés, ami azt jelenti, hogy bármely két stringsu, v++, eitheruv, orvu.

Areversalwrof a stringwinduktívan a következőképpen határozható meg:

argentinr=caur,(ua)R=auR,

Hola (a) és a (Z) uu++.

például reillag=gallierR.

Által settingu=ǫin (ua)R=auR,

sinceǫR=ǫanda=ǫa kapunk

aR= (ǫa)R=aǫR=aǫ=a,

namelyaR=amert alla∈Σ.

a|v|indukcióval kimutatható, hogy

(uv)R=vRuR.

hasznos trükk, amely csökkenti a nehézkes jelöléseket, amikor a húrok indukcióját végzi, az a megfigyelés, hogy anonempty húrokw hosszúságún+ 1 (n ~ 0) írható

w=ua, someuu-ra és néhány Symbola-ra a|u|=n.

16 2.fejezet. A formális NYELVELMÉLET alapjai

Ifxnem az üres halmaz, sincef:X .. Nis egy injekció, ha van egy surjectionr: N .. Xsuch thatr .. F= idX, a setXis megszámlálható, ha van asurjectionfromNontoX.

tény. Megmutatható, hogy egy halmazxszámlálható, ha véges, vagy ha benne van bijektionwithn(ebben az esetben végtelen).

később látni fogjuk, hogyn .. NIS megszámlálható. Ennek következtében a racionális számok halmazaszámlálható.

egy halmaz megszámlálhatatlan, ha nem megszámlálható.

például R (a valós számok halmaza) megszámlálhatatlan.Hasonlóképpen

(0,1) ={x ons| 0 < x < 1 }

megszámlálhatatlan. Van azonban egy bijekció között(0,1) andR (találj egyet!) A készlet 2naz összes részhalmaz ofnis megszámlálhatatlan. Ez a Cantor-tétel különleges eseteaz alábbiakban tárgyaljuk.

tegyük fel, hogy / 6 / = KH-val, – vel ={a 1,…, ak}. Először is figyeld meg, hogy vannakhossz húrokés (kn+1-1)/(k−1) hosszúságú húrok legfeljebb Hosszúságúakk= 1, A második képletet ki kell cserélnin+ 1. Valóban, mivel egy karakterlánc egy függvényu: {1,…, n} 6, ahosszú húrok számaa függvények száma {1,…, n} – re, és mivel a kardinalitása ISK, vannak ilyen függvények (ezt azonnal indukció mutatja onn). Ezután a legtöbb hosszúságú húrok számanis

1 + k + k 2 +···+kn.

ha k = 1, akkor ez a szám n+ 1, és ha k!! 2, mint egy geometriai sorozat összege, akkor(kn+1-1)/(k−1).

Ha 6 = 6, akkor az összes karakterláncok száma végtelen és megszámlálható, amint azt most megmutatjuk, ha egy explicit bijection-t építünk ki onnantól.

Ifk= 1 writea=a 1 , majd

{a} ++ ={ ++ , A, aa, aaa,…, egy,…}.

megvan a bijekción7.Ifk 2, akkor gondolhatunk a

u=ai 1 ···ain

mint az egész ábrázolásav(u) ban ben basekváltva (kn−1)/(k−1), val vel

2.2. Ábécék, húrok, nyelvek 17

ons =I 1 kn− 1 +i 2 kn− 2 +···+in-1 k + in

=

kn-1k− 1

• (i 1-1) kn− 1 +···+ (in− 1 -1)k+in− 1.

(és withv ( 6) = 0), ahol 1 IJ IJ kforj= 1,…, n.

gyakorlatként hagyjuk, hogy ezt megmutassukv: 6 Nis egy Bijekció. Meglepően nehéz megtalálni a vis inverzét(ez egy képlet).

tény, hogy a xhamsternek az a száma, ahol a példa nélküli v if / u| < |v|, éspéldátlanv a lexikográfiai sorrendben, ha|u|=|v|. Könnyen ellenőrizhető, hogy a fentieláció (uporedesv) teljes rend.

például, ifk= 2,és ha azt írjuk, hogy ={a,b}, akkor a felsorolás

– vel kezdődik,0a , b ,1, 2, aa, ab,ba , bb , 3 , 4 ,5, 6, aaa, aab, aba, abb, BAA, bab, BBA, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14

a következő sor eléréséhez összefűznia bal oldalon, majd összefűznia bal oldalon. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

működik!

másrészt, ha 6 = 6, akkor a 2-es halmaza minden részhalmazának(minden nyelv) megszámlálhatatlan.Valóban, meg tudjuk mutatni, hogy nincs surjection fromNonto 2 ++ első, megmutatjuk, hogy nincs surjection from otherc-tól 2 ++ – ig. Ez a Cantor-tétel különleges esete.Azt állítjuk , hogy ha nincs Surjekció A (Z) – tól A (Z) – ig 2 (Z) – ig, akkor nincs surjekció A (Z) – tól 2 (Z) – ig 2 (Z) – ig).

bizonyíték. Tegyük fel ellentmondással, hogy van egy surjectiong:N 6 . De ha 6 = 6, akkor végtelen és megszámlálható, tehát megvan a bijekcióv: N. Ekkor a

ca. // N

G // 2 AC.

egy surjekció, mert a bijekcióvis egy surjekció,gis egy surjekció, és a surjekció összetétele egy surjekció, ami ellentmond annak a hipotézisnek, hogy nincs surjekció A (Z) közül a (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z) A (Z)

2.3. Műveletek a nyelveken 19

2.3 műveletek a nyelveken

a bonyolultabb nyelvek egyszerűbb nyelvekből történő felépítésének egyik módja az, hogy különböző műveletekkel kombinálják őket. Először áttekintjük az Unió, a kereszteződés éskiegészítését.

Adott egy abc Σ, bármely két languagesL 1 ,L 2, Σ, theunionL 1 ∪L 2 ofL 1andL 2 a nyelv

L 1 ∪L 2 ={w∈Σ∗|w∈L 1 vagy w∈L 2 }.

az L 1. és L. 2. szakasz a

L 1. és L. 2. szakasz a nyelv l. 7996 > L. ={w. és W. L. 1. és W. L. 2.}.

az 1 −L2|l 1 és az L 2 közötti különbség a nyelv

L 1 −L 2 ={h /h / h / h }.

a különbséget is nevezikrelatív KOMPLEMENT.

a különbség különleges esetét akkor kapjuk meg, amikorl 1 = ons, ebben az esetben definiáljuk a kiegészítéstegy nyelvhezmint

l={w ons|SC}.

a fenti műveletek nem használják a húrok szerkezetét. A következő műveletek használjákkoncetenáció.

meghatározás 2.8.Adott egy abc Σ, bármely két languagesL 1 ,L 2, Σ, theconcatenationL 1 L 2 ofL 1 andL 2 a nyelv

L 1 L 2 ={w∈Σ∗|∃u∈L 1., ∃v∈L 2 , w=uv}.

bármely nyelv esetében a következőképpen határozzuk meg:

L 0 ={ons}, Ln+1=LnL (n 0).

a settingn= 0 inLn+1=LnL, sinceL 0 ={xHamster}, kapunk

L 1 =L0+1=L 0 L={XHamster}L=L,

soL 1 =L.

20 2.fejezet. ALAPOKAT A HIVATALOS NYELV ELMÉLET

A következő tulajdonságok könnyen ellenőrizni:

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.

általában L 1 L 26 =L 2 L 1.So az általunk bevezetett műveletek, kivéve a komplementációt (sinceL= ++ −lis Infinite iflis véges, és a ++ nem üres), megőrzik a nyelvek végességét. Ez nem így vana következő két művelet esetében.

meghatározás 2.9.Ha egy ábécét adunk hozzá, minden nyelvheza többit, a többit, a többit, a háromt, a háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a Háromt, a