Fogalomt´ ar a Form´ alis nyelvek ´ es automat´ ak t´ argyhoz (A t¨ orzsanyaghoz tartoz´ o defin´ıci´ okat ´ es t´ eteleket * jel¨ oli.)
Defin´ıci´ ok Univerz´ alis ´ ab´ ec´ e: Szimb´ olumok egy megsz´aml´alhat´oan v´egtelen halmaz´at univerz´alis ´ab´ec´enek nevezz¨ uk. *
´ ec´enek nevezz¨ ´ ec´ Ab´ e: Ab´ uk az univerz´ alis ´ab´ec´e egy tetsz˝oleges v´eges r´eszhalmaz´at.
*
Bet˝ u: Az ´ ab´ec´e elemeit bet˝ uknek h´ıvjuk.
*
Sz´ o: Az X ´ ab´ec´e elemeinek egy tetsz˝ oleges v´eges sorozat´at az X ´ab´ec´e feletti sz´onak nevezz¨ uk. Ha X nem l´enyeges vagy egy´ertelm˝ u, akkor sz´or´ol besz´el¨ unk.
*
Nyelv: X ∗ valamely r´eszhalmaz´ at (azaz 2X valamely elem´et) az X ´ab´ec´e feletti nyelvnek nevezz¨ uk.
*
Nyelvoszt´ aly (nyelvcsal´ ad): Nyelvek valamely ¨osszess´eg´et nyelvoszt´alynak, nyelvcsal´adnak h´ıvjuk.
*
K´ et sz´ o konkaten´ aci´ oja: Az u = t1 · · · tk ´es v = t01 · · · t0` szavak konkaten´aci´oja alatt az uv := t1 · · · tk t01 · · · t0` sz´ ot ´ertj¨ uk. (A k´et sz´o egym´as ut´ani le´ır´as´aval kapott sz´o.)
*
Sz´ o hatv´ anya: Legyen u egy sz´ o, nemnegat´ıv eg´esz hatv´anyai u0 := ε, u1 := u, un := un−1 u. (rekurz´ıv defin´ıci´ o)
*
Sz´ o megford´ıt´ asa: Legyen u = t1 · · · tk egy sz´o, ekkor u megford´ıt´asa u−1 := tk · · · t1 .
∗
Homomorfizmus: A h : X ∗ 7−→ Y ∗ konkaten´aci´otart´o lek´epez´eseket homomorfizmusnak nevezz¨ uk. h konkaten´ aci´ otart´ o lek´epez´es, ha tetsz˝oleges u, v ∈ X ∗ sz´o eset´en h(uv) = h(u)h(v). Homomorfizmus nyelvekre val´ o kiterjeszt´ ese: h(L) :=
S
u∈L {h(u)}.
*
K´ et nyelv metszete, uni´ oja, k¨ ul¨ onbs´ ege, szimmetrikus differenci´ aja: A nyelv is egy halmaz (szavak halmaza), ezeket mint halmazokon vett m˝ uveleteket ´ertelmezz¨ uk.
*
Nyelv komplementere: Egy X ´ ab´ec´e feletti nyelv komplementer´en a halmazelm´eleti ´ertelemben vett komplementert ´ertj¨ uk X ∗ -ra n´ezve.
*
K´ et nyelv konkaten´ aci´ oja: Legyenek L1 , L2 nyelvek. Ekkor az L1 ´es L2 nyelvek konkaten´aci´o j´ an az L1 L2 := {uv u ∈ L1 ∧ v ∈ L2 } nyelvet ´ertj¨ uk.
*
Nyelv hatv´ anya: Legyen L egy nyelv, nemnegat´ıv eg´esz hatv´anyai L0 := {ε}, L1 := L, Ln := Ln−1 L. (rekurz´ıv defin´ıci´ o)
*
Nyelv lez´ artja (iter´ altja): Legyen L egy nyelv. L∗ :=
*
S∞ Nyelv pozit´ıv lez´ artja (iter´ altja): Legyen L egy nyelv. L+ := i=1 Li az L nyelv pozit´ıv lez´ artja. Nyelv megford´ıt´ asa: Legyen L egy nyelv. L−1 := {u−1 u ∈ L} az L nyelv megford´ıt´asa. 1
S∞
i=0
Li az L nyelv lez´artja.
*
R´ eszsz´ o: v r´eszszava u-nak, ha l´eteznek olyan w1 , w2 szavak, melyre u = w1 vw2 . Sz´ o egy prefixe: v az u sz´ o prefixe, ha van olyan w sz´o, hogy u = vw. v val´odi prefix, ha v 6= ε, u. Sz´ o prefixhalmaza: Legyen u egy sz´ o. Pre(u) := { v v prefixe u-nak} az u sz´o prefixhalmaza.
*
Sz´ o legfeljebb i hossz´ us´ ag´ u prefixhalmaza: Pre(u, i) := Pre(u) ∩ X(u)≤i . u `(u) ≤ i Sz´ o i hossz´ us´ ag´ u prefixe: pre(u, i) := . v v ∈ Pre(u) ∧ `(v) = i Sz´ o egy suffixe: v az u sz´ o suffixe, ha van olyan w sz´o, hogy u = wv. v val´odi suffix, ha v 6= ε, u. Sz´ o suffixhalmaza: Legyen u egy sz´ o. Suf(u) := { v v suffixe u-nak} az u sz´o suffixhalmaza.
*
Sz´ o legfeljebb i hossz´ us´ ag´ u suffixhalmaza: Suf(u, i) := Suf(u) ∩ X(u)≤i . u `(u) ≤ i Sz´ o i hossz´ us´ ag´ u suffixe: suf(u, i) := . v v ∈ Suf(u) ∧ `(v) = i Nyelv prefixhalmaza: Legyen L egy nyelv. Pre(L) :=
S
Nyelv suffixhalmaza: Legyen L egy nyelv. Suf(L) :=
S
u∈L
u∈L
Pre(u) az L nyelv prefixhalmaza.
Suf(u) az L nyelv suffixhalmaza.
*
Regul´ aris nyelvek: (rekurz´ıv defin´ıci´ o) • az elemi nyelvek, azaz ∅, {ε}, {a} (a ∈ U ) • azon nyelvek, melyek az elemi nyelvekb˝ol az uni´o, konkaten´aci´o ´es lez´ar´as m˝ uveletek v´eges sz´ am´ u alkalmaz´ as´ aval ´ allnak el˝ o
*
Regul´ aris kifejez´ esek: (rekurz´ıv defin´ıci´ o) • az elemi regul´ aris kifejez´esek, azaz ∅, ε, a (a ∈ U ) • ha R1 ´es R2 regul´ aris kifejez´esek akkor (R1 ∪ R2 ), (R1 R2 ), R1∗ is regul´aris kifejez´esek • a regul´ aris kifejez´esek halmaza a legsz˝ ukebb halmaz, melyre a fenti k´et pont teljes¨ ul
*
X ´ ab´ ec´ e feletti regul´ aris kifejez´ esek: (rekurz´ıv defin´ıci´ o) • az elemi regul´ aris kifejez´esek, azaz ∅, ε, a (a ∈ X) • ha R1 ´es R2 X ´ ab´ec´e feletti regul´aris kifejez´esek akkor (R1 ∪ R2 ), (R1 R2 ), R1∗ is X ´ab´ec´e feletti regul´ aris kifejez´esek • ax X ´ ab´ec´e feletti regul´ aris kifejez´esek halmaza a legsz˝ ukebb halmaz, melyre a fenti k´et pont teljes¨ ul
*
X ´ ab´ ec´ e feletti ´ altal´ anos´ıtott regul´ aris kifejez´ esek: (rekurz´ıv defin´ıci´ o) • az elemi regul´ aris kifejez´esek, azaz ∅, ε, a (a ∈ X) • ha R1 ´es R2 X ´ ab´ec´e feletti ´ altal´anos´ıtott regul´aris kifejez´esek akkor (R1 ∪ R2 ), (R1 R2 ), R1∗ , (R1 ∩ R2 ), R1 is X ´ ab´ec´e feletti ´altal´anos´ıtott regul´aris kifejez´esek • az X ´ ab´ec´e feletti ´ altal´ anos´ıtott regul´aris kifejez´esek halmaza a legsz˝ ukebb halmaz, melyre a fenti k´et pont teljes¨ ul
*
Regul´ aris kifejez´ esek szemantik´ aja: (rekurz´ıv defin´ıci´ o) • az ∅, ε, a regul´ aris kifejez´esek rendre az ∅, {ε}, {a} nyelveket reprezent´alj´ak • ha R1 az L1 illetve R2 az L2 nyelvet reprezent´alja, akkor (R1 ∪ R2 ), (R1 R2 ), R1∗ rendre az L1 ∪ L2 , L1 L2 , L∗1 nyelveket reprezent´alja.
2
*
X ´ ab´ ec´ e feletti ´ altal´ anos´ıtott regul´ aris kifejez´ esek szemantik´ aja: (rekurz´ıv defin´ıci´ o) • az ∅, ε, a elemi regul´ aris kifejez´esek rendre az ∅, {ε}, {a} nyelveket reprezent´alj´ak • ha R1 az L1 illetve R2 az L2 nyelvet reprezent´alja, akkor (R1 ∪R2 ), (R1 R2 ), R1∗ , (R1 ∩R2 ), R1 rendre az L1 ∪ L2 , L1 L2 , L∗1 , L1 ∩ L2 , L1 nyelveket reprezent´alja.
*
Rekurz´ıvan felsorolhat´ o nyelv: Az L nyelv rekurz´ıvan felsorolhat´o ⇐⇒ ha l´etezik A algoritmus, mely az elemeit felsorolja. Felsorol´o algoritmus: Az A algoritmus outputj´ara szavakat all´ıt el˝ ´ o, s ´ıgy a nyelv ¨ osszes szav´ at (´es csak azokat) felsorolja.
*
Parci´ alisan rekurz´ıv nyelv: Az L nyelv parci´alisan rekurz´ıv ⇐⇒ l´etezik olyan A parci´alisan eld¨ ont˝ o algoritmus, melynek inputj´ ara tetsz˝oleges sz´ot helyezve eld¨onti, benne van-e a nyelvben (u ∈ L sz´ o eset´en igen v´ alasszal ´all le, m´ıg u 6∈ L eset´en nem termin´al, vagy ha termin´al, akkor nem v´ alaszt ad).
*
Rekurz´ıv nyelv: Az L nyelv rekurz´ıv ⇐⇒ l´etezik olyan A eld¨ont˝o algoritmus, melynek inputj´ara egy tetsz˝ oleges u sz´ ot helyezve eld¨onti, benne van-e az L nyelvben (mindig termin´al, igen a v´ alasz, ha u eleme az L nyelvnek, ´es nem a v´alasz ellenkez˝o esetben).
*
Generat´ıv nyelvtan (grammatika): A G = h T, N, P, S i n´egyest nyelvtannak nevezz¨ uk, ahol T a termin´ alis, N a nyelvtani (nemtermin´alis) jelek egym´ast´ol diszjunkt ´ab´ec´eje, P (produkci´os) szab´ alyoknak egy v´eges halmaza, ahol minden P ∈ P szab´aly p → q alak´ u, p, q ∈ (T ∪ N )∗ ´es p tartalmaz legal´ abb egy nyelvtani jelet, tov´abb´a S ∈ N , melyet kezd˝oszimb´olumnak nevez¨ unk.
*
Mondatforma: (T ∪ N )∗ elemeit mondatform´aknak nevezz¨ uk.
*
K¨ ozvetlen levezet´ es (nyelvtanban): Az α mondatform´ab´ol k¨ozvetlen¨ ul levezethet˝o a β mondatforma, ha l´eteznek γ1 , γ2 mondatform´ak ´es p → q ∈ P, hogy α = γ1 pγ2 ´es β = γ1 qγ2 . Jel¨ ol´ese: α → β. G
*
K¨ ozvetett levezet´ es (nyelvtanban): Az α mondatform´ab´ol k¨ozvetetten levezethet˝o a β mondatforma, ha l´etezik k ∈ N ´es γ0 , γ1 , . . . , γk mondatform´ak, hogy α = γ0 , β = γk ´es minden ∗ k i ∈ [0, k − 1] eset´en γi → γi+1 . Jel¨ol´ese: α → β. Ha fontos, hogy ´eppen k l´ep´esben: α → β. G G G Ekkor k a levezet´es hossza.
*
Nyelvtan ´ altal gener´ alt nyelv: A G = h T, N, P, S i nyelvtan ´altal gener´alt nyelv L(G) := ∗ ∗ S → u}. {u ∈ T G
Ekvivalens nyelvtanok: A G1 ´es G2 nyelvtanok ekvivalensek (G1 ∼ G2 ), ha L(G1 ) = L(G2 ). Kv´ aziekvivalens nyelvtanok: A G1 ´es G2 nyelvtanok kv´aziekvivalensek (G1 ∼ G2 ), ha kv
L(G1 ) \ {ε} = L(G2 ) \ {ε}. *
Nyelvtanok t´ıpusai: Egy G nyelvtan i. t´ıpus´ u (i ∈ {0, 1, 2, 3}), ha a szab´alyai a t´abl´azatban megadott alak´ uak (Alapt´ıpus szab´ alyai oszlop).
*
Nyelvtanok megszor´ıtott t´ıpusai: Egy G nyelvtan megszor´ıtott i. t´ıpus´ u (i ∈ {1, 2, 3}), ha a szab´ alyai a t´ abl´ azatban megadott alak´ uak (Megszor´ıtott t´ıpus szab´ alyai oszlop).
*
K¨ ornyezetf¨ uggetlen nyelvtan: 2. t´ıpus´ u nyelvtan.
*
K¨ ornyezetf¨ ugg˝ o nyelvtan: Megszor´ıtott 1. t´ıpus´ u nyelvtan.
3
*
Norm´ alform´ ak: Egy G nyelvtan i-es norm´alform´aj´ u (i = 1, 2, 3), ha a szab´alyai a t´abl´azatban megadott alak´ uak (Norm´ alforma szab´ alyai oszlop). Az t´abl´azatban megadott 1. t´ıpus´ u norm´ alforma elnevez´ese Kuroda norm´alforma, a 2. t´ıpus´ u´e Chomsky norm´alforma. T´ıpus
Alapt´ıpus szab´ alyai
Megszor´ıtott t´ıpus szab´alyai +
Norm´alforma szab´alyai
0.
nincs tov´ abbi megk¨ ot´es
p → q, ahol q ∈ (T ∪ N ) ; S → ε, ez esetben S nem szerepel szab´aly jobboldal´an
AB → A (A, B ∈ N ); BA → A (A, B ∈ N ); +Kuroda NF szab´alys´em´ai
1.
p → q, ahol `(p) ≤ `(q); S → ε, ez esetben S nem szerepel szab´ aly jobboldal´ an
γ1 Aγ2 → γ1 qγ2 , ahol γ1 , γ2 ∈ (T ∪ N )∗ , A ∈ N, q ∈ (T ∪ N )+ ; S → ε, ez esetben S nem szerepel szab´aly jobboldal´an
(Kuroda) A → a (A ∈ N, a ∈ T ); A → BC (A, B, C ∈ N ); AB → AC (A, B, C ∈ N ); BA → CA (A, B, C ∈ N ); S → ε, ez esetben S nem szerepel szab´aly jobboldal´an
2.
A → q, ahol A ∈ N, q ∈ (T ∪ N )∗
A → q, ahol A ∈ N, q ∈ (T ∪ N )+ ; S → ε, ez esetben S nem szerepel szab´aly jobboldal´an
(Chomsky) A → a (A ∈ N, a ∈ T ); A → BC (A, B, C ∈ N ); S → ε, ez esetben S nem szerepel szab´aly jobboldal´an
3.
A → uB vagy A → u, ahol A, B ∈ N , ´es u ∈ T ∗
A → aB vagy A → a ahol A, B ∈ N, a ∈ T ; S → ε, ez esetben S nem szerepel szab´aly jobboldal´an
A → ε vagy A → aB, ahol A, B ∈ N ´es a ∈ T
(A t´ abl´ azatban konvencion´ alisan S a kezd˝oszimb´olum) Greibach norm´ alforma Legyen G = hT, N, P, Si egy nyelvtan. A G nyelvtan Greibach-f´ele norm´ alform´ aj´ u, ha szab´ alyai a k¨ ovetkez˝o alak´ uak: S → ε, ahol S kezd˝oszimb´olum ´es ha van ilyen szab´ aly, akkor S nem fordul el˝o szab´aly jobboldal´an; A → aQ, ahol A ∈ N, a ∈ T, ´es ∗ Q∈N . Zs´ akutca: Olyan nyelvtani jel, melyb˝ ol az adott 2. t´ıpus´ u nyelvtanban nem vezethet˝o le termin´alis sz´ o. Nem el´ erhet˝ o nyelvtani jel: Olyan nyelvtani jel, mely az adott 2. t´ıpus´ u nyelvtanban semmilyen, a kezd˝ oszimb´ olumb´ ol t¨ ort´en˝ o levezet´esben nem szerepel. Zs´ akutcamentes nyelvtan: 2. t´ıpus´ u nyelvtan, melynek semmelyik nyelvtani jele se zs´akutca. ¨ Osszef¨ ugg˝ o nyelvtan: 2. t´ıpus´ u nyelvtan, mely nem tartalmaz nem el´erhet˝o nyelvtani jelet. Reduk´ alt nyelvtan: Zs´ akutcamentes ´es ¨osszef¨ ugg˝o 2. t´ıpus´ u nyelvtan. *
L´ ancszab´ aly: Egy G = h T, N, P, S i nyelvtanban p → q ∈ P l´ancszab´aly, ha p, q ∈ N .
*
L´ ancszab´ alymentes nyelvtan: Egy nyelvtan l´ancszab´alymentes, ha nincs l´ancszab´alya.
*
Epszilonszab´ aly: Egy G = h T, N, P, S i nyelvtanban p → q ∈ P epszilonszab´aly, ha q = ε.
*
Korl´ atozott epszilonszab´ aly (KeS): Egy G = h T, N, P, S i nyelvtanra teljes¨ ul a korl´atozott epszilonszab´ aly, ha nincsenek epszilonszab´alyai az S → ε szab´aly esetleges kiv´etel´evel, de 4
ebben az esetben minden p → q ∈ P szab´alyra q ∈ (T ∪ N \ {S})∗ (azaz semelyik szab´aly jobboldala sem tartalmazza a kezd˝oszimb´olumot). *
Epszilonmentes nyelvtan: Egy nyelvtan epszilonmentes, ha teljes¨ ul r´a a korl´atozott epszilonszab´ aly. Nyelvtani transzform´ aci´ o: A Φ nyelvtani transzform´aci´o olyan elj´ar´as, mely egy G nyelvtanb´ol, egy m´ asik, Φ(G) nyelvtant k´esz´ıt. Ekvivalens nyelvtani transzform´ aci´ o: Egy Φ nyelvtani transzform´aci´o ekvivalens nyelvtani transzform´ aci´ o, ha minden G nyelvtanra G ∼ Φ(G). Kv´ aziekvivalens nyelvtani transzform´ aci´ o: Egy Φ nyelvtani transzform´aci´o kv´aziekvivalens nyelvtani transzform´ aci´ o, ha minden G nyelvtanra G ∼ Φ(G). kv
T´ıpusmeg˝ orz˝ o nyelvtani transzform´ aci´ o: Legyen Gπ a π t´ıpus´ u nyelvtanok oszt´alya. Egy Φ nyelvtani transzform´ aci´ o meg˝ orzi a π t´ıpust, amennyiben minden G ∈ Gπ eset´en Φ(G) ∈ Gπ . *
Nyelvek t´ıpusai: Egy L nyelv (megszor´ıtott) i. t´ıpus´ u, ha l´etezik olyan (megszor´ıtott) i. t´ıpus´ u nyelvtan, mely L-et gener´ alja. (l. megszor´ıt´ asi t´etel).
*
Regul´ aris nyelv: 3. t´ıpus´ u nyelv. (l. Kleene t´etel)
*
K¨ ornyezetf¨ uggetlen nyelv: 2. t´ıpus´ u nyelv.
*
K¨ ornyezetf¨ ugg˝ o nyelv: 1. t´ıpus´ u nyelv. Nyelvi oper´ atorra z´ art nyelvcsal´ ad: Legyen Ψ n-v´altoz´os nyelvi oper´ator, azaz ha L1 , . . . , Ln nyelvek, akkor Ψ(L1 , . . . , Ln ) is legyen nyelv. Az L nyelvcsal´ad z´art a Ψ nyelvi oper´atorra, ha L1 , . . . , Ln ∈ L eset´en Ψ(L1 , . . . , Ln ) ∈ L. BNF: Egy Backus-Naur forma (BNF), a k¨ovetkez˝o ´ep´ıt˝ok¨ovekb˝ol ´all: hsz¨ovegi,::=,{,},|, egy´eb karakterek. hsz¨ ovegi a fogalmak, az egy´eb karakterek a termin´alisok. Egy BNF szab´aly baloldal´ an pontosan 1 fogalom ´ all, jobboldal´an fogalmak, termin´alisok, {,},| jelek sorozata all, u ´ ´gy hogy a sorozat helyesen z´ ar´ojelezett a {,} z´ar´ojelekkel. A k´et oldalt a ::= szimb´olum v´ alasztja el egym´ ast´ ol. Z´ ar´ ojelek ´es alternat´ıv´ ak jelent´ese: Az F ::= γ1 {α1 | · · · |αn }γ2 formula az F ::= γ1 α1 γ2 , . . ., F ::= γ1 αn γ2 formul´ akat reprezent´alja. Szemantik´ aja: Adott BNF szab´ alyok egy halmaza (z´ar´ojelek ´es alternat´ıv´ak n´elk¨ ul). Az α mondatform´ ab´ ol (termin´ alisok ´es fogalmak sorozata) k¨ozvetlen¨ ul levezethet˝o a β mondatforma, ha l´eteznek γ1 , γ2 , ξ mondatform´ak ´es F ::= ξ BNF szab´aly, hogy α = γ1 F γ2 ´es β = γ1 ξγ2 . A k¨ ozvetett levezet´est az eddigiekhez hasonl´oan defini´aljuk. Egy adott fogalom azon termin´ alis sorozatok halmaz´at reprezent´alja, mely bel˝ole, mint 1 hossz´ us´ag´ u mondatform´ ab´ ol k¨ ozvetetten levezethet˝ o. EBNF: A BNF-hez k´epest k´et tov´ abbi jel¨ol´est haszn´alunk. @γ, ahol γ egy fogalom, termin´alis, vagy csoport a 0, 1, 2, stb. hosszus´ag´ u, csak γ-b´ol ´all´o sorozatokat reprezent´alja. γkn , ahol 0 ≤ k ≤ n term´eszetes eg´esz sz´ amok ´es γ egy fogalom, termin´alis, vagy csoport a k, k+1, . . . , n hossz´ us´ ag´ u γ sorozatokat reprezent´alja. Szemantika: mint a BNF-n´el. Szintaxisgr´ af: Szintaxisgr´ af alatt olyan ir´any´ıtott gr´afot ´ert¨ unk, mely a k¨ovetkez˝o tulajdons´agokkal rendelkezik. Egyetlen forr´ asa ´es egyetlen nyel˝oje van. Az ´elek c´ımk´ezetlenek, a sz¨ogpontok
5
lehetnek c´ımk´ezettek ´es c´ımk´ezetlenek. A c´ımk´eknek k´et fajt´aja van, az egyik t´eglalap, a m´ asik ellipszis alak´ u. Ezen fel¨ ul a gr´afnak van egy neve. A t´eglalap alak´ u c´ımk´eket ´es a gr´af nev´et fogalmaknak, az ellipszis alak´ u c´ımk´eket termin´alisoknak nevezz¨ uk. Szemantik´ aja: Adott szintaxisgr´ afok egy halmaza. Az α mondatform´ab´ol (termin´alisok ´es fogalmak sorozata) k¨ ozvetlen¨ ul levezethet˝o a β mondatforma, ha l´eteznek γ1 , γ2 , ξ mondatform´ ak ´es F fogalom, hogy α = γ1 F γ2 , β = γ1 ξγ2 , tov´abb´a l´etezik olyan szintaxisgr´af, melynek c´ımk´eje F ´es a gr´ afban l´etezik ir´any´ıtott u ´t1 a forr´asb´ol a nyel˝obe, mely ment´en a c´ımk´ezett sz¨ ogpontok c´ımk´ei az ir´any´ıtott u ´t1 ´altal meghat´arozott sorrendben ´eppen ξ-t adj´ ak. A k¨ ozvetett levezet´est az eddigiekhez hasonl´oan defini´aljuk,. Egy adott fogalom azon termin´ alis sorozatok halmaz´ at reprezent´alja, mely bel˝ole, mint 1 hossz´ us´ag´ u mondatform´ab´ol k¨ ozvetetten levezethet˝ o. *
n-verem: n-verem alatt a k¨ ovetkez˝ o (2n + 5)-¨ost ´ertj¨ uk:
V = Q, T, Σ1 , . . . , Σn , δ, q0 , σ1 , . . . , σn , F , ahol Q T Σi δ q0 ∈ Q σi F ⊆Q
az ´ allapotok halmaza (ez legyen v´eges halmaz), egy ´ ab´ec´e, a bemen˝ o´ ab´ec´e, az i-edik verem ´ ab´ec´eje, az ´ allapot´ atmeneti f¨ uggv´eny, kezd˝ o´ allapot, az i. verem kezd˝ oszimb´oluma, ahol σi ∈ Σi , a v´eg´ allapotok halmaza. ∗
∗
Az ´ allapot´ atmeneti f¨ uggv´eny δ : Q × (T ∪ {ε}) × Σ1 × · · · × Σn → 2Q×Σ1 ×···×Σn alak´ u f¨ uggv´eny, melyre megk¨ ovetelj¨ uk, hogy ´ert´ekk´eszlete v´eges halmazokb´ol ´alljon. *
Veremautomata: 1-verem.
*
Konfigur´ aci´ o: Konfigur´ aci´ onak nevezz¨ uk azoknak az adatoknak az ¨osszess´eg´et, melyekt˝ol a g´ep elk¨ ovetkezend˝ o m˝ uk¨ od´ese f¨ ugg. A konfigur´ aci´ ok a k¨ ovetkez˝ o alak´ u (n + 2)-esek: [q, v, α1 , . . . , αn ], ahol: • q az aktu´ alis ´ allapot, • v az input sz´ o m´eg elolvasatlan r´esze, • αi az i-edik verem tartalma.
*
K¨ ozvetlen konfigur´ aci´ o´ atmenet: K¨ozvetlen konfigur´aci´o´atmenetr˝ol besz´el¨ unk, ha V egy l´ep´esben v´ alt ´ at egyik konfigur´ aci´ ob´ ol a m´asikba, azaz [q, u, α1 , . . . , αn ] a [q 0 , v, β1 , . . . , βn ] akkor V
´es csak akkor, ha van olyan t ∈ T ∪ {ε}, hogy u = tv, tov´abb´a minden i ∈ [1, n] eset´en van olyan σi ∈ Σi ´es γi , τi ∈ Σ∗i , amelyekre αi = σi γi , βi = τi γi , valamint (q 0 , τ1 , . . . , τn ) ∈ δ(q, t, σ1 , . . . , σn ). Ha itt t = ε, akkor ε-mozg´asr´ol besz´el¨ unk. *
K¨ ozvetett konfigur´ aci´ o´ atmenet: A k¨ozvetett konfigur´aci´o´atmenet a k¨ozvetlen ´atmenet ref∗
lex´ıv, tranzit´ıv lez´ artja. Jel¨ ol´ese: a. V
*
Kezd˝ okonfigur´ aci´ o: Az u sz´ ohoz tartoz´o kezd˝okonfigur´aci´o: [q0 , u, σ1 , . . . , σn ].
*
Termin´ al´ o konfigur´ aci´ o: Egy K konfigur´aci´o termin´al´o konfigur´aci´o, ha nincs r´ak¨ovetkez˝oje, 0 azaz @ K konfigur´ aci´ o, hogy K a K 0 . V
*
V´ eg´ allapottal elfogad´ o konfigur´ aci´ o: V´eg´allapottal elfogad´o egy [q, ε, β1 , . . . , βn ] konfigur´aci´o, 1 Itt
az u ´t egy ponton t¨ obbsz¨ or is ´ athaladhat. Ez val´ oj´ aban a gr´ afelm´ eleti s´ eta fogalomnak felel meg.
6
ha q ∈ F . *
¨ ¨ Ures veremmel elfogad´ o konfigur´ aci´ o: Ures veremmel elfogad´o egy [q, ε, β1 , . . . , βn ] konfigur´ aci´ o, ha β1 = ε.
*
Sz´ o v´ eg´ allapottal elfogad´ asa: A V n-verem v´eg´allapottal elfogadja az u sz´ot, ha l´etezik ´atmenet az u sz´ ohoz tartoz´ o kezd˝ okonfigur´aci´ob´ol v´eg´allapottal elfogad´o konfigur´aci´oba.
*
Sz´ ou ¨ res veremmel elfogad´ asa: A V n-verem u ¨res veremmel elfogadja az u sz´ot, ha l´etezik atmenet az u sz´ ´ ohoz tartoz´ o kezd˝ okonfigur´aci´ob´ol u ¨res veremmel elfogad´o konfigur´aci´oba. V´ eg´ allapottal elfogadott nyelv: A V ´altal v´eg´allapottal elfogadott nyelv: LF (V) = u ∈ T ∗ ∗ [q0 , u, σ1 , . . . , σn ] a [q, ε, β1 , β2 , . . . , βn ] valamely q ∈ F -re .
*
V
*
¨ Ures veremmel elfogadott nyelv: A V ´altal u ¨res veremmel elfogadott nyelv: ∗ ∗ u ∈ T [q0 , u, σ1 , . . . , σn ] a [q, ε, ε, β2 , . . . , βn ] .
Lε (V) =
V
*
Determinisztikus n-verem: Egy adott V n-verem determinisztikus, ha minden konfigur´aci´onak legfeljebb 1 r´ ak¨ ovetkez˝ oje van. Ekvivalens defin´ıci´ o: Egy adott V n-verem determinisztikus, ha a k¨ovetkez˝o k´et felt´etel teljes¨ ul: • Minden (q, t, σ1 , . . . , σn ) ∈ Dδ eset´en δ(q, t, σ1 , . . . , σn ) ≤ 1, • δ(q, ε, σ1 , . . . , σn ) 6= ∅ eset´en minden t ∈ T -re δ(q, t, σ1 , . . . , σn ) = 0.
*
Determinisztikus veremautomata: determinisztikus 1-verem.
*
V´ eges, ε-´ atmenetes nemdeterminisztikus automata (εNDA): 0-verem
*
V´ eges, nemdeterminisztikus automata (NDA): 0-verem, Dδ ⊆ {(q, t) | q ∈ Q, t ∈ T }.
melyre
V´ eges, parci´ alis determinisztikus automata (PDA): Determinisztikus Dδ ⊆ {(q, t) | q ∈ Q, t ∈ T }.
0-verem,
0-verem,
melyre
*
V´ eges determinisztikus automata (VDA): Determinisztikus Dδ = {(q, t) | q ∈ Q, t ∈ T }.
melyre
*
´ Allapot´ atmeneti f¨ uggv´ eny ´ altal´ anos´ıt´ asa: Legyen A = hQ, T, δ, q0 , F i egy v´eges determinisztikus automata. Rekurz´ıvan defini´aljuk δ(q, u) ´ert´ek´et (q ∈ Q, u ∈ T ∗ ). δ(q, ε) := q, δ(q, t) m´ ar defin´ alt (t ∈ T ). δ(q, ut) := δ(δ(q, u), t) (u ∈ T ∗ , t ∈ T ).
*
VDA ´ altal felismert nyelv ´ altal´ anos´ıtott ´ allapot´ atmeneti f¨ uggv´ ennyel megadva: Legyen A = hQ, T, δ, q0 , F i egy v´eges determinisztikus automata. Az A ´altal felismert (elfogadott) nyelv a k¨ ovetkez˝ o: L(A) := {u ∈ T ∗ δ(q0 , u) ∈ F }. Automata megad´ asa t´ abl´ azattal: A sorok megfelelnek Q elemeinek, az oszlopok T (´altal´anosabb automata eset´en X = T ∪ {ε} vagy X = R(T )) elemeinek. A q ∈ Q sornak ´es t ∈ T (vagy ´ altal´ anosabban t ∈ X) oszlopnak megfelel˝o cella tartalma δ(q, t). A kezd˝o´allapotot a →, a v´eg´ allapotokat ← szimb´ olummal megjel¨olj¨ uk.
7
*
Automata megad´ asa ´ atmenetdiagrammal: Ir´any´ıtott gr´af, ahol a sz¨ogpontok ´es az ´elek is c´ımk´ezettek. A sz¨ ogpontok megfelelnek Q elemeinek (a kezd˝o´allapotot a → szimb´olummal megjel¨ olj¨ uk, F elemeit bekarik´ azzuk), m´ıg az ´elek T (´altal´anosabb automata eset´en X = T ∪ {ε} vagy X = R(T )) elemeinek. q ∈ Q-b´ol vezet t ∈ T (vagy ´altal´anosabban t ∈ X) c´ımk´ej˝ u ir´ any´ıtott ´el q 0 ∈ Q-ba, akkor ´es csak akkor, ha q 0 = (∈)δ(q, t). ´ Altal´ anos´ıtott szekvenci´ alis automata: A = hQ, T, δ, q0 , F i ´altal´anos´ıtott szekvenci´alis automata, ha Q egy v´eges halmaz, az ´allapotok halmaza, T egy v´eges halmaz, az inputszavak ab´ec´eje, q0 ∈ Q a kezd˝ ´ o´ allapot, F ⊆ Q a v´eg´allapotok halmaza, tov´abb´a az ´allapot´atmeneti f¨ uggv´eny δ : Q × R(T ) → 2Q alak´ u f¨ uggv´eny, melyre megk¨ovetelj¨ uk, hogy v´eges tart´oj´ u legyen, azaz minden q ∈ Q-hoz csak v´eges sok R ∈ R(T ) eset´en teljes¨ ul, hogy δ(q, R) 6= ∅. ´ Altal´ anos´ıtott szekvenci´ alis automata ´ altal elfogadott sz´ o: Az A = hQ, T, δ, q0 , F i ´altal´a∗ nos´ıtott szekvenci´ alis automata elfogadja az u ∈ T sz´ot ⇔ ∃n ∈ N, u1 , . . . , un ∈ T ∗ , R1 , . . . Rn ∈ R(T ) ´es q1 , . . . , qn ∈ Q, melyre u = u1 · · · un , tov´abb´a minden 1 ≤ i ≤ n eset´en ui ∈ L(Ri ), qi ∈ δ(qi−1 , Ri ) ´es qn ∈ F . ´ Atmenetdiagrammos megad´ as eset´en: A elfogadja az u ∈ T ∗ sz´ot, ha van ir´any´ıtott u ´t1 q0 -b´ol valamely F -beli ´ allapotba, mely u ´t1 ment´en az ´elek c´ımk´eje az adott sorrendben R1 , . . . , Rn ´es u ∈ L(R1 R2 · · · Rn ). ´ Altal´ anos´ıtott szekvenci´ alis automata ´ altal felismert nyelv: L(A) = {u ∈ T ∗ | A elfogadja u-t}.
*
Minim´ alis automata: Valamely L ∈ L3 -hoz adott minim´alis ´allapotsz´am´ u v´eges, determinisztikus automat´ at L minim´ alis automat´aj´anak nevezz¨ uk.
*
¨ Osszef¨ ugg˝ o automata: Egy A = hQ, T, δ, q0 , F i v´eges, determinisztikus automata ¨osszef¨ ugg˝o, ha minden q ∈ Q eset´en l´etezik u ∈ T ∗ sz´o, hogy δ(q0 , u) = a.
*
Automata ´ allapotra vonatkoz´ o marad´ eknyelve: Legyen A = hQ, T, δ, q0 , F i egy v´eges determinisztikus automata. Az A automata q ∈ Q-ra vonatkoz´o marad´eknyelve L(A, q) := {v ∈ T ∗ | δ(q, v) ∈ F }.
*
Automata ekvivalens ´ allapotai: Legyen A = hQ, T, δ, q0 , F i egy v´eges determinisztikus au 0 tomata. q ∼ q ⇔ L(A, q)=L(A, q 0 ) ⇔ ∀u ∈ T ∗ : (δ(q, u)∈F ⇔ δ(q 0 , u)∈F ) . Automat´ ak ekvivalens ´ allapotai: Legyenek A = hQ, T, δ, q0 , F i ´es A0 = hQ0 , T, δ, q00 , F 0 i v´eges determinisztikus automat´ ak. q ∼ q 0 ⇔ L(A, q)=L(A0 , q 0 ) (q ∈ A, q 0 ∈ A0 ). Automat´ ak ekvivalenci´ aja: Legyenek A = hQ, T, δ, q0 , F i ´es A0 = hQ0 , T, δ, q00 , F 0 i v´eges determinisztikus automat´ ak. A ∼ A0 ⇔ q0 ∼ q00 .
*
Automata faktorautomat´ aja: Legyen A = hQ, T, δ, q0 , F i egy v´eges determinisztikus automata. A faktorautomat´ aja A/∼ := h{Cq }q∈Q , T, δ 0 , Cq0 , Fi, ahol • Cq az q-val ekvivalens ´ allapotok oszt´alya, melynek reprezent´ansa q, • F = {Cq q ∈ F }, • δ 0 (Cq , t) = Cδ(q,t) , azaz δ 0 -t egy tetsz˝oleges reprezent´anssal defini´aljuk.
*
Reduk´ alt automata: Egy adott A v´eges, determinisztikus automata reduk´alt automata, ha minden q, q 0 ∈ A eset´en q ∼ q 0 ⇔ q = q 0 , azaz nincsenek k¨ ul¨onb¨oz˝o ekvivalens ´allapotai.
8
*
Automata i-ekvivalens ´ allapotai: Legyen A = hQ, T, δ, q0 , F i egy v´eges determinisztikus aui tomata. Azt mondjuk, hogy q ∼ q 0 (q i-ekvivalens q 0 -vel), ha minden u ∈ T ≤i eset´en δ(q, u) ∈ F ⇔ δ(q 0 , u) ∈ F (i ≥ 0). (i)
Automat´ ak izomorfi´ aja: Legyenek Ai = hQi , T, δi , q0 , Fi i (i = 1, 2) v´eges, determinisztikus automat´ ak. Ekkor A1 ´es A2 izomorfak, ha l´etezik ϕ : Q1 → Q2 k¨olcs¨on¨osen egy´ertelm˝ u r´ ak´epez´es, melyre a k¨ ovetkez˝ ok teljes¨ ulnek: (1) (2) • ϕ(q0 ) = q0 , • ϕ(F1 ) = F2 , • δ-t meg˝ orzi, azaz minden q1 ∈ Q1 ´es minden t ∈ T eset´en ϕ(δ1 (q1 , t)) = δ2 (ϕ(q1 ), t).
(i) Direkt szorzat automata: Legyenek Ai = Qi , T, δi , q0 , Fi , v´eges, determinisztikus automa(1) (2) t´ ak, i = 1, 2. Az A1 × A2 = hQ1 × Q2 , T, δ1 × δ2 , (q0 , q0 ), F× i automat´at direkt szorzat automat´ anak h´ıvjuk. A1 × A2 m˝ uk¨od´ese komponensenk´ent p´arhuzamosan t¨ort´enik, amit a δ1 × δ2 jel¨ ol´essel fejez¨ unk ki. Form´alisan: (δ1 × δ2 ) (q1 , q2 ), t = δ1 (q1 , t), δ2 (q2 , t) . A v´eg´ allapotok halmaza feladatonk´ent v´altozhat. P´eld´ aul legyen a ∩, \, 4 m˝ uveletek k¨oz¨ ul az egyik. Feladat: konstru´alni egy A automat´at, melyre fenn´ all, hogy L(A ) = L(A1 ) L(A2 ). Ekkor • F∩ := F1 × F2 , • F\ := F1 × (Q2 \ F2 ), • F4 := F1 × (Q2 \ F2 ) ∪ (Q1 \ F1 ) × F2 . Knuth-Morris-Pratt (KMP) automata: Legyen m ∈ T ∗ egy sz´o. Az m = m1 m2 · · · m`(m) mint´ ahoz tartoz´ o Am Knuth-Morris-Pratt automata (vagy r¨oviden KMP automata) a k¨ovetkez˝ o. Am = h{qi }0≤i≤`(m) , T, δ m , q0 , {q`(m) }i, ahol `(m) i = `(m) δ m (qi , x) = qj ⇐⇒ j = . max{`(w) | w ∈ Pre(m) ∩ Suf(m1 · · · mi x)} i < `(m) *
Nyelv sz´ ora vonatkoz´ o marad´ eknyelve: Egy L nyelv p ∈ T (L)∗ -ra vonatkoz´o marad´eknyelve Lp := {v ∈ T (L)∗ pv ∈ L}.
¨ Osszes levezet´ esek gr´ afja: Legyen G = T, N, P = {p1 → q1 , . . . , pn → qn }, S tetsz˝oleges nyelvtan. G ¨ osszes levezet´eseinek gr´afja olyan v´egtelen, ir´any´ıtott gr´af, melynek ponjtai ∗ (T ∪ N ) elemeinek felelnek meg. α-b´ol β-ba van i, j c´ımk´ej˝ u (i ≥ 1, j ≥ 1) ´el, ha α → β ´es G
*
α = γ1 pj γ2 , β = γ1 qj γ2 , i = `(γ1 ) + 1.
Szintaxisfa: Legyen G = T, N, P, S tetsz˝oleges 2-es t´ıpus´ u nyelvtan. A t nem¨ ures f´at G feletti szintaxisf´ anak nevezz¨ uk, ha megfelel a k¨ovetkez˝o tulajdons´agoknak: • pontjai T ∪ N ∪ {ε} elemeivel vannak c´ımk´ezve. • bels˝ o pontjai N elemeivel vannak c´ımk´ezve. • ha egy bels˝ o pont c´ımk´eje X, a k¨ozvetlen lesz´armazottjainak c´ımk´ei pedig balr´ol jobbra olvasva X1 , X2 , . . . , Xk , akkor X → X1 X2 . . . Xk ∈ P. • az ε-nal c´ımk´ezett pontoknak nincs testv´ere. Legbal levezet´ es: A legbal levezet´es olyan levezet´es, hogy ha a levezet´es folyam´an a mondatforma i. bet˝ uj´en helyettes´ıt´es t¨ ort´enik, akkor a kor´abbi poz´ıci´okat (1., . . . , i−1.) a levezet´es m´ar a tov´ abbi l´ep´esekben nem ´erinti, azok v´altozatlanul maradnak. 1 Itt
az u ´t egy ponton t¨ obbsz¨ or is ´ athaladhat. Ez val´ oj´ aban a gr´ afelm´ eleti s´ eta fogalomnak felel meg.
9
Legjobb levezet´ es: A legjobb levezet´es olyan levezet´es, hogy ha a levezet´es folyam´an a mondatforma h´ atulr´ ol i. bet˝ uj´en helyettes´ıt´es t¨ort´enik, akkor a k´es˝obbi poz´ıci´okat (h´atulr´ol 1., . . . , i−1.) a levezet´es m´ ar a tov´abbi l´ep´esekben nem ´erinti, azok v´altozatlanul maradnak. Legbal mondatforma: Valamely L(G)-beli sz´o legbal levezet´ese sor´an el˝ofordul´o mondatforma. Legjobb mondatforma: Valamely L(G)-beli sz´o legjobb levezet´ese sor´an el˝ofordul´o mondatforma. Egy´ ertelm˝ u nyelvtan: G ∈ G2 egy´ertelm˝ u nyelvtan, ha minden u ∈ L(G)-nek pontosan egy szintaxisf´ aja l´etezik. Egy´ ertelm˝ u nyelv: L´etezik 2. t´ıpus´ u egy´ertelm˝ u nyelvtan, ami gener´alja.
*
L´ enyegesen nem egy´ ertelm˝ u nyelv: Nem l´etezik 2. t´ıpus´ u egy´ertelm˝ u nyelvtan, ami gener´alja.
Szintaktikus elemz´ esek alapfeladata: Legyen adva egy G = T, N, P, S ∈ G2 m´asodik t´ıpus´ u ∗ nyelvtan ´es egy u ∈ T sz´ o. Az elemz´esi algoritmusok feladata azt eld¨onteni, hogy u sz´o eleme-e L(G)-nek ´es ha igen, akkor fel´ep´ıteni u egy G feletti szintaxisf´aj´at.
*
Fel¨ ulr˝ ol lefel´ e elemz´ es: A szintaxisf´ at a gy¨ok´ert˝ol, azaz a kezd˝oszimb´olumt´ol pr´ob´alja fel´ep´ıteni.
*
Alulr´ ol felfel´ e elemz´ es: A szintaxisf´ at a levelekt˝ol, azaz az elemzend˝o sz´ot´ol pr´ob´alja fel´ep´ıteni. LL(k)nyelvtan: A G 2-es t´ıpus´ u nyelvtan LL(k) nyelvtan, ha tetsz˝oleges ∗
∗
∗
G
G,lb
∗
S −→ vAα1 −→ vγ1 α1 → vw1 ´es S −→ vAα2 −→ vγ2 α2 → vw2 levezet´esek eset´en abb´ol, G,lb
G,lb
G
G,lb
hogy pre(w1 , k)=pre(w2 , k) k¨ ovetkezik, hogy γ1 = γ2 . Ny´ el: Alulr´ ol felfel´e elemz´es eset´en az olyan visszahelyettes´ıthet˝o r´eszre, mely egy legjobb mondatforma valamely legjobb levezet´es´enek utols´o l´ep´es´eben ´all el˝o, a ny´el elnevez´est haszn´aljuk. LR(k) nyelvtan: A G 2-es t´ıpus´ u nyelvtan LR(k) nyelvtan, ha tetsz˝oleges ∗
∗
S −→ α1 Av1 −→ α1 γ1 v1 → w1 v1 ´es S −→ α2 Bv2 −→ α2 γ2 v2 → w2 v2 legjobb levezet´esek G,lj
G,lj
G
G,lj
G,lj
G
eset´en abb´ ol, hogy α1 γ1 pre(v1 , k) ´es α2 γ2 pre(v2 , k) valamelyike kezd˝oszelete a m´asiknak, k¨ ovetkezik, hogy α1 = α2 , A = B ´es γ1 = γ2 .
10
T´ etelek * *
T´ etel: Nem minden nyelv ´ırhat´ o le nyelvtannal. (Church-t´ezis) Minden valamilyen konstrukt´ıv m´odon megadhat´o nyelv le´ırhat´o nyelvtannal.
*
T´ etel: (Megszor´ıt´ asi t´etel) Lmegszi = Li (i = 1, 2, 3).
*
T´ etel: (Norm´ alforma t´etel) Lnfi = Li (i = 0, 1, 2, 3). i = 1 eset´en Kuroda norm´ alforma t´etel, i = 2 eset´en Chomsky norm´alforma t´etel a neve.
*
T´ etel: (Greibach NF t´etel) Minden G ∈ G2 nyelvtanhoz l´etezik G0 Greibach norm´alform´aj´ u nyelv0 tan, melyre G ∼ G.
*
T´ etel: (Z´ arts´ agi t´etel) Az Li (i = 0, 1, 2, 3) nyelvoszt´alyok z´artak az uni´o, konkaten´aci´o ´es a lez´ ar´ as m˝ uveletekre.
*
T´ etel: L0 ⊆ LRekFel , L0 ⊆ LParcRek , L1 ⊆ LRek ,
*
T´ etel: LVDA = LPDA = LNDA = LεNDA (= L0V ) = L3 T´ etel: Legyen A egy v´eges, determinisztikus automata, ekkor A/∼ reduk´alt ´es L(A/∼ ) = L(A). T´ etel: (Izomorfia t´etel) Legyenek A1 ´es A2 ¨osszef¨ ugg˝o, reduk´alt ´es egym´assal ekvivalens au∼ A2 . tomat´ ak. Ekkor A1 =
*
T´ etel: (Kleene t´etel) LREG = L3 .
*
T´ etel: Az L3 nyelvoszt´ aly z´ art a komplementer, a metszet, a k¨ ul¨onbs´eg ´es a szimmetrikus differencia m˝ uveletekre.
*
T´ etel: (Chomsky nyelvhierarchia) L0 ⊃ L1 ⊃ L2 ⊃ L3 . T´ etel: (Myhill-Nerode t´etel) L ∈ L3 akkor ´es csak akkor, ha {Lp }p∈T ∗ < ∞, ahol T = T (L) az L nyelv ´ ab´ec´eje.
*
T´ etel: (Kis Bar-Hillel lemma) Minden L ∈ L3 nyelvhez van olyan n = n(L) ∈ N nyelvf¨ ugg˝o konstans, hogy minden u ∈ L, `(u) ≥ n sz´o eset´en van u-nak olyan u = xyz felbont´asa (x, y, z ∈ T (L)∗ ), melyre • `(xy) ≤ n, • `(y) > 0, • minden i ≥ 0 eg´esz eset´en xy i z ∈ L.
*
T´ etel: (Nagy Bar-Hillel-lemma) Minden L ∈ L2 nyelvhez vannak olyan p = p(L), q = q(L) ∈ N nyelvf¨ ugg˝ o konstansok , hogy minden u ∈ L, `(u) ≥ p sz´o eset´en van u-nak olyan u = xyzvw felbont´ asa (x, y, z, v, w ∈ T (L)∗ ), melyre • `(yzv) ≤ q, • `(yv) > 0, • minden i ≥ 0 eg´esz eset´en xy i zv i w ∈ L.
*
T´ etel: A determinisztikus veremautomat´ak ´altal elfogadott nyelvek oszt´alya val´odi r´eszhalmaza a veremautomat´ ak ´ altal elfogadott nyelvek oszt´aly´anak.
*
T´ etel: A v´eg´ allapottal ´es az u ¨res veremmel elfogad´o veremautomat´ak ´altal elfogadhat´o nyelvek nyelvoszt´ alya megegyezik. 11
*
T´ etel: L1V = L2 .
*
T´ etel: LnV = L0 , (n ≥ 2).
*
Lemma: Tetsz˝ oleges G ∈ G2 nyelvtan, Z ∈ T ∪ N ∪ {ε} ´es α ∈ (T ∪ N )∗ eset´en Z → α akkor ´es
∗
G
csak akkor, ha l´etezik t G feletti szintaxisfa, melyre gy(t) = Z ´es front(t) = α. T´ etel: (Lin´ aris nyelvi egyenletek megold´ ok´eplete) Ha R1 ´es R2 regul´aris kifejez´esek ´es ε 6∈ L(R1 ), akkor az R1 X ∪ R2 = X egyenlet egy´ertelm˝ u megold´asa X = R1∗ R2 . T´ etel: (Line´ aris nyelvi egyenletrendszerek megoldhat´ aga) Legyen Mx ∪ v = egyen x nyelvi os´ L1 L11 · · · L1n . . . . . .. .. letrendszer, ahol az M = .. nyelvm´atrix ´es a v = . nyelvvekLn Ln1 · · · Lnn X1 n S n . S . {Ljk } ∪ tor adottak ´es x = . ismeretlen nyelvekb˝ol ´all´o vektor. Ha L = j=1 k=1 Xn n S {Lj } ⊆ Li (i ∈ {0, 1, 2, 3}) ´es ε 6∈ Ljk (1 ≤ j ≤ n, 1 ≤ k ≤ n), akkor az egyenletrendj=1
szernek egy´ertelm˝ uen l´etezik megold´asa, melynek elemei L elemeib˝ol regul´aris m˝ uveletekkel megkaphat´ ok.
T´ etel: LLL(k) ⊂ LLR(k) = L1DV .
12
Algoritmusok ´ Altermin´ alisok bevezet´ ese (ΦAlt ´ )
Input: G = T, N, P, S nyelvtan. Output: G0 nyelvtan, melynek csak A → a (A ∈ N, a ∈ T ) s´em´aj´ u szab´alyai tartalmaznak termin´ alist ´es G0 ∼ G. Minden t ∈ T termin´ alisra t valamennyi el˝ofordul´as´at P-beli szab´alyokban egy u ´j (nem N -beli), termin´ alisonk´ent egyedi Qt nyelvtani jelre cser´elj¨ uk. Minden t ∈ T termin´ alisra hozz´ aadjuk a szab´alyrendszerhez a Qt → t szab´alyt.
0. t´ıpus´ u ε-mentes´ıt´ es (Φ0epsz )
Input: G = T, N, P, S nyelvtan. Output: G0 epszilonmentes nyelvtan, melyre G0 ∼ G. kv
Minden Z ∈ T ∪ N ´es p → ε ∈ P (p ∈ (T ∪ N )∗ N (T ∪ N )∗ ) eset´en hozz´aadjuk a szab´alyrendszerhez a Zp → Z ´es pZ → Z szab´ alyokat, majd az epszilonszab´alyokat elhagyjuk.
2. t´ıpus´ u ε-mentes´ıt´ es (Φ2epsz )
Input: G = T, N, P, S 2. t´ıpus´ u nyelvtan. 0 Output: G megszor´ıtott 2. t´ıpus´ u nyelvtan, melyre G ∼ G0 . ∗ Az els˝ o l´ep´esben meghat´ arozzuk a H := {A ∈ N A → ε} halmazt. Ehhez rekurz´ıvan defini´aljuk G
a Hi (i ≥ 1) halmazokat: H1 := {A ∈ N A → ε ∈ P}, Hi+1 := Hi ∪ {A ∈ N ∃A → Q ∈ P : Q ∈ Hi∗ }. H1 ⊆ H2 ⊆ · · · ⊆ Hi ⊆ . . . , ´es mivel a Hi halmaz elemsz´ama fel¨ ulr˝ol korl´atos ez´ert stabiliz´al´odik a sorozat, azaz egy i0 indext˝ ol kezd˝ od˝ oen biztosan azonosak lesznek ezek a halmazok, ez a Hi0 lesz a H halmaz. A m´ asodik l´ep´esben a H halmaz ismeret´eben ´atalak´ıtjuk a nyelvtant a kell˝o alak´ ura. S 6∈ H eset´en:
¯ S , ahol A → q¯ ∈ P ¯ akkor ´es csak akkor, ha q¯ 6= ε ∧ ∃A→ q ∈ P, hogy q¯-t q-b´ol G0 := T, N, P, n´eh´ any (esetleg nulla) H-beli jel elhagy´as´aval kapjuk. S ∈ H eset´en: ¯ P-hez vegy¨ uk hozz´ a m´eg az S 0 → S | ε szab´alyokat ´es S 0 legyen az u ´j kezd˝oszimb´olum. Megjegyz´es: Φ2epsz meg˝ orzi a 2. ´es 3. t´ıpust.
L´ ancmentes´ıt´ es (ΦL´anc )
Input: G = T, N, P, S 1. t´ıpus´ u nyelvtan. 0 Output: G 1-es t´ıpus´ u l´ ancszab´ alymentes nyelvtan, melyre G0 ∼ G. ∗ Az els˝ o l´ep´esben meghat´ arozzuk minden A ∈ N eset´en a H(A) := {B ∈ N A → B} halmazt. G
Ehhez rekurz´ıvan defini´ aljuk a Hi (A) (i ≥ 0) halmazokat: H0 (A) := {A}, Hi+1 (A) := Hi (A) ∪ {B ∃C ∈ Hi (A) ∧ C → B}. G
H0 (A) ⊆ H1 (A) ⊆ · · · ⊆ Hi (A) ⊆ . . . , ´es mivel a Hi (A) halmaz elemsz´ama fel¨ ulr˝ol korl´atos ez´ert stabiliz´ al´ odik a sorozat, azaz egy i0 indext˝ol kezd˝od˝oen biztosan azonosak lesznek ezek a halmazok, ez a Hi0 (A) lesz a H(A) halmaz.
13
A m´ asodik l´ep´esben a H(A) halmazok (A ∈ N ) ismeret´eben ´atalak´ıtjuk a nyelvtant a kell˝o alak´ ura:
0 0 G = T, N, P , S lesz az u ´j nyelvtan, ahol P0 = {u1 A1 u2 A2 · · · un An un+1 → β u1 , . . . , un+1 ∈ T ∗ ∧ A1 , . . . , An ∈ N ∧ β ∈ (T ∪ N )∗ ∧ ∃B1 ∈ H(A1 ), . . . , Bn ∈ H(An ) : u1 B1 u2 B2 · · · un Bn un+1 → β ∈ P}. Megjegyz´esek: 1. ΦL´anc meg˝ orzi az 1., 2., ´es 3. t´ıpust. 2. ΦL´anc alkalmazhat´o nem felt´etlen ε-mentes 3. t´ıpus´ u nyelvtanokra is. Ilyenkor is G0 ∼ G ´es ΦL´anc meg˝orzi a 3. t´ıpust.
Hosszredukci´ o (ΦHossz )
Input: G = T, N, P, S 1-es t´ıpus´ u nyelvtan. 0 Output: G 1-es t´ıpus´ u nyelvtan olyan szab´alyokkal, melyeknek baloldala ´es jobboldala legfeljebb 2 hossz´ us´ ag´ u, tov´ abb´ a G0 ∼ G. Legyen X1 X2 . . . Xm → Y1 Y2 . . . Yn (m ≥ 2, n ≥ m) hossz´ us´agot nem cs¨okkent˝o szab´aly. (X1 , X2 , . . . Xm , Y1 , Y2 . . . Yn ∈ N ) A szab´ aly szimul´ aci´ oja a Z1 , Z2 , . . . , Zn−2 u ´j nyelvtani jelek bevezet´es´evel: X1 X2 → Y1 Z1 , Z1 X3 → Y2 Z2 , .. . Zm−3 Xm−1 → Ym−2 Zm−2 , Tov´ abb´ a ha n = m, akkor Zm−2 Xm → Ym−1 Ym , egy´ebk´ent (n > m eset´en): Zm−2 Xm → Ym−1 Zm−1 , Zm−1 → Ym Zm , .. . Zn−3 → Yn−2 Zn−2 , Zn−2 → Yn−1 Yn . m = 1 eset´en: X1 → Y1 Z1 , Z1 → Y2 Z2 , .. . Zn−3 → Yn−2 Zn−2 , Zn−2 → Yn−1 Yn . Megjegyz´esek: 1. A fenti algoritmust 3. t´ıpus´ u G nyelvtan eset´en is defini´aljuk. Ekkor m = 1 ´es Y1 , . . . , Yn−1 ∈ T , Yn ∈ N ∪ {ε}. Ebben az esetben az algoritmus outputja egy olyan G0 nyelvtan, melynek p0 → q 0 szab´ alyaira q 0 ∈ T N ∪ T ∪ N ∪ {ε}. 2. ΦHossz meg˝orzi az 1., 2., ´es az 1. megjegyz´essel defini´ alt algoritmus eset´en a 3. t´ıpust tov´abb´a a l´ancmentess´eget ´es az epszilonmentess´eget.
1-es t´ıpus´ u nyelvtanok norm´ alform´ ara hoz´ asa (Φ1NF ) Kuroda norm´ alforma Input: G 1-es t´ıpus´ u nyelvtan. 0 Output: G Kuroda norm´ alform´ aj´ u nyelvtan, melyre G0 ∼ G. L´ep´esei: ´ 1. Altermin´ alisok bevezet´ese
14
2. L´ ancmentes´ıt´es 3. Hosszredukci´ o 4. Az AB → CD (A 6= C, B 6= D) s´em´aj´ u szab´alyok elimin´al´asa (Az AB → CD (A 6= C, B 6= D) s´em´ aj´ u szab´alyokat az AB → AW , AW → CW , CW → CD szab´ alyokkal helyettes´ıtj¨ uk, ahol W u ´j, egyedi nyelvtani jel.)
Zs´ akutcamentes´ıt´ es (ΦZs´ak ) Input: G 2. t´ıpus´ u nyelvtan. Output: G0 zs´ akutcamentes 2. t´ıpus´ u nyelvtan, melyre G0 ∼ G. ∗ Az els˝ o l´ep´esben meghat´ arozzuk a J := {A ∈ N ∃u ∈ T ∗ , A → u} halmazt. Ehhez rekurz´ıvan G
defini´ aljuk a Ji (i ≥ 1) halmazokat: J1 := {A ∈ N ∃u ∈ T ∗ , A → u ∈ P}, Ji+1 := Ji ∪ {A ∈ N ∃A → Q ∈ P : Q ∈ (Ji ∪ T )∗ }. J1 ⊆ J2 ⊆ · · · ⊆ Ji ⊆ . . . , ´es mivel a Ji halmaz elemsz´ama fel¨ ulr˝ol korl´atos ez´ert stabiliz´al´odik a sorozat, azaz egy i0 indext˝ ol kezd˝ od˝ oen biztosan azonosak lesznek ezek a halmazok, ez a Ji0 lesz a J halmaz. Ezek ut´ an a G nyelvtant u ´gy alak´ıtjuk ´at, hogy elhagyunk minden olyan szab´alyt, mely tartalmaz (N \ J)-beli nyelvtani jelt.
¨ Osszef¨ ugg˝ ov´ e alak´ıt´ as (ΦOf ¨ ) Input: G 2. t´ıpus´ u nyelvtan. 0 Output: G ¨ osszef¨ ugg˝ o 2. t´ıpus´ u nyelvtan, melyre G0 ∼ G. ∗ Az els˝ o l´ep´esben meghat´ arozzuk a K := {A ∈ N ∃α ∈ (T ∪ N )∗ A(T ∪ N )∗ , S → α} halmazt. G
Ehhez rekurz´ıvan defini´ aljuk a Ki (i ≥ 0) halmazokat: K0 := {S}; K1 := K0 ∪ {A ∈ N ∃α ∈ (T ∪ N )∗ A(T ∪ N )∗ , S → α ∈ P}, Ki+1 := Ki ∪ {A ∈ N ∃B ∈ Ki , α ∈ (T ∪ N )∗ A(T ∪ N )∗ , B → α ∈ P}. K1 ⊆ K2 ⊆ · · · ⊆ Ki ⊆ . . . , ´es mivel a Ki halmaz elemsz´ama fel¨ ulr˝ol korl´atos ez´ert stabiliz´al´odik a sorozat, azaz egy i0 indext˝ ol kezd˝ od˝ oen biztosan azonosak lesznek ezek a halmazok, ez a Ki0 lesz a K halmaz. Ezek ut´ an a G nyelvtant u ´gy alak´ıtjuk ´at, hogy elhagyunk minden olyan szab´alyt, melynek baloldala (N \ K)-beli.
2-es t´ıpus´ u nyelvtanok redukci´ oja (ΦRed ) Input: G 2-es t´ıpus´ u nyelvtan. Output: G0 reduk´ alt (zs´ akutcamentes ´es ¨osszef¨ ugg˝o) 2-es t´ıpus´ u nyelvtan, melyre G0 ∼ G. L´ep´esei: 1. Zs´ akutcamentes´ıt´es ¨ 2. Osszef¨ ugg˝ ov´e t´etel.
2-es t´ıpus´ u nyelvtanok norm´ alform´ ara hoz´ asa (Φ2NF ) Chomsky norm´ alforma Input: G 2-es t´ıpus´ u nyelvtan. 0 Output: G Chomsky norm´ alform´ aj´ u nyelvtan, melyre G0 ∼ G. L´ep´esei: 15
1. 2. 3. 4.
´ Altermin´ alisok bevezet´ese ε-mentes´ıt´es L´ ancmentes´ıt´es Hosszredukci´ o
3-as t´ıpus´ u nyelvtanok norm´ alform´ ara hoz´ asa (Φ3NF ) Input: G 3-as t´ıpus´ u nyelvtan. 0 Output: G 3-as t´ıpus´ u norm´ alform´ aj´ u nyelvtan, melyre G0 ∼ G. L´ep´esei: 1. L´ ancmentes´ıt´es 2. Hosszredukci´ o 3. Az A → a s´em´ aj´ u szab´ alyok elimin´al´asa (Minden A → a s´em´ aj´ u szab´ alyt az A → aF szab´allyal helyettes´ıt¨ unk, ahol F u ´j, egyedi nyelvtani jel, ´es hozz´ aadjuk m´eg a szab´ alyrendszerhez az F → ε szab´alyt.)
Polinomi´ alis algoritmus a sz´ oprobl´ ema eld¨ ont´ es´ ere 2. t´ıpus eset´ en Cocke-Younger-Kasami (CYK) algoritmus Input: G = hT, N, P, Si Chomsky norm´alform´aj´ u nyelvtan ´es egy u = t1 · · · tn ∈ T ∗ sz´o. Output: IGEN, ha u ∈ L(G). NEM, ha u 6∈ L(G). Ha u = ε, akkor u ∈ L(G) ⇐⇒ S → ε ∈ P. Legyen Ai a Pi ∈ P szab´ aly bal-, qi pedig a jobboldala. (Ai ∈ N , qi ∈ T ∪ N 2 .) A CYK algoritmus rekurz´ıven defini´ al Hi,j , 1 ≤ i ≤ j ≤ n halmazokat (j−i) szerint n¨ovekv˝o sorrendben. Hi,i := {Ak | qk = ti }, j−1 S Hi,j := {Ak | qk ∈ Hi,r Hr+1,j } (i < j). r=i
Ha S ∈ H1,n , akkor u ∈ L(G), k¨ ul¨ onben u 6∈ L(G).
Line´ aris algoritmus a sz´ oprobl´ ema eld¨ ont´ es´ ere 3. t´ıpus eset´ en Input: G = hT, N, P, Si 3. t´ıpus´ u norm´ alform´aj´ u nyelvtan ´es egy u = t1 · · · tn ∈ T ∗ sz´o. Output: IGEN, ha u ∈ L(G). NEM ha u 6∈ L(G). Az algoritmus rekurz´ıvan kisz´ amol egy a nyelvtani jelek halmaz´anak r´eszhalmazaib´ol ´all´o sorozatot. H0 = {S}, Hi+1 = {A ∈ N | ∃B ∈ Hi ∧ B → ti+1 A ∈ P}. Legyen tov´ abb´ a F = {A ∈ N | A → ε ∈ P}. u ∈ L(G) ⇔ Hn ∩ F 6= ∅.
Minim´ alis automata el˝ o´ all´ıt´ asa Input: A = hQ, T, δ, q0 , F i v´eges, determinisztikus automata. Output: L(A) minim´ alis automat´ aja. L´ep´esei: ¨ 1. Osszef¨ ugg˝ ov´e alak´ıt´ as Meghat´ arozzuk a q0 -b´ ol el´erhet˝ o´ allapotok H halmaz´at. H0 := {q0 },
16
Hi+1 := Hi ∪ {q ∃ q 0 ∈ Hi ∧ ∃ t ∈ T : δ(q 0 , t) = q}, H0 ⊆ H1 ⊆ · · · ⊆ Hi ⊆ . . . , ´es mivel a Hi halmaz elemsz´ama fel¨ ulr˝ol korl´atos ez´ert stabiliz´al´odik a sorozat, azaz egy i0 indext˝ ol kezd˝ od˝ oen biztosan azonosak lesznek ezek a halmazok, ez a Hi0 lesz a H halmaz. Az ¨ osszef¨ ugg˝ o automata: A¨ossz = hH, T, δ H×T , q0 , F ∩ Hi. 2. Redukci´ o 0 1 Rekurz´ıvan meghat´ arozzuk az A¨ossz automata ∼, ∼, . . . ekvivalenci´ait: 0 0 • q ∼ q , ha (q ∈ F ⇔ q 0 ∈ F ), i+1 i i • q ∼ q 0 ⇔ q ∼ q 0 ∧ (∀t ∈ T : δ(q, t) ∼ δ(q 0 , t)). 0 1 2 ∼≺∼≺∼≺ · · · ≺∼, (%1 ≺ %2 , ha minden q, q 0 ∈ Q eset´en q%2 q 0 ⇒ q%1 q 0 .) i ´ıgy az ∼ az ´ allapotok halmaz´ anak egyre finomod´o feloszt´as´at adja, mely v´eges sok l´ep´esben stabii i+1 liz´ al´ odik. i0 := min{i | ∼= ∼ }. A¨ossz /i0 a minim´ alis automata. ∼
NDA-hoz vele ekvivalens VDA k´ esz´ıt´ ese Input: A = hQ, T, δ, q0 , F i v´eges, nemdeterminisztikus automata. Output: A0 = hQ0 , T, δ 0 , q00 , F 0 i v´eges, determinisztikus automata, melyre L(A0 ) = L(A). Q0 := 2Q , s S δ 0 ({q1 , . . . qs }, t) := δ(qi , t) (q1 , . . . , qs ∈ Q, t ∈ T ). i=1
q00 := {q0 } F 0 := {A ∈ 2Q | A ∩ F 6= ∅}. A q00 -t tartalmaz´ o A0¨ossz komponens meghat´aroz´asa: Amikor az ´ allapotokra sorra hat´ arozzuk meg az ´allapot´atmeneteket k´esz´ıt¨ unk egy sort δ 0 ´ert´ekk´eszlet´er˝ ol. Minden l´ep´esben a sor elej´en lev˝ o, m´eg nem vizsg´alt ´allapotra meghat´arozzuk az ´atmeneteket. Az elj´ ar´ as akkor ´er v´eget, ha a sor ki¨ ur¨ ul. Kezdetben a sor egyed¨ ul q00 -t tartalmazza.
3-as norm´ alform´ aj´ u nyelvtan k´ esz´ıt´ ese VDA-hoz Input: A = hQ, T, δ, q0 , F i v´eges, determinisztikus automata. Output: G = hT, N, P, Si 3-as t´ıpus´ u norm´alform´aj´ u nyelvtan, melyre L(G) = L(A). N := Q, S := q0 , q1 → tq2 ∈ P ⇔ δ(q1 .t) = q2 (q1 , q2 ∈ Q, t ∈ T ), q→ε∈P ⇔ q∈F (q ∈ Q).
VDA k´ esz´ıt´ ese 3-as norm´ alform´ aj´ u nyelvtanhoz Input: G = hT, N, P, Si 3-as norm´ alform´aj´ u nyelvtan. Output: A = hQ, T, δ, q0 , F i v´eges, determinisztikus automata, melyre L(A) = L(G). L´ep´esei: 1. NDA k´esz´ıt´ese 3NF nyelvtanhoz. Q := N , q0 := S, B ∈ δ(A, t) ⇔ A → tB ∈ P (A, B ∈ N, t ∈ T ), A∈F ⇔ A→ε∈P (A ∈ N ). 2. NDA-hoz vele ekvivalens VDA k´esz´ıt´ese. 17
εNDA-hoz vele ekvivalens NDA k´ esz´ıt´ ese Input: A = hQ, T, δ, q0 , F i εNDA. Output: A0 = hQ0 , T, δ 0 , q00 , F 0 i NDA, melyre L(A0 ) = L(A). Q0 := Q, q00 := q0 . Egy q ∈ Q ´ allapot ε-lez´ artja azon ´ allapotokb´ol ´all, ahova q-b´ol ε-´atmenetekkel eljuthatunk. Halmazsorozattal t¨ ort´en˝ o rekurz´ıv megad´ asa: H0 (q) := {q}. S Hi+1 (q) := Hi ∪ q0 ∈Hi (q) δ(q 0 , ε). H0 (q) ⊆ H1 (q) ⊆ · · · ⊆ Q. A Hi (q) halmazsorozat legfeljebb |Q| l´ep´esben stabiz´al´odik, legyen i0 a legkisebb index, melyre Hi0 (q) = Hi0 +1 (q). Ekkor H(q) := Hi0 (q). q 0 ∈ δ 0 (q, t) ⇔ ∃ q 00 ∈ H(q), q 0 ∈ δ(q 00 , t). q ∈ F 0 ⇔ H(q) ∩ F 6= ∅.
Regul´ aris kifejez´ es ´ altal le´ırt nyelvet felismer˝ o VDA k´ esz´ıt´ ese (Automataszint´ ezis) Input: R regul´ aris kifejez´es. Output: A = hQ, T, δ, q0 , F i v´eges, determinisztikus automata, melyre L(A) = L(R). L´ep´esei: ´ 0. Altal´ anos´ıtott szekvenci´ alis automata k´esz´ıt´ese regul´aris kifejez´eshez. Adott R regul´ aris kifejez´eshez kiindulunk egy A = h{qS , qV }, T, δ, qS , {qV }i ´altal´anos´ıtott szekvenci´ alis automat´ ab´ ol, ahol δ(qS , R) = {qV } az egyetlen ´atmenet. Erre ny´ılv´an L(A) = L(R). R q q S
V
´ 1. Altal´ anos´ıtott szekvenci´ alis automata lebont´asa εNDA-v´a Az al´ abbi lebont´ asi l´ep´esek nem v´ altoztatj´ak az elfogadott nyelvet. R1 (R1 ∪ R2 ) q1 q2 q1 ⇒ R2
q1
(R1 R2 )
q2
⇒
q1
R1
q2
R2
qu´j
q2
R q1
R∗
q2
⇒
q1
ε
qu´j
ε
q2
Addig bontjuk a regul´ aris kifejez´eseket am´ıg εNDA-t nem kapunk. (Az ∅-zal c´ımk´ezett ´eleket elhagyjuk.) 2. εNDA-hoz vele ekvivalens NDA k´esz´ıt´ese 3. NDA-hoz vele ekvivalens VDA k´esz´ıt´ese
VDA ´ altal elfogadott nyelv le´ır´ asa regul´ aris kifejez´ essel (Automataanal´ızis) Input: A = hQ, T, δ, q0 , F i VDA. Output: R regul´ aris kifejez´es, melyre L(R) = L(A). 18
L´ep´esei: 1. Nyelvi egyenletrendszer fel´ır´ asa az ´allapotok marad´eknyelveire. S • Ha q 6∈ F , akkor a q marad´eknyelv´ere vonatkoz´o egyenlet: L(A, q) = t∈T tL(A, δ(q, t)). S • Ha q ∈ F , akkor a q marad´eknyelv´ere vonatkoz´o egyenlet: L(A, q) = ε ∪ t∈T tL(A, δ(q, t)). 2. Az egyenletrendszer Gauss-elimin´aci´oval t¨ort´en˝o megold´asa L(A, q0 )-ra. Legyen Q = {q0 , q1 . . . , qn−1 }. n egyenlet¨ unk van n ismeretlennel. A qn−1 ´allapot marad´eknyelv´ere vonatkoz´ o egyenletb˝ ol kifejezz¨ uk L(A, qn−1 )-t a t¨obbi marad´eknyelv f¨ uggv´eny´eben a line´aris nyelvi egyenlet megold´ ok´eplete seg´ıts´eg´evel. Ezt behelyettes´ıtj¨ uk a t¨obbi n − 1 egyenletbe, ´ıgy marad n − 1 egyenlet n − 1 ismeretlennel. Folytatjuk, am´ıg egy egyenlet¨ unk marad, melynek egyetlen ismeretlene L(A, q0 ). Az egyenletet a line´aris nyelvi egyenlet megold´ok´eplete alapj´an megoldjuk. Megjegyz´es: Az ¨ osszes t¨ obbi marad´eknyelvet visszahelyettes´ıt´essel kaphatjuk meg.
VDA el˝ o´ all´ıt´ asa marad´ eknyelvekb˝ ol Input: L nyelv. Output: Ha L ∈ L3 , akkor A VDA, melyre L(A) = L. Ha L 6∈ L3 , akkor NINCS. Hat´ arozzuk meg L szavakra vonatkoz´o marad´eknyelveit, ´es ha v´eges sok k¨ ul¨onb¨oz˝o van, akkor ∗ legyenek p1 , . . . , pn ∈ T (L) olyan szavak, melyre Lp1 , . . . , Lpn kiadja a marad´eknyelvek rendszer´et. Az Lpi t 1 ≤ i ≤ n, t ∈ T (L) maradnyelvekr˝ol meghat´arozzuk, mely pj -re egyezik meg az Lpj marad´eknyelvvel. Teh´ at a VDA: A = h{Lp }p∈T ∗ , T, δ, Lε , {Lp | ε ∈ Lp }i, ahol δ(Lp , t) = Lpt .
19
Jel¨ ol´ esek A ⊆ B; C ⊂ D 2H Df ε X∗ X+ Xi X ≤i X ≥i X(u); T (u) X(L); T (L) `(u) `t (u) `H (u) L∗ L+ u−1 ; L−1 Pre(u); Suf(u) Pre(L); Suf(L) Pre(u, i); Suf(u, i) pre(u, i); suf(u, i) u⊆v R(X) R RAlt ´ (X) L(R) α→β G k
A r´eszhalmaza B-nek; C val´odi r´eszhalmaza D-nek H hatv´ anyhalmaza az f f¨ uggv´eny ´ertelmez´esi tartom´anya u ¨res sz´ o az ¨ osszes X feletti sz´o halmaza ∗ X \ {ε}, az ¨ osszes X feletti pozit´ıv hossz´ us´ag´ u sz´o halmaza az ¨ osszes X feletti i hossz´ us´ag´ u sz´o halmaza az ¨ osszes X feletti legfeljebb i hossz´ us´ag´ u sz´o halmaza az ¨ osszes X feletti legal´abb i hossz´ us´ag´ u sz´o halmaza a legsz˝ ukebb ´ ab´ec´e, mely f¨ol¨ott u sz´o a legsz˝ ukebb ´ ab´ec´e, mely felett L nyelv az u sz´ o hossza az u sz´ oban szerepl˝o t bet˝ uk sz´ama az u sz´ oban szerepl˝o H-beli bet˝ uk sz´ama L lez´ artja L pozit´ıv lez´ artja u illetve L megford´ıt´asa u prefix- illetve suffixhalmaza L prefix- illetve suffixhalmaza az u sz´ o legfeljebb i hossz´ us´ag´ u prefix- illetve suffixhalmaza az u sz´ o i hossz´ us´ag´ u prefixe illetve suffixe u r´eszszava v-nek X ´ ab´ec´e feletti regul´aris kifejez´esek halmaza az ¨ osszes regul´aris kifejez´es halmaza X ´ ab´ec´e feletti ´altal´anos´ıtott regul´aris kifejez´esek halmaza az R regul´ aris kifejez´es ´altal reprezent´alt nyelv α-b´ ol k¨ ozvetlen¨ ul levezethet˝o β
α→β
α-b´ ol k l´ep´esben levezethet˝o β
α→β
α-b´ ol k¨ ozvetetten levezethet˝o β
G ∗ G
L(G) Gi Gmegszi G1 ∼ G2 G1 ∼ G2 kv
Li Lmegszi Lnfi LRekFel LParcRek LRek LnV LεNDA
a G nyelvtan a´ltal gener´alt nyelv i. t´ıpus´ u nyelvtanok oszt´alya (i ∈ {0, 1, 2, 3}) megszor´ıtott i. t´ıpus´ u nyelvtanok oszt´alya (i ∈ {0, 1, 2, 3}) G1 ´es G2 nyelvtan ekvivalensek G1 ´es G2 nyelvtan kv´aziekvivalensek i. t´ıpus´ u nyelvek nyelvoszt´alya (i ∈ {0, 1, 2, 3}) megszor´ıtott i. t´ıpus´ u nyelvek nyelvoszt´alya (i ∈ {0, 1, 2, 3}) (l. megszor´ıt´ asi t´etel) i-es norm´ alform´aj´ u nyelvtanok ´altal gener´alt nyelvek nyelvoszt´alya (i ∈ {0, 1, 2, 3}) (l. norm´ alforma t´etel) a rekurz´ıve felsorolhat´o nyelvek nyelvoszt´alya a parci´ alisan rekurz´ıv nyelvek nyelvoszt´alya a rekurz´ıv nyelvek nyelvoszt´alya az n-vermek ´ altal elfogadott nyelvek nyelvoszt´alya az εNDA-k ´ altal elfogadott nyelvek nyelvoszt´alya
20
LNDA LPDA LVDA LREG ΦAlt ´ Φ0epsz Φ2epsz ΦL´anc ΦHossz Φ1NF ΦZs´ak ΦOssz ¨ ΦRed Φ2NF Φ3NF front(t) gy(t) α −→ β
az NDA-k ´ altal elfogadott nyelvek nyelvoszt´alya a PDA-k ´ altal elfogadott nyelvek nyelvoszt´alya a VDA-k ´ altal elfogadott nyelvek nyelvoszt´alya a regul´ aris nyelvek nyelvoszt´alya Az ´ altermin´ alisok bevezet´es´enek nyelvtani transzform´aci´oja A 0. t´ıpus´ u ε-mentes´ıt´es nyelvtani transzform´aci´oja A 2. t´ıpus´ u ε-mentes´ıt´es nyelvtani transzform´aci´oja A l´ ancmentes´ıt´es nyelvtani transzform´aci´oja A hosszredukci´o nyelvtani transzform´aci´oja Az 1. t´ıpus´ u (Kuroda) norm´alform´ara hoz´as nyelvtani transzform´aci´oja A zs´ akutcamentes´ıt´es nyelvtani transzform´aci´oja Az ¨ osszef¨ ugg˝ ov´e t´etel nyelvtani transzform´aci´oja A 2. t´ıpus´ u nyelvtanok redukci´oj´anak nyelvtani transzform´aci´oja A 2. t´ıpus´ u (Chomsky) norm´alform´ara hoz´as nyelvtani transzform´aci´oja A 3-as norm´ alform´ara hoz´as nyelvtani transzform´aci´oja a t szintaxisfa leveleinek balr´ol jobbra val´o ¨osszeolvas´asa a t szintaxisfa gy¨okere α-b´ ol legbal levezet´essel k¨ozvetlen¨ ul levezethet˝o β
α −→ β
α-b´ ol legbal levezet´essel k l´ep´esben levezethet˝o β
α −→ β
α-b´ ol legbal levezet´essel k¨ozvetetten levezethet˝o β
α −→ β
α-b´ ol legjobb levezet´essel k¨ozvetlen¨ ul levezethet˝o β
α −→ β
α-b´ ol legjobb levezet´essel k l´ep´esben levezethet˝o β
α −→ β
α-b´ ol legjobb levezet´essel k¨ozvetlen¨ ul k¨ozvetetten levezethet˝o β
LLL(k) LLR(k) L1DV
LL(k) nyelvtanok ´altal gener´alt nyelvek nyelvoszt´alya LR(k) nyelvtanok ´altal gener´alt nyelvek nyelvoszt´alya Determinisztikus 1-vermek ´altal elfogadott nyelvek nyelvoszt´alya
G,lb k
G,lb ∗ G,lb G,lj k G,lj ∗
G,lj
21
Konvencion´ alis szimb´ olumhaszn´ alatok X, Y, . . . t, x, y, z, a, b, c, . . . u, v, w, . . . ε L, L1 , . . . L, . . . R, R1 , . . . G, G1 , . . . G, . . . T N a, b, c, . . . A, B, C, . . . S α, β, γ, ξ, %, σ, τ, . . . A, A1 , . . . Q, A q, q1 , . . . a, a1 , . . . F δ V, V1 , . . . Σ, Σ1 , . . . σ, σ1 , . . . % Φ
´b´ec´ek a bet˝ uk szavak u ¨res sz´ o nyelvek nyelvoszt´ alyok regul´ aris kifejez´esek nyelvtanok nyelvtanoszt´ alyok termin´ alis ´ ab´ec´e nyelvtani jelek (nemtermin´alisok) ´ab´ec´eje termin´ alisok nemtermin´ alisok kezd˝ oszimb´ olum (csak akkor, ha nincs m´as k.sz. k¨ ul¨on megadva) mondatform´ ak v´eges determinisztikus vagy nemdeterminisztikus automat´ak automata ´ allapothalmaza automata ´ allapotai automata v´eg´ allapotainak halmaza automata ´ allapot´atmenet f¨ uggv´enye veremautomat´ak verem´ ab´ec´ek verem´ ab´ec´e elemei rel´ aci´ o nyelvtani transzform´aci´o
22
