Form´ alis Nyelvek - 1. 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. Csima Judit ´ es Friedl Katalin: Nyelvek ´ es automat´ ak, BMGE jegyzet, 2013. (weben el´ erhet˝ o) 2. R´ ev´ esz Gy¨ orgy, Bevezet´ es a form´ alis nyelvek elm´ elet´ ebe, Tank¨ onyvkiad´ o, 1977. 3. F¨ ul¨ op Zolt´ an, Form´ alis nyelvek ´ es szintaktikus elemz´ es¨ uk, Polygon, Szeged, 2004. 4. Bach Iv´ an: Form´ alis nyelvek, Typotex, 2001. 3
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. 5. M. Sipser: Introduction to the Theory of Computation, 2nd edition, Thomson Course Technology, 2006. 4
Tudnival´ ok Az el˝ oad´ asok alapj´ aul az irodalomjegyz´ ek magyar- ´ es angol nyelv˝ u elemei szolg´ alnak. Az t´ ablak´ epek (a di´ ak) seg´ıtik a felk´ esz¨ ul´ est ´ es kiz´ ar´ olag tanul´ asi c´ elokra haszn´ alhat´ ok. A di´ ak szerz˝ oi jogv´ edelem alatt ´ allnak, mind r´ eszben, mind eg´ eszben kiz´ ar´ olag az el˝ oad´ o (Csuhaj Varj´ u Erzs´ ebet) honlapj´ an tehet˝ ok publikuss´ a!!! A kurzus vizsg´ aval z´ arul, a vizsga sor´ an az el˝ oad´ asokon elhangzott anyagot k´ erem sz´ amon. Vizsg´ azni csak legal´ abb el´ egs´ eges gyakorlati jegy birtok´ aban lehet. 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. Az el˝ oad´ asok l´ atogat´ asa nem k¨ otelez˝ o, de er˝ osen 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. 5
Az el˝ oad´ asv´ azlatokat (a di´ akat) .pdf file form´ aj´ aban az el˝ oad´ asok ut´ an felteszem a Neptun-meet-street-be. Minden kedden 10-12 ´ ora 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. Ha b´ armilyen k´ erd´ es¨ uk van a tant´ arggyal kapcsolatban, keressenek meg emailben (
[email protected]) vagy a fogad´ o´ or´ an. J´ o tanul´ ast k´ıv´ anok! Budapest, 2016. febru´ ar Csuhaj Varj´ u Erzs´ ebet tansz´ ekvezet˝ o egyetemi tan´ ar
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, Chomsky-f´ ele nyelvoszt´ alyok bizonyos z´ arts´ agi tulajdons´ agai. 3. K¨ ornyezetf¨ uggetlen grammatik´ ak ´ es nyelvek: reduk´ alt grammatik´ ak, norm´ alform´ ak, levezet´ esi fa. Regul´ aris grammatik´ ak, regul´ aris nyelvek, regul´ aris kifejez´ esek. A gener´ alt nyelvek ´ es nyelvoszt´ alyok bizonyos fontos tulajdons´ agai. 4. K¨ ornyezetf¨ ugg˝ o- ´ es mondatszerkezet˝ u grammatik´ ak: hossz-nemcs¨ okkent˝ o grammatik´ ak, norm´ alform´ ak. A gener´ alt nyelvek ´ es nyelvoszt´ alyok tulajdons´ agai. Nyelvoszt´ alyok Chomsky-f´ 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. Az automat´ ak tulajdons´ agai, a felismert nyelvoszt´ alyok, az automat´ ak ´ es a grammatik´ ak kapcsolatai. 2. Line´ arisan korl´ atozott automata, Turing g´ ep. 3. Szintaktikai elemz´ es: kapcsolat szintaxis ´ es szemantika k¨ oz¨ ott; 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 IV. 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 ´ es le´ır´ as´ ara. 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- m´ as sz´ oval f¨ uz´ ereknek- mondunk. A 0 hossz´ us´ ag´ u sorozatot ¨ ures sz´ onak nevezz¨ uk ´ es ε-nal jel¨ olj¨ uk. P´ elda: Legyen az ´ ab´ ec´ e V = {a, b, c} ´ es akkor aaabbbccc egy sz´ o. 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 vagy m´ as sz´ oval ¨ osszef˝ uz´ es´ enek 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. Megjegyz´ es: 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 ´ 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 u 6= v ´ es u 6= ε. 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. 17
Az
Alapfogalmak ´ es jel¨ ol´ esek - V - folytat´ as
Legyen V ´ ab´ ec´ e´ es legyenek u, v, x, y szavak V felett, tov´ abb´ a legyen v = xuy. Ha x = ε, akkor u-t a v sz´ o prefix´ enek vagy kezd˝ oszelet´ enek, ha y = ε, akkor u-t a v sz´ o szufix´ enek vagy ut´ otagj´ anak h´ıvjuk. Legyen v = aabbbcc sz´ o. Az u = aabbb sz´ o prefixe, a bbbcc sz´ o szufixe v-nek.
18
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.
19
Alapfogalmak ´ es jel¨ ol´ esek - VII Legyen V ´ 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.
20
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. 21
Nyelvekre vonatkoz´ o m˝ uveletek - I Legyen V egy ´ ab´ ec´ e´ es legyenek L1 , L2 nyelvek V felett (L1 ⊆ V ∗ ´ es L2 ⊆ V ∗ ). • L1 ∪ L2 = {u | u ∈ L1 vagy u ∈ L2 } - az L1 ´ es az L2 nyelv uni´ oja; • L1 ∩ L2 = {u | u ∈ L1 ´ es u ∈ L2 } - az L1 ´ es az L2 nyelv metszete; • L1 − L2 = {u | u ∈ L1 ´ es u ∈ / L2 } - az L1 ´ es az L2 nyelv k¨ ul¨ onbs´ ege. ¯ = V ∗ − L. • Az L ⊆ V ∗ nyelv komplementere a V ´ ab´ ec´ ere vonatkoz´ oan L
22
Nyelvekre vonatkoz´ o m˝ uveletek - II Legyen V ´ ab´ ec´ e´ es legyenek L1 , L2 nyelvek V felett (L1 ⊆ V ∗ ´ es L2 ⊆ V ∗ ). • L1L2 = {u1u2 | u1 ∈ L1 , u2 ∈ L2 } - az L1 ´ es az L2 nyelv konkaten´ aci´ oja; • Minden L nyelvre fenn´ allnak a k¨ ovetkez˝ o egyenl˝ os´ egek: ∅L = L∅ = ∅ ´ es {ε}L = L{ε} = L. • Li jel¨ oli az L nyelv i-edik hatv´ any´ at: 0 i i−1 L = {ε}, L = L L, i ≥ 1. • Az L nyelv az lez´ artja (Kleene-lez´ artja) alatt az S L∗ = i≥0 Li nyelvet ´ ertj¨ uk. A megfelel˝ o m˝ uveletet lez´ ar´ asnak vagy ∗-m˝ uveletnek mondjuk. S ertj¨ uk. • Az L+ nyelv alatt az L+ = i≥1 Li nyelvet ´ Nyilv´ anval´ oan, ha ε ∈ L, akkor L+ = L∗ . 23
Nyelvekre vonatkoz´ o m˝ uveletek - III Legyen V egy ´ ab´ ec´ e´ es L ⊆ V ∗ . L−1 = {u−1|u ∈ L} a t¨ uk¨ ork´ epe (megford´ıt´ asa) az L nyelvnek. Tulajdons´ ag: (L−1)−1 = L ´ es (L−1)i = (Li)−1, i ≥ 0.
24
Nyelvekre vonatkoz´ o lek´ epez´ esek: Legyen V1 , V2 ´ ab´ ec´ e. A h : V1∗ → V2∗ lek´ epez´ est homomorfizmusnak nevezz¨ uk, ha h(uv) = h(u)h(v) ∗ minden u, v ∈ V1 eset´ en. A fenti tulajdons´ ag alapj´ an h(ε) = ε. (Minden u ∈ V1∗ -ra h(u) = h(εu) = h(uε).) Nyilv´ anval´ o, hogy minden u = a1 a2 . . . an sz´ ora, ahol ai ∈ V1 , 1 ≤ i ≤ n, fenn´ all, hogy h(u) = h(a1 )h(a2 ) . . . h(an ).
25
Nyelvekre vonatkoz´ o lek´ epez´ esek: Legyen h : V1∗ → V2∗ homomorfizmus. ora, A h homomorfizmus ε-mentes, ha h(u) 6= ε b´ armely u ∈ V1∗ sz´ ahol u 6= ε. Legyen h : V1∗ → V2∗ homomorfizmus. Az L ⊆ V1∗ nyelv h-homomorf k´ ep´ en a h(L) = {w ∈ V2∗ | w = h(u), u ∈ L} nyelvet ´ ertj¨ uk. 26
Nyelvekre vonatkoz´ o lek´ epez´ esek:
A h homomorfizmust izomorfizmusnak nevezz¨ uk, ha b´ armely u ´ es v ora teljes¨ ul, hogyha h(u) = h(v), akkor u = v. V1∗-beli sz´ Egy p´ elda az izomorfizmusra a decim´ alis sz´ amok bin´ aris reprezent´ aci´ oja: V1 = {0, 1, 2, . . . , 9}, V2 = {0, 1}, h(0) = 0000, h(1) = 0001, . . . , h(9) = 1001
27
