Form´ alis Nyelvek - 1. El˝ oad´ as Csuhaj Varj´ u Erzs´ ebet Algoritmusok ´ es Alkalmaz´ asaik Tansz´ ek Informatikai Kar E¨ otv¨ os Lor´ and Tudom´ anyegyetem H-1117 Budapest P´ azm´ any P´ eter s´ et´ any 1/c E-mail:
[email protected]
1
A kurzus c´ elja, hogy megismerkedj¨ unk a form´ alis nyelvek ´ es automat´ ak elm´ elet´ enek, a sz´ am´ıt´ astudom´ any egyik trad´ıcion´ alis ´ ag´ anak alapjaival.
2
Irodalom:
1. Gy¨ orgy E. R´ ev´ esz, Introduction to Formal Languages, McGraw-Hill Book Company, 1983. Tov´ abbi irodalom: 2. A. Salomaa, Formal Languages, Acedemic Press, 1973. 3. K. Krithivasan, Rama, R., Introduction to Formal Languages, Automata Theory and Computation, Pearson, 2009. 4. J. E. Hopcroft, Rajeev Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Second Edition. Addison-Wesley (2001).
3
Magyar nyelv˝ u irodalom: 1. R´ ev´ esz Gy¨ orgy, Bevezet´ es a form´ alis nyelvek elm´ elet´ ebe, Tank¨ onyvkiad´ o, 1977. 2. F¨ ul¨ op Zolt´ an, Form´ alis nyelvek ´ es szintaktikus elemz´ es¨ uk, Polygon, Szeged, 2004.
4
Tudnival´ ok Az el˝ oad´ asok alapj´ aul az irodalomjegyz´ ek [1], [2] ´ es [3] eleme szolg´ al. Az el˝ oad´ asv´ azlatok (a slide-ok) minden l´ enyeges inform´ aci´ ot tartalmaznak ´ es kiz´ ar´ olag tanul´ asi c´ elokra haszn´ alhat´ ok. A kurzus vizsg´ aval z´ arul, a vizsga sor´ an az el˝ oad´ asokon elhangzott ´ es az el˝ oad´ asv´ azlatokon szerepl˝ o anyagot k´ erem sz´ amon. Az el˝ oad´ asokon tov´ abbi inform´ aci´ ok is elhangozhatnak, ezek kieg´ esz´ıt˝ o jelleg˝ uek. A vizsga el˝ ott h´ arom h´ ettel r´ eszletes inform´ aci´ ot adok a sz´ amonk´ er´ es alapj´ aul szolg´ al´ o anyagr´ ol ´ es a sz´ amonk´ er´ es m´ odj´ ar´ ol. 5
Az el˝ oad´ asok l´ atogat´ asa nem k¨ otelez˝ o, de aj´ anlott. A gyakorlatok l´ atogat´ asa k¨ otelez˝ o, a lehets´ eges hi´ anyz´ asok sz´ am´ at a gyakorlatvezet˝ ok ismertetni fogj´ ak a gyakorlatokon. A gyakorlati jegy megszerz´ es´ enek felt´ eteleit is a gyakorlatvezet˝ ok fogj´ ak meghat´ arozni ´ es ismertetni.
Az el˝ oad´ asv´ azlatokat .pdf file form´ aj´ aban az el˝ oad´ asok ut´ ani p´ enteken felteszem a honlapomra (http://people.inf.elte.hu/csuhaj), ´ es a pontos webc´ımet a Neptun rendszeren kereszt¨ ul k¨ oz¨ olni fogom. Minden szerd´ an de. 10-12 h k¨ oz¨ ott fogad´ o´ or´ am van a D´ eli t¨ omb 2.511-es hivatali szob´ amban, ahol az ´ erdekl˝ od˝ oket szeretettel v´ arom. Ugyancsak keressenek meg emailben (
[email protected]) vagy a fogad´ oo ´r´ an, ha b´ armilyen k´ erd´ es¨ uk felmer¨ ul a tant´ arggyal kapcsolatban. J´ o tanul´ ast k´ıv´ anok! Budapest, 2013. febru´ ar Csuhaj Varj´ u Erzs´ ebet 6
A kurzus tartalm´ anak r¨ ovid le´ır´ asa 1. Bevezet´ es, a form´ alis nyelv fogalma: alapvet˝ o fogalmak ´ es jel¨ ol´ esek,szavak, nyelvek, grammatik´ ak, a grammatik´ ak Chomsky-f´ ele hierarchi´ aja. 2. M˝ uveletek nyelveken: defin´ıci´ ok, nyelvoszt´ alyok z´ arts´ agi tulajdons´ agai. 3. K¨ ornyezetf¨ uggetlen grammatik´ ak ´ es nyelvek: reduk´ alt grammatik´ ak, a Chomsky norm´ alforma, levezet´ esi fa, line´ aris grammatik´ ak, regul´ aris grammatik´ ak, regul´ aris nyelvek, regul´ aris kifejez´ esek. A gener´ alt nyelvek ´ es nyelvoszt´ alyok tulajdons´ agai. 4. K¨ ornyezetf¨ ugg˝ o- ´ es mondatszerkezet˝ u grammatik´ ak: hossz-nemcs¨ okkent˝ o grammatik´ ak, Kuroda norm´ al forma, mondatszerkezet˝ u grammatik´ ak norm´ alform´ ai. A gener´ alt nyelvek ´ es nyelvoszt´ alyok tulajdons´ agai. Nyelvoszt´ alyok Chomskyf´ ele hierarchi´ aja.
7
A kurzus tartalm´ anak r¨ ovid le´ır´ asa - folytat´ as 1. Automat´ ak ´ es nyelvek: v´ eges automat´ ak, veremautomat´ ak, k´ etverm˝ u automata, line´ arisan korl´ atolt automata, Turing g´ ep. Az automat´ ak tulajdons´ agai, a felismert nyelvoszt´ alyok, az automat´ ak ´ es a grammatik´ ak kapcsolatai. 2. Szintaktikai elemz´ es: kapcsolat szintaxis ´ es szemantika k¨ oz¨ ott; k¨ ornyezetf¨ uggetlen grammatik´ ak ´ es nyelvek egy´ ertelm˝ us´ ege; LL(k) ´ es LR(k) grammatik´ ak.
8
A form´ alis nyelvek ´ es automat´ ak elm´ elete - a gy¨ okerek A nyelv grammatik´ aj´ anak fogalma m´ ar kb. id˝ osz´ am´ıt´ asunk el˝ ott az V. sz´ azadban felmer¨ ult Indi´ aban (Panini). Fontosabb l´ ep´ esek: • Axel Thue, Emil Post, matematika, a XX. sz´ azad eleje. • W. Mc Culloch, W. Pitts, 1943, az idegrendszer modellje - a v´ eges ´ allapot´ u g´ ep; S.C. Kleene, 1956, neur´ alis h´ al´ o - a v´ eges automata. • Noam Chomsky, 1959, matematikai model, az angol nyelv grammatik´ aj´ anak matematikai modellje. • Programnyelvek, ALGOL 60, 1960 9
Mivel foglalkozik a form´ alis nyelvek ´ es automat´ ak elm´ elete? A form´ alis nyelvek elm´ elete szimb´ olumsorozatok halmazaival foglalkozik. C´ elja - t¨ obbek k¨ oz¨ ott - v´ eges, t¨ om¨ or le´ır´ as´ at adni az ilyen halmazoknak. Az elm´ elet m´ odszereket ad form´ alis nyelvek defini´ al´ as´ ara, a form´ alis elemek nyelvhez val´ o tartoz´ as´ anak eld¨ ont´ es´ ere, a nyelvi elemek strukt´ ur´ aj´ anak felismer´ es´ ere. A szimb´ olum fogalm´ at alapfogalomnak tekintj¨ uk, ez´ ert nem defini´ aljuk. 10
Milyen tudom´ any´ agakhoz kapcsol´ odnak a form´ alis nyelvek ´ es automat´ ak?
• A term´ eszetes nyelvek g´ epi feldolgoz´ asa, matematikai modellez´ ese, matematikai nyelv´ eszet,
• programoz´ asi nyelvek, ford´ıt´ oprogramok elm´ elete,
• k´ odelm´ elet,
• k´ epfeldolgoz´ as, 11
• mintafelismer´ es,
• fejl˝ od˝ o rendszerek modellez´ ese (Lindenmayer rendszerek),
• molekul´ aris sz´ am´ıt´ astudom´ any (DNS sz´ am´ıt´ as),
• multi-´ agens rendszerek form´ alis le´ır´ asai,
• stb.
Alapfogalmak ´ es jel¨ ol´ esek - I Szimb´ olumok v´ eges nem¨ ures halmaz´ at ´ ab´ ec´ enek nevezz¨ uk. P´ elda: V = {a, b, c} Egy V ´ ab´ ec´ e elemeib˝ ol k´ epzett v´ eges sorozatokat V feletti szavaknak vagy sztringeknek mondunk. P´ elda: Legyen az ´ ab´ ec´ e V = {a, b, c} ´ es akkor aaabbbccc egy sz´ o. A 0 hossz´ us´ ag´ u sorozatot ¨ ures sz´ onak nevezz¨ uk ´ es ε-nal jel¨ olj¨ uk. A V ´ ab´ ec´ e feletti szavak halmaz´ at (bele´ ertve az ¨ ures sz´ ot is) V ∗-gal, a nem¨ ures szavak halmaz´ at V +-szal jel¨ olj¨ uk. 12
Alapfogalmak ´ es jel¨ ol´ esek - II
Legyen V egy ´ ab´ ec´ e ´ es legyenek u, v V feletti szavak (azaz, legyen u, v ∈ V ∗). Az uv sz´ ot az u ´ es v szavak konkaten´ altj´ anak nevezz¨ uk. P´ elda: Legyen az ´ ab´ ec´ e V = {a, b, c}, legyenek u = abb ´ es v = cbb szavak. Akkor uv = abbcbb az u ´ es v konkaten´ altja.
A konkaten´ aci´ o mint m˝ uvelet asszociat´ıv, de ´ altal´ aban nem kommutat´ıv. P´ elda: Legyen u = ab, v = ba, akkor uv = abba ´ es vu = baab. 13
Alapfogalmak ´ es jel¨ ol´ esek - II - folytat´ as Legyen V egy ´ ab´ ec´ e. Meg´ allap´ıthatjuk, hogy V ∗ z´ art a konkaten´ aci´ o m˝ uvelet´ ere n´ ezve (azaz, b´ armely u, v ∈ V ∗ eset´ en uv ∈ V ∗ teljes¨ ul), tov´ abb´ a a konkaten´ aci´ o egys´ egelemes m˝ uvelet, ahol az egys´ egelem ε (azaz, b´ armely u ∈ V ∗ eset´ en uε ∈ V ∗ ´ es εu ∈ V ∗).
14
Alapfogalmak ´ es jel¨ ol´ esek - III
Legyen i nemnegat´ıv eg´ esz sz´ am ´ es legyen w a V ´ ab´ ec´ e feletti sz´ o (w ∈ V ∗). A w sz´ o i-edik hatv´ anya alatt a w sz´ o i p´ eld´ any´ anak konkaten´ alj´ at ´ ertj¨ uk ´ es wi-vel jel¨ olj¨ uk. P´ elda: Legyen az ´ ab´ ec´ e V = {a, b, c}, ´ es legyen w = abc. w3 = abcabcabc.
Akkor
Konvenci´ o alapj´ an minden w ∈ V ∗ sz´ ora w0 = ε. 15
Alapfogalmak ´ es jel¨ ol´ esek - IV
Legyen V egy ´ ab´ ec´ e ´ es legyen w egy V feletti sz´ o (azaz, legyen w ∈ V ∗). A w sz´ o hossz´ an a w sz´ ot alkot´ o szimb´ olumok sz´ am´ at ´ ertj¨ uk (azaz, w mint sorozat hossz´ at) ´ es |w|-vel jel¨ olj¨ uk. P´ elda: Legyen az ´ ab´ ec´ e V = {a, b, c} ´ es legyen w = abcccc. Akkor w hossza 6. Az ¨ ures sz´ o hossza - nyilv´ anval´ oan - 0, azaz |ε| = 0. 16
Alapfogalmak ´ es jel¨ ol´ esek - V
Egy V ´ ab´ ec´ e feletti k´ et u ´ es v sz´ ot azonosnak nevez¨ unk, ha mint szimb´ olumsorozatok egyenl˝ oek (azaz, mint sorozatok elemr˝ ol-elemre megegyeznek.) Legyen V egy ´ ab´ ec´ e ´ es legyenek u ´ es v szavak V felett. Az u sz´ ot a v sz´ o r´ eszszav´ anak nevezz¨ uk, ha v = xuy teljes¨ ul valamely x ´ es y V feletti szavakra. Az u sz´ ot a v sz´ o val´ odi r´ eszszav´ anak mondjuk, ha x ´ es y k¨ oz¨ ul legal´ abb az egyik nem¨ ures, azaz, xy 6= ε. 17
P´ elda: Legyen V = {a, b, c} ´ ab´ ec´ e ´ es legyen v = aabbbcc sz´ o. u = abbbc sz´ o val´ odi r´ eszszava v-nek.
Az
Ha x = ε, akkor u-t a v sz´ o prefix´ enek, ha y = ε, akkor u-t a v sz´ o szufix´ enek h´ıvjuk. Legyen v = aabbbcc sz´ o. Az u = aabbb sz´ o prefixe, a bbbcc sz´ o szufixe v-nek.
Alapfogalmak ´ es jel¨ ol´ esek - VI
Legyen u egy V ´ ab´ ec´ e feletti sz´ o. Az u sz´ o t¨ uk¨ ork´ epe vagy ford´ıtottja alatt azt a sz´ ot ´ ertj¨ uk, amelyet ´ ugy kapunk, hogy u szimb´ olumait megford´ıtott sorrendben ´ırjuk. Az u sz´ o t¨ uk¨ ork´ ep´ et u−1 -gyel jel¨ olj¨ uk. Legyen u = a1 . . . an, ai ∈ V, 1 ≤ i ≤ n. Ekkor u−1 = an . . . a1.
18
Alapfogalmak ´ es jel¨ ol´ esek - VII Legyen V egy ´ ab´ ec´ e ´ es legyen L tetsz˝ oleges r´ eszhalmaza V ∗-nak. Akkor L-et egy V feletti nyelvnek nevezz¨ uk. Az ¨ ures nyelv - amely egyetlen sz´ ot sem tartalmaz - jel¨ ol´ ese ∅.
Egy V ´ ab´ ec´ e feletti nyelvet v´ eges nyelvnek mondunk, ha v´ eges sz´ am´ u sz´ ot tartalmaz, ellenkez˝ o esetben v´ egtelen nyelvr˝ ol besz´ el¨ unk.
19
P´ eld´ ak nyelvekre
Legyen V = {a, b} ´ ab´ ec´ e. Akkor L1 = {a, b, ε} v´ eges nyelv, L2 = {aibi | 0 ≤ i} v´ egtelen nyelv. P´ elda L2-beli szavakra: ab, aabb, aaabbb, . . . Legyen L3 = {uu−1|u ∈ V ∗}. P´ elda L3-beli szavakra: u = ababb, u−1 = bbaba ´ es uu−1 = ababbbbaba. 20
Nyelvek sokf´ ele m´ odon el˝ o´ all´ıthat´ ok, egyik m´ od a nyelvek gener´ al´ asa grammatik´ aval.
21
Generat´ıv grammatika - Defin´ıci´ o Egy G generat´ıv grammatik´ an (grammatik´ an vagy (generat´ıv) nyelvtanon) egy (N, T, P, S) n´ egyest ´ ert¨ unk, ahol • N´ es T diszjunkt ´ ab´ ec´ ek, a nemtermin´ alis ´ es a termin´ alis szimb´ olumok ´ ab´ ec´ ei; • S ∈ N a kezd˝ oszimb´ olum (axi´ oma), • P v´ eges halmaza (x, y) rendezett p´ aroknak, ahol x, y ∈ (N ∪ T )∗ ´ es x legal´ abb egy nemtermin´ alis szimb´ olumot tartalmaz. A P halmaz elemeit ´ at´ır´ asi szab´ alyoknak (r¨ oviden szab´ alyoknak) vagy produkci´ oknak nevezz¨ uk. Az (x, y) jel¨ ol´ es helyett haszn´ alhatjuk az x → y jel¨ ol´ est is, ahol a → szimb´ olum nem eleme az (N ∪ T ) halmaznak.
22
P´ elda Generativ Grammatik´ ara Legyen G = (N, T, P, S) egy generat´ıv grammatika, ahol N = {S} a nemtermin´ alisok ´ ab´ ec´ eje, T = {a, b} a termin´ alisok ´ ab´ ec´ eje, ´ es
P = {S → aSb, S → ab, S → ba} a szab´ alyok halmaza. 23
K¨ ozvetlen levezet´ esi l´ ep´ es - Defin´ıci´ o
Legyen G = (N, T, P, S) egy generat´ıv grammatika ´ es legyen u, v ∈ (N ∪ T )∗. Azt mondjuk, hogy a v sz´ o k¨ ozvetlen¨ ul vagy egy l´ ep´ esben levezethet˝ o az u sz´ ob´ ol G-ben ´ es ezt u =⇒G v m´ odon jel¨ olj¨ uk, ha u = u1xu2, v = u1yu2, u1, u2 ∈ (N ∪ T )∗ ´ es x → y ∈ P. 24
P´ elda k¨ ozvetlen levezet´ esre
Legyen G = (N, T, P, S) egy generat´ıv grammatika, ahol N = {S} a nemtermin´ alisok ´ ab´ ec´ eje, T = {a, b} a termin´ alisok ´ ab´ ec´ eje ´ es P = {S → aSb, S → ab, S → ba} a szab´ alyok halmaza. Legyen u = aaaSbbb. Akkor v = aaaaSbbbb k¨ ozvetlen¨ ul (egy l´ ep´ esben) levezethet˝ o u-b´ ol, azaz u =⇒G v, ugyanis u1 = aaa, u2 = bbb, x = S, y = aSb ´ es S → aSb ∈ P. 25
Levezet´ es - Defin´ıci´ o
Legyen G = (N, T, P, S) egy generat´ıv grammatika ´ es legyen u, v ∈ (N ∪ T )∗. Azt mondjuk, hogy a v sz´ o k l´ ep´ esben levezethet˝ o az u sz´ ob´ ol Gben, k ≥ 1, ha l´ etezik olyan u1, . . . , uk+1 ∈ (N ∪ T )∗ szavakb´ ol ´ all´ o sorozat, amelyre u = u1, v = uk+1, valamint ui =⇒G ui+1, 1 ≤ i ≤ k teljes¨ ul. A v sz´ o levezethet˝ o az u sz´ ob´ ol G-ben, ha vagy u = v, vagy l´ etezik olyan k ≥ 1 sz´ am, hogy a v sz´ o az u sz´ ob´ ol k l´ ep´ esben levezethet˝ o. 26
Levezet´ es Legyen G = (N, T, P, S) egy tetsz˝ oleges generat´ıv grammatika ´ es legyen u, v ∈ (N ∪ ∗ T) . Azt mondjuk, hogy a v sz´ o levezethet˝ o az u sz´ ob´ ol G-ben ´ es ezt u =⇒∗G v m´ odon jel¨ olj¨ uk, ha vagy u = v vagy valamely z ∈ (N ∪ T )∗ sz´ ora fenn´ all, hogy ∗ u =⇒G z ´ es z =⇒G v teljes¨ ul. =⇒∗ a =⇒ rel´ aci´ o reflex´ıv tranzit´ıv lez´ artj´ at jel¨ oli. A =⇒ rel´ aci´ o tranz´ıt´ıv lez´ artj´ at =⇒+ -val jel¨ olj¨ uk. A kezd˝ oszimb´ olumb´ ol levezethet˝ o sztringeket mondatform´ anak nevezz¨ uk.
27
A gener´ alt nyelv - Defin´ıci´ o
Legyen G = (N, T, P, S) egy tetsz˝ oleges generat´ıv grammatika. A G grammatika ´ altal gener´ alt L(G) nyelv alatt az L(G) = {w|S =⇒∗G w, w ∈ T ∗} szavakb´ ol ´ all´ o halmazt ´ ertj¨ uk. Azaz, a G grammatika ´ altal gener´ alt nyelv a T ∗ halmaz azon elemei, amelyek levezethet˝ ok a G grammatika S kezd˝ oszimb´ olum´ ab´ ol.
28
P´ elda
Legyen G = (N, T, P, S) egy generat´ıv grammatika, ahol N = {S}, T = {a, b} ´ es P = {S → aSb, S → ab, S → ba}. Akkor L(G) = {anabbn, anbabn|n ≥ 0}. P´ elda egy levezet´ esre: S =⇒G aSb =⇒G aaSbb =⇒G aababb.
29
P´ elda Legyen G = (N, T, P, S) egy generat´ıv grammatika, ahol N = {S, X, Y }, T = {a, b, c}. Legyen P = {S → abc, S → aXbc, Xb → bX, Xc → Y bcc, bY → Y b, aY → aaX, aY → aa}.
Akkor L(G) = {anbncn|n ≥ 1}. P´ elda egy levezet´ esre: S =⇒ aXbc =⇒G abXc =⇒G abY bcc =⇒G aY bbcc =⇒G aabbcc. 30
Ekvivalens Grammatik´ ak ´ es Nyelvek
K´ et generat´ıv grammatik´ at (gyeng´ en) ekvivalensnek nevez¨ unk, ha ugyanazt a nyelvet gener´ alj´ ak. K´ et nyelvet gyeng´ en ekvivalensnek mondunk, ha legfeljebb az ¨ ures sz´ oban k¨ ul¨ onb¨ oznek.
31
A Chomsky-f´ ele hierarchia A G = (N, T, P, S) generat´ıv grammatik´ at i-t´ıpus´ unak mondjuk, i = 0, 1, 2, 3, ha P szab´ alyhalmaz´ ara teljes¨ ulnek a k¨ ovetkez˝ ok: • i = 0: Nincs korl´ atoz´ as. • i = 1: P minden szab´ alya u1Au2 → u1vu2 alak´ u, ahol u1, u2 , v ∈ (N ∪ T )∗, A ∈ N , ´ es v 6= ε, kiv´ eve az S → ε alak´ u szab´ alyt, felt´ eve, hogy P -ben ilyen szab´ aly l´ etezik. Ha P tartalmazza az S → ε szab´ alyt, akkor S nem fordul el˝ o P egyetlen szab´ aly´ anak jobboldal´ an sem. • i = 2: P minden szab´ alya A → v alak´ u, ahol A ∈ N ´ es v ∈ (N ∪ T )∗. • i = 3: P minden szab´ alya vagy A → uB vagy A → u, alak´ u, ahol A, B ∈ N ´ es u ∈ T ∗. 32
P´ elda
Legyen G = (N, T, P, S) egy generat´ıv grammatika, ahol N = {S}, T = {a, b} ´ es P = {S → aSb, S → ab, S → ba}. Ez a grammatika 2-t´ıpus´ u (k¨ ornyezetf¨ uggetlen).
33
A Chomsky-f´ ele hierarchia - folytat´ as Legyen i = 0, 1, 2, 3. Egy L nyelvet i-t´ıpus´ unak mondunk, ha i-t´ıpus´ u grammatik´ aval gener´ alhat´ o. Az i-t´ıpus´ u nyelvek oszt´ aly´ at Li -vel jel¨ olj¨ uk. A 0-t´ıpus´ u grammatik´ at mondatszerkezet˝ u grammatik´ anak, az 1-t´ıpus´ u grammatik´ at k¨ ornyezetf¨ ugg˝ o grammatik´ anak, a 2-t´ıpus´ u grammatik´ at k¨ ornyezetf¨ uggetlen grammatik´ anak is nevezz¨ uk. A 3-t´ıpus´ u grammatik´ at regul´ aris vagy v´ eges ´ allapot´ u grammatik´ anak is mondjuk. A 0,1,2,3-t´ıpus´ u nyelvek oszt´ alyait rendre rekurz´ıven felsorolhat´ o, k¨ ornyezetf¨ ugg˝ o, k¨ ornyezetf¨ uggetlen, valamint regul´ aris nyelvoszt´ alynak is mondjuk.
34
A Chomsky-f´ ele hierarchia - folytat´ as
Nyilv´ anval´ o, hogy L3 ⊆ L2 ⊆ L0 ´ es L 1 ⊆ L 0 . A k´ es˝ obbiekben megmutatjuk, hogy L3 ⊂ L2 ⊂ L1 ⊂ L0 .
Megjegyz´ es: K¨ onnyen ´ eszrevehetj¨ uk, hogy a L2 ´ es a L1 nyelvoszt´ alyok k¨ oz¨ otti, a tartalmaz´ asra vonatkoz´ o rel´ aci´ o nem azonnal l´ athat´ o a megfelel˝ o grammatik´ ak defin´ıci´ oj´ ab´ ol. 35
Hivatkoz´ as:
Gy¨ orgy E. R´ ev´ esz, Introduction to Formal Languages, McGraw-Hill Book Company, 1983, Chapter 1.
36
