Szoftver Szigorlat Tételek '07 BSC Készítette: Somody Gábor Ádám 2007.05.26
1
Tételsor Témakörök:
Amit nem tudtam kidolgozni azt félkövér betűvel jelzem!! Légyszíves dolgozzátok ki, és küldjétek el a [email protected] címre. Köszönöm mindenki nevében.
Elméleti alapok, nyelvek, paradigmák:
Majdnem teljesen kész!!! 1 hiányzik!!
1. A 0-s nyelvosztály. A Turing gép definíciója. Mit jelent a T Turing-gép által elfogadott nyelv, és milyen típusú? Szubrutin Turing-gépen. A Turing-gép változatai és a Turing-géppel ekvivalens gépek. (Mit jelent az ekvivalencia. Bizonyítani itt nem kell.) 2. A bináris szalagot használó Turing gép mozgási szabályainak megadása bináris sorozat formájában. (táblázattal ) Az utánzó Turing-gép konstrukciója. Ebből az univerzális Turing-gép konstrukciója. (Turing-gépek sorszámozása a bináris táblázat alapján.) 3. A Chomsky-hierarchia. A grammatikákra tett megszorítások nyelvosztályonként. Az egyes nyelvosztályokra az elfogadást milyen géppel lehet elvégezni? (Csak a gépek megnevezése kell.) 4. A környezetfüggő nyelvek. Grammatika alakja. A lineárisan korlátozott Turing-gép. 5. A reguláris nyelvek. Grammatika megadása. Véges állapotú automata, grammatikák és automaták megfeleltetése. Változatok (nem determinisztikus, determinisztikus, teljes) 6. Az önmaguk leírását elfogadó, illetve az önmaguk leírását nem elfogadó Turing gépek leírásai milyen nyelvosztályba tartoznak. A Turing gépek megállásának eldönthetetlensége. 7. Környezetfüggetlen nyelvek. A grammatika megadása. A levezetési fa és szerepe. A kettős pumpálási lemma. (Nagy Bar-Hillel lemma) 8. Milyen műveletekre zártak, illetve nem zártak a környezetfüggetlen nyelvek. A tartalmazási kérdés eldönthetősége. 9. Műveletek reguláris nyelvekkel, reguláris kifejezések, pumpálási lemma (kis Bar-Hillel lemma.) 10. Nem determinisztikus Turing-géphez determinisztikus Turing gép szerkesztése. 11. Nyelvek (függvények) időbonyolultsága, bonyolultsági osztályok. (Determinisztikus, és nem – determinisztikus bonyolultság.) 12. Nyelvek (függvények) tárbonyolultsága, bonyolultsági osztályok. (Determinisztikus, és nem – determinisztikus bonyolultság.) 13. Nyelvek és nemnegatív egész számokból álló halmazok megfeleltetése. Rekurzív (eldönthet halmazok), rekurzívan felsorolható halmazok. Turing-gépek, mint átalakítók. Kiszámítható függvények. 14. Véges ÁBC feletti nyelv fogalma. Grammatika megadása. A grammatika által generált nyelv. 15. Veremautomaták. Veremautomaták és környezetfüggetlen grammatikák megfeleltetése. Veremautomata konstrukciója grammatikához. Klasszikus algoritmusok: Animált rendezések: http://www.cs.bme.hu/~kiskat/sza/anim.html 16. Alapvető programozási tételek (N-1) (összegzés, számlálás, maximumkeresés, lineáris keresés, logaritmikus keresés) 17. Alapvető programozási tételek (N-N) (szétválogatás, halmazműveletek), Programozási tételek összeépítése. 18. Dinamikus programozás (mátrixok láncszorzása) 19. n*n-es rendezések (alapelvek, algoritmusok) 20. Haladó rendezések I. ( Kupacrendezés, Shell rendezés) 21. Haladó rendezések II. (Szétosztó-, Leszámláló-, Radix-, Edényrendezés) 22. Haladó rendezések III. (quicksort, rekurzív és nemrekurzív módon) 23. Ritka mátrixokkal kapcsolatos algoritmusok. 24. Strassen mátrixszorzási algoritmus. 25. A játékelmélet alapjai. Klasszikus adatstruktúrák: Ezt dolgozzátok ki!! 26. Adatszerkezetek, láncolt listák, egyszer láncolt listák műveletei I. (új elem felvétele, bejárás, törlés) 27. Adatszerkezetek, láncolt listák, speciális listák műveletei II. (rendezett láncolt lista, többirányú, többszörösen láncolt lista, strázsa) 28. B-fa adatszerkezet, B-fába való beszúrás algoritmusa (B-fa jellemzői, előnyei, felépítése, új elem felvétele) 29. B-fa adatszerkezet, B-fából való törlés algoritmusa (B-fa jellemzői, előnyei, felépítése, törlés) 30. Fa adatszerkezetek, bináris fák alapműveletei (új elem felvétele, bejárások, törlés) 31. Fa adatszerkezetek, piros-fekete fa adatszerkezet (forgatások, új elem felvétele, törlés) 32. Gráfok I. (körmentes út keresése (labirintus); legrövidebb út keresése). 33. Gráfok II. (Kruskal algoritmus és alkalmazásai) 34. Gráfok III. (topológiai rendezés és alkalmazásai) 35. Hasító táblázatok (alapelvek, hasító függvények, kulcsütközések feloldása)
2
Szoftverfejlesztés lépései:
Teljesen kész!!!
36. A szoftver jellemzői (a termék elállítás jellemzői, hibaaránygörbék, költségösszetevők, költségarányok) 37. A szoftverkrízis (előzmények, tünetek, okok, megoldások) 38. A szoftverfolyamat modelljei I. (modelltípusok, a modellezési koncepció, célok, a vízesés modell) 39. A szoftverfolyamat modelljei II. ( az evolúciós modell, a formális rendszerfejlesztés) 40. A szoftverfolyamat modelljei III. (újrafelhasználás orientált fejlesztés, inkrementális fejlesztés, RAD modell) 41. A szoftverfolyamat modelljei IV. (spirális fejlesztés, Agile Software Processes, XP) 42. A szoftver projekt ütemezése 43. Szoftver projekt mérése 44. Programozás, tesztelés, szoftverevolúció (a belövés folyamata, szoftvervalidáció, tesztelési folyamat, fázisok, dokumentumok, az evolúció folyamata) 45. Projekt becslés (általános fogalmak, dekompozíción alapuló technikák, tapasztalati becslési modellek, becslési bizonytalanság) 46. Projekt menedzsment, projekt tervezés (a menedzsment kérdései, a projekt elkészítése, a terv típusai, a tervkészítés folyamata, a terv szakaszai, mérföldkövek a folyamatban) 47. Kockázat menedzsment 48. COCOMO 81, COCOMO 2 49. Team-szervezési megoldások Tervezési módszerek: Teljesen kész!!! 50. Szoftverspecifikáció (fázisok, folyamat, technikák) 51. Szoftvertervezés (a folyamat tevékenységei, általános modell, általános elvek) 52. Tervezési módszerek I. (kategorizálás, a Jackson féle módszer) 53. Tervezési módszerek II. (Strukturált analízis és tervezés) 54. Jelentősebb OO módszertanok (OOAD, RDD, OOSE, OOD, OMT) 55. UML (fogalmak, keletkezése, jellemzői, célok, tulajdonságok, kritikája, építőkövei) 56. UML – Osztály diagramm 57. UML – Objektum és szekvencia diagramm 58. UML – Use Case Diagramm 59. UML – Együttműködési diagramm, állapot diagramm 60. UML – Aktivitás (activity) diagramm, package diagramm 61. UML – Komponens diagramm, Konfigurációs (Deployment) diagramm 62. UML – Composite structure, Kollaborációs, Timing, Interaction Overview diagrammok 63. RUP I. (jellemzők, történelem, UML és RUP, módszertan, technológia, eszközök, emberek, szervezeti minták) 64. RUP II. (a RUP fázisai) 65. Verifikáció és validáció. Implementációs technikák, OOP paradigma: Teljesen kész lesz a hétvégére!!! 66. Osztály, objektum, UML jelölések (Konstruktor, destruktor, példányosítás. Egységbezárás, láthatóságok, tulajdonság. Osztályok láthatósága. Self vagy this.) 67. Osztályok csoportosítása (Logikai csoportosítás, fizikai csoportosítás. Névterek. A dll és az assembly. A komponensalapú programozást támogató láthatóságok. Friend kapcsolat.) 68. Osztály szint tagok (Osztályszint adattagok fogalma, inicializálása. Osztály szint tagfüggvények. Példák osztály szint tagok felhasználására. Singleton pattern) 69. Konstruktorok (Konstruktor, destruktor hívások sorrendje öröklés és asszociációs kapcsolat, többszörös öröklés esetén. Default és felülírt konstruktorok. Taginicializáló lista. A konstruktor, destruktor feladatai virtuális metódushívás esetén.) 70. Hivatkozás és érték típusok (Hivatkozás típusú tagok inicializálása. Hivatkozás és érték típusok közti különbség. Automatikus szemétgyűjtés. A hivatkozás argumentum és visszatérési érték. Konstansok.) 71. Öröklés (Öröklés fogalma, UML jelölése. Specializáció és absztrakció. Adatvédelem az öröklés során. Függvény felüldefiniálás (elrejtés) az utódosztályokban. Hatókör feloldó operátor vagy base. Többszörös öröklés és problémái. Lezárt osztályok.) 72. Nem virtuális, virtuális metódusok (Virtuális és nem virtuális metódusok viselkedése közti különbség. Fordításidejű, futásidejű kötés. Polimorfizmus. VMT. Virtualitás lehetőségei a különböző nyelvekben. Statikus metódus és virtuális metódus kapcsolata. Lezárt metódusok. Komponensek új verziói és a virtualitás.) 73. Az értékadás problémái (s típusú referencia/mutató utód típusú objektumra hivatkozik/mutat. Típuskényszerítés. Az ‘is’ és az ‘as’ operátor. Hozzon példákat az osztálykönyvtárból az elv alkalmazására!) 74. Absztrakt interfész (Absztrakt függvény. Absztrakt osztály. Interfész fogalma. Szerepük az öröklésben. Azonosság és különbség az interfész és az absztrakt osztály között.) 75. Kivételkezelés (A kivételkezelés fogalma. Kivétel dobása, elkapása. Különböző típusú kivételek. Kezeletlen kivétel. Egymásba ágyazott kivételek. Egy választott osztálykönyvtár és a kivételkezelés.) 76. Operátor overloading (Az operátor átdefiniálás szabályai. Egy választott operátor átdefiniálása választott nyelven, különböző típusú paraméterekkel. Konverziós operátorok.) 77. Template fogalma (Függvény overloading vagy template függvény. Függvény paraméter és típus paraméter közti különbség. Template osztályok. A template bemutatása egy konkrét osztályon keresztül.)
3
Elméleti alapok, nyelvek, paradigmák
4
1. A 0-s nyelvosztály. A Turing gép definíciója. Mit jelent a T Turing-gép által elfogadott nyelv, és milyen típusú? Szubrutin Turing-gépen. A Turing-gép változatai és a Turing-géppel ekvivalens gépek. (Mit jelent az ekvivalencia. Bizonyítani itt nem kell.)
Turing-gépek és a 0-s nyelvosztály: Bevezetés: Alan Turing: 1936 Turing-gép Noam Chomsky: 1956 Nyelvosztályok Nagy ugrás következik: a 3-as és 2-es nyelvosztály felismerő gépei után a „minden felismerhetőt” felismerő gépek következnek, a Turing-gépek. Ehhez kapcsolódóan a „minden formálisan leírható” nyelvet tartalmazó 0-ás nyelvosztály következik. A 3-as és 2-es nyelvosztályoknál jól látható a szövegszerű jellemzések szerepe. Gyakorlati használatuk is erre épül. Nézzük meg még egyszer a fizikai megvalósítás méretigényét a két felismerő gépre: Reguláris nyelv – véges automata: A gép mérete csak az állapotátmeneti rendszertől függ (gráf éleinek száma), konstans. Egy n hosszú mondat elfogadása csak n-el arányos mennyiségű időt igényel. Környezetfüggetlen nyelv – veremautomata: A gép mérete a mozgásokat leíró 3 rendszer méretével arányos. Egy n hosszú mondat elfogadása az elemző fa felépítését igényli, ezért n logn -nel arányos időt (lépésszámot) igényel. Ezen felül a veremmemória fizikai mérete és n-nel arányos. Programozási nyelveken mindkét automata programja elkészíthető. A veremautomata esetében nagy mondatok elemzésénél tárkezelési problémák jönnek be. A Turing-gépek szerepe egészen más. Elvi, elméleti szerepet töltenek be. A céljuk nem a felhasználás, mint az előző két automata esetében. Feladatuk az algoritmusok, eljárások (procedúrák) segítségével megoldható feladatok jellemzése, az algoritmusok elméleti tárgyalásához eszköz, matematikai módszer biztosítása. Mit tudnak a Turing-gépek? Válasz: a Church-tézis. A Church-tézis azt állítja, hogy minden probléma, amelyre eljárás, procedúra szerkeszthető Turing géppel megoldható. Ez nagyon súlyos kijelentés, hiszen ez annyit jelent, hogy a Turing-gép a matematikai értelemben vett megismerhetőség határa. Más megfogalmazásban a kiszámíthatóság szerepel: minden intuitíva kiszámítható függvényhez létezik Turing-gép, amely ugyanazt a függvényt határozza meg. A tézis nem tétel. Nincs bebizonyítva. Eddig minden konkrét esetre bebizonyították. A Church-tézis egyszerre pozitív, és negatív állítás:
+: Ami megoldható, azt Turing-géppel meg lehet oldani. -: Mást nem tudunk megoldani, csak azt, amit a Turing-gépek tudnak. Ez a gondolkodás elvi korlátja. Nem minden kérdésre tudnak a Turing-gépek választ adni. Például, a 0-s nyelvosztály esetében a w ∈ L kérdésre nem minden nyelvhez lehet a választ megadó Turing-gépet konstruálni, úgy, hogy az w ∉ L esetben is véges lépésben választ adjon. Bevezetés vége Vannak Turing-géppel eldönthetetlen kérdések. Ebből az is következik, hogy a matematikában is vannak eldönthetetlen kérdések. (Kurt Gödel eldönthetetlenségi tétele). Majd látunk rá példát A 0-s nyelvosztály
G N , ∑ , P , S grammatikájában a P-beli szabályokra egyetlen megszorítás van: az
szabály baloldalán szerepeljen nem terminális: A Church-tézis szerint
∗
∈P
∗
∈ N ∪∑ N N ∪∑ .
w ∈ LG felismeréséhez létezik Turing-gép, ami akkor és csak akkor fogad el egy w mondatot, ha
w ∈ LG . A G grammatika segítségével a w ∈ LG mondathoz létezik véges levezetés, ami véges idő alatt megtalálható, tehát ez megoldható feladat. A w ∉ LG esetről általában nem tudjuk eldöntését garantálni. Fordítva is igaz, minden (felismerő) Turing-géphez létezik ekvivalens grammatika.
5
A Turing-gép felépítése:
Mindkét irányban végtelen, írható és olvasható cellákból álló szalag. A vezérlés az állapot és a beolvasott érték alapján új értéket ír vissza, jobbra vagy balra lép a szalagon, átmegy egy állapotba.
Formális megadás:
T =Q , ∑ , ,{ l , r } , , q 0, F , ahol -
Q : állapotok véges halmaza ∑ : input nyelv abc-je : a szalag abc-je ∑ ⊂ , ha üres szimbólumot „bl” (blank) jelöli, ez csak olvasható, felülírható, de nem írható jel. : a mozgások véges halmaza q 0 : kezdő állapot, q 0 ∈Q F : végállapotok halmaza, F ⊆Q .
A mozgások:
: Q× ⇒Q× – {bl }×{l , r } Ha egyértelmű: determinisztikus, ha nem, akkor nemdeterminisztikus. A blank „bl” szimbólum szerepe: azt jelzi, hogy üres a szalag eleje, vége. Ha a gép olvassa, felülírja azonnal. Az {l, r}szerepe: - l :balra lép (left) - r : jobbra lép (right) A T Turing-gép felismeri (elfogadja) a
∗
w ∈∑
szót:
- Kiinduláskor az input szalag a w szót tartalmazza, előtte és utána üres. - Az olvasófej w első betűjén áll, és a gép a q 0 állapotban van. - A gépnek van olyan mozgássorozata, amelynek során a teljes w szót elolvasta, és F-beli állapotba jutott. Példa: Igen egyszerű feladat: az input szó első betűje megegyezik-e az utolsóval? Állapot indexe: (első betű, olvasott betű) - jobbra lép, azt ír, amit olvasott, - kivétel: ha „bl”-et olvas.
q 0 , a q a ,a , a , r q a , b , c q a ,c , c , r q a , a , bl f 1 , a , l - a válasz igen: f 1 állapot q a , b , bl f 2 , b , l - a válasz nem: f 2 állapot Szubrutint lehet írni: Egyik Turing-gép szubrutinként (szolgaként, segéd-berendezésként) használ egy másikat. Legyen T 1 és T 2 két Turing-gép, Q 1 ∩Q 2 =0 , diszjunkt állapotok. T 1 kezdőállapota q 01 ,
T 2 kezdőállapota q02 A T 1−et módosítsuk, hogy egy q , a állapotban hívja meg T 2−t , majd T 2 befejeződése után jusson vissza egy p állapotba.
T 1−ben vegyük a q , a q 02 , a , r mozgást, T 2−ben az elfogadó állapot helyére írjuk p-t. Ezek után egyesítsük a két gépet.
6
Feladat: Turing-gép szerkesztése, amely egy másik Turing-gépet utánoz, úgy, hogy a gép leírását megkapja. 1.
Hogyan adjuk meg egy T Turing-gép leírását? Táblázattal. Az állapotokat számozhatjuk, helyettesíthetjük sorszámukkal. A táblázat egy sora: 5 elemből áll: < állapot , olvasott jel , írott jel , új állapot , irány > Az állapotot pl. 10-es számrendszerben, az irányt 0, 1-gyel (bal, jobb) adhatjuk meg. Használhatunk speciális szalag-jeleket: < , > a sor eleje és vége, # : a bejegyzések vége. Pl.: a 5 , a=6 ,b , l mozgásnak a 5 # a # b # 6# l # jelsorozat felel meg. Ilyen módon kódolhatjuk az input szalagra a T leírását. Legyen az w T .
2.
Hogyan utánozzuk T-t? A T lépés leutánzása:
w T w és T ' inputja. Fel kell jegyezni: hol áll T a saját szalagon, és hogy mi a T állapota.
- T aktuális címére állni - olvasni a cellát (de nem felülírni) - az olvasott érték szerint (pl. állapottal kódolható) - kikeresni a - megfelelő sort, - feljegyezni az új állapotot - az új-érték, irány szerinti állapotba visszamenni, T szerint címre írni az új értéket, lépni, feljegyezni az aktuális címet.
A Turing-gép változatai, ekvivalens gépek: 1, A szalagjelek megválasztása, : Lényegtelen, mi a véges abc a szalagon. Elég egyetlen jel és a „bl”. Gyakori a ={ 0,1, bl } választás. Tetszőleges véges ábécé: a 1 , a 2 ,… , a n átkódolható. Az indexeket binárisan átkódolhatjuk: szükséges az elválaszthatóságuk (prefixmentes kódolás jó). Átkódolással minden Turing-géphez készíthetünk ekvivalens bináris szalaggal dolgozó Turing-gépet. Emberi érthetőség miatt kényelmes a szalagon speciális jelek használatát megengedni. 2, Egyirányú szalag: ekvivalens a két irányban végtelen szalaggal rendelkező gép lehetőségeivel. Egy szalagos gép:
7
3, Több szalag egyidejű használata (párhuzamos gép): Nem növeli a Turing-gépek lehetőségeit. pl.: két szalagos géphez egy szalagos gép: 4 „sávos” szalag.
T 2 gép :
T 1 gép :
Kódolás: - első sáv: az első szalag másolata - második sáv: 1, ha a kétszalagos gép ezen a cellán áll, 0 ha nem - harmadik sáv: a második szalag másolata - negyedik sáv: 1, ha a kétszalagos gép ezen a cellán áll, 0 ha nem
A
T 1 működése: A T 2 gépnek megfelelő p állapotban
- megkeresi a 2. sávban az 1 értéket, megjegyzi X értékét (pl.: P 4X állapotba lép) - megkeresi a 4. sávban az 1 értéket, megjegyzi az Y értéket, (pl.: P X ,Y állapotba kerül) - A T_2 gép (p, x, y)- hoz tartozó
q , x ' , irány1 , y ' ,irány 2 mozgásnak megfelelő állapotot hozza létre a T 1 szalagján.
8
2. A bináris szalagot használó Turing gép mozgási szabályainak megadása bináris sorozat formájában. (táblázattal ) Az utánzó Turing-gép konstrukciója. Ebből az univerzális Turing-gép konstrukciója. (Turing-gépek sorszámozása a bináris táblázat alapján.) Több szalag egyidejű használata (párhuzamos gép): Nem növeli a Turing-gépek lehetőségeit. pl.: két szalagos géphez egy szalagos gép: 4 „sávos” szalag.
T 2 gép :
T 1 gép :
Kódolás: - első sáv: az első szalag másolata - második sáv: 1, ha a kétszalagos gép ezen a cellán áll, 0 ha nem - harmadik sáv: a második szalag másolata - negyedik sáv: 1, ha a kétszalagos gép ezen a cellán áll, 0 ha nem
A
T 1 működése: A T 2 gépnek megfelelő p állapotban
- megkeresi a 2. sávban az 1 értéket, megjegyzi X értékét (pl.: P 4X állapotba lép) - megkeresi a 4. sávban az 1 értéket, megjegyzi az Y értéket, (pl.: P X ,Y állapotba kerül) - A T_2 gép (p, x, y)- hoz tartozó
q , x ' , irány1 , y ' ,irány 2 mozgásnak megfelelő állapotot hozza létre a T 1 szalagján.
Az univerzális Turing-gép és a megállási probléma A T Turing-gép mozgási rendszerének megadása táblázattal: Elég, ha csak a ={ 0 ,1 , bl } szalag-ábécé használatára szorítkozunk, és determinisztikus gépekre. Olyan táblázatot készítünk, amit könnyen tudunk sorfolytonosan bináris adatként kezelni. A p , a=q , b ,irány mozgást a < p , a , q , b ,irány > ötössel adhatjuk meg. Legyen T állapotainak száma n. Sorszámozzuk az állapotokat, és sorszámukat [log 2 n] (felső egész) hosszú bináris kóddal adjuk meg. A beolvasott a érték lehet 0, 1 vagy bl: Kódjaik: bl – 00 0 – 01 1 – 11 A kiírt érték csak 0 vagy 1 lehet. A mozgás irányát a bal – 0, illetve a jobb – 1 kódolja. Egy sor kódolásához 2 [log 2 n]4 bit szükséges. A rendszer leírásához meg kell adni n értékét, és a táblázat sorainak számát, M-et.
T leírása: T =1n 0 1M 0sor 1…sor M > , és a sorokat érték szerint rendezve soroljuk fel.
A T gép
9
Feladat: Szerkesszünk Turing-gépet, amely tetszőleges T Turing-gép T leírót és utána egy w szót kapva inputként utánozza T-t, és w úgy dolgozza fel, mint T. Vagyis, ha T elfogadja w-t, akkor az utánzó gép is elfogadja, ha T nem elfogadó állapotban áll meg, akkor az utánzó gép is nem elfogadó állapotban áll meg, és ha T nem áll meg, akkor az utánzó gép sem áll meg. Tervezzük meg a szalag használatát:
Egyirányú szalag, T munkaszalagjának utánzására: A páratlan sorszámú cellák a w-től jobbra, a párosak a balra elhelyezkedő celláknak felelnek meg. Lépések vázlata: - A T gép egy p , a q , b ,irány lépésének utánzása a következő állapotból indul: A T-utánzó modul olvassa „a”-t. Az olvasási címe cím1-ben szerepel a szalagon. A Táblázat-kezelő modul olvasási címe a cím2 szalagrészen van. A cím2 a < P , x , ... > sorok közül az elsőre mutat. (Az utánzó gép állapotainak indexeiben kódolunk az olvasott jeleknek megfelelő információt.) 1. lépés: A T-utánzó modul működik, és „a”-t olvas. Átmegy elmegy cím2 olvasására.
P a ,k állapotba, és csupa P a ,valami típusú állapotot használva
2. lépés: A Táblázat-kezelő olvassa cím2-től kezdve az T táblázatot, továbbra is P a ,valami típusú állapotokat használva. A táblázat < P , x , q , b , irány > sorai közül megkeresi az x=a értéket tartalmazó sort. (Ha nincs ilyen, megáll, nem elfogadó állapotban.) Ehhez kell az állapotban az „a” index. Ha megtalálta a megfelelő sort, akkor állapotokkal folytatódik a futás. 3. lépés: megkeresi
q b , irány , valami típusú
T -ben az első < q , y , ... > q-hoz tartozó sort. (Ha nincs megáll.) Ennek címét írja cím2-be.
4. lépés: cím1 értékét az állapotban lévő irány index szerint
−2 ,−1 , 1 , 2−vel változtatja, kiírja.
5. lépés: Elmegy az (új) cím1-re. Az irány index értéke szerint a régi cím1-re áll, és beírja az indexből „b”-t. Az új cím1 olvasására lép, vagyis vissza az 1. lépésre. Jelöljük az így kapott utánzó gépet UT-vel. Az UT utánzó gépből könnyen megkapjuk a szokásos univerzális U Turing-gépet: Kezdjük a (bináris szalagot használó és determinisztikus) Turing-gépek sorszámozásával. A sorszámozást az T leírásoknak, mint bináris egész számoknak monoton növekvő sorrendje adja. - az első a sorrendben az üres (állapot nélküli) gép. A leírása n=0 és M =0 szerint 00 . - minden más esetben n≥1 miatt T 1-es bittel kezdődik, vagyis 2-es számrendszerben értékes jeggyel. Ez egyértelmű rendezést ad az T kódokra. - A T géphez az i indexet rendeljük, ha T az i-edik a felsorolásban. Jelölésben T i az i-edik Turing-gép. Az U univerzális Turing-gép az
1i 0 W bemenetre a T i -nek megfelelően dolgozza fel w-t.
U felépítése: - i-hez előállítja az i-edik leírást,
T i -t. (Ez nem nehéz feladat.)
- Meghívja UT-t az T i W inputtal.
10
3. A Chomsky-hierarchia. A grammatikákra tett megszorítások nyelvosztályonként. Az egyes nyelvosztályokra az elfogadást milyen géppel lehet elvégezni? (Csak a gépek megnevezése kell.)
A Chomsky hierarchia: Megszorítások a produkciós szabályokra: szigorú->gyengébb. Vannak
1 2 Szokásos jelölések: azonos jobboldalakra: ... n
}
3 2 1 0 osztályok.
jelölése : 1∣2∣…∣n
A nemtermálisokat gyakran a nyelv ABC-jével adjuk meg, ilyenkor <elnevezés> alakot használunk. Pl.: < magyar mondat > < alanyi rész > < állítmányi rész > ∣ < állítmányi rész > < alanyi rész >
Grammatikákra tett megszorítások nyelvosztályonként 3-as osztály: Reguláris nyelvek. G
∑ , N , P , S
P: minden szabály:
A aB
vagy
A a Megengedjük még az
S −szabály , de csak a mondatszimbólumra. Az üres szó akkor és csak akkor eleme L(G)-nek, ha P-ben van S szabály. Ezek a jobb-reguláris grammatikák. Ha minden szabály A Ba , akkor bal reguláris. Elfogadása: Véges automatával.
G= N , ∑ , P , S grammatika 2-es osztályú, más néven környezetfüggetlen, ha a levezetési szabályok alakjai: A w , ahol A∈ N és w ∈ N ∪∑ , egyetlen kivétel az S −szabály.
2-es osztály: Környezetfüggetlen nyelvek. A
Elfogadása: Veremautomatával. 1-es osztály: Környezetfüggő nyelvek. A P szabályai lehetnek:
G N , ∑ , P , S -ben P-ben itt is lehet S .
∗
A alakúak, ahol A∈ N , ∈ N ∪∑ , , ∈ N ∪∑ . A szabályokban az A környezetét adó , -ról kapta az osztály a környezetfüggő nyelvek elemzést. 2, változat: , ahol -ban van nemterminális, és ∣∣≤∣∣ (hosszak) nem csökkenő nyelvtan. 1, változat:
A két nyelvosztály ugyanaz. Elfogadása: Lineárisan korlátozott Turing géppel. 0-ás osztály:
G N , ∑ , P , S grammatikájában a P-beli szabályokra egyetlen megszorítás van: az
baloldalán szerepeljen nem terminális: Elfogadása: Turing géppel.
∗
∗
∈ N ∪∑ N N ∪∑ .
11
∈ P szabály
4. A környezetfüggő nyelvek. Grammatika alakja. A lineárisan korlátozott Turing-gép. Az 1-es nyelvosztály grammatikái: A P szabályai lehetnek: 1, változat:
G N , ∑ , P , S -ben P-ben itt is lehet S .
∗
A alakúak, ahol A∈ N , ∈ N ∪∑ , , ∈ N ∪∑ . A szabályokban az A környezetét adó , -ról kapta az osztály a környezetfüggő nyelvek elemzést. 2, változat:
, ahol -ban van nemterminális, és A két nyelvosztály ugyanaz.
∣∣≤∣∣
(hosszak) nem csökkenő nyelvtan.
A nemcsökkenő tulajdonság miatt w ∈ LG eldöntéséhez elég S-ből a sok) levezetést megnézni. Az L G nyelv rekurzív, ha G 1-es osztálybeli.
∣w∣ -nél nem hosszabb mondatformákra vezető (véges
Az elfogadó gép: Olyan Turing-gép, amelynek szalagja sz input méretével megegyező véges hosszúságú. Ezek a lineárisan korlátozott Turing-gépek. Jelöljük őket LKT-vel. Ha egy LKT nem elfogadó állapotba jutva lép le a szalagról, futása befejeződik. (Ezért egy LKT futása vagy véges, vagy periodikus.)
G= N , ∑ , P , S grammatikájához az LKT gép szalag abc-je legyen párok, ahol x ∈ ∑ és y ∈ N ∪∑ . Az 1-es osztály
∑
és az < x , y > alakú
A gép egy cellájában az input értéke „a” volt, akkor az „a” értéke a cellában nem változik, csak < a , y > érték írható be. Az LKT gép az szabályoknak megfelelő mondatformákat a második komponensben alakítja ki. A kialakított mondatforma hossza nem csökkenhet. Ha a végén a második komponensek mind komponens azonos lett, az LKT elfogadta az inputot.
∑
-beliek, és minden cellában a két
A cellák komponenseit egymás alá rajzoltuk. A X mondatformát az helyettesítésekkel alakítja a gép, hasonlóan a Turinggép konstrukciójához. A konstrukció nemdeterminisztikus gépet ad! Fordított irányban: LKT-hez G konstrukciójában a Turing-gépen konstrukció nem jó, ott törölni kell a segéd nemterminális jeleket, ami csökkentő szabály. Az állapot beszúrásával a szalagon lévő szó közepébe, szintén nem élhetünk, mert ki kell a végén törölni, s ez megint csökkentő. Mindez elkerülhető, ha a nemterminálisok indexelésébe helyezünk el mindent: Például az [ xx ] -nek feleljen meg Axx , minden x ∈ -ra.
∑
[ yx ] -nek feleljen meg Ayx , minden y ∈ és x ∈ ∑ -ra. A p [ yx] -nek feleljen meg A pyx . Az
Az LKT gép minden lépése egy nemterminálishoz kapcsolódik: amelyik három indexű. Például: p , a q , b , r −hez A pax Acy Abx Aq c y alakú szabályok tartoznak,
p , a q , b ,l −hez
Acy A pax Aqcy Abx alakú szabályok tartoznak.
A pax , vagy Acy indexeléses nemterminálisok helyett használható a Baskus-Naur jelölés: < pax > , < cy > is. Az LKT gépek közül nézzük a bináris szalaggal dolgozó gépeket. Ezek is Turing-gépek, leírhatók mozgásaik T mintájára. Az
Legyen
L11={ T ∣ ahol T LKT gép és elfogadja saját leírását.} L12={ T ∣ ahol T LKT gép és nem fogadja el saját leírását. } A borbély-paradoxon mintájára az L12 nyelv nem lehet 1-es osztálybeli, nem létezhet hozzá felismerő LKT gép. Turing-géppel viszont felismerhető lesz.
12
5. A reguláris nyelvek. Grammatika megadása. Véges állapotú automata, grammatikák és automaták megfeleltetése. Változatok (nem determinisztikus, determinisztikus, teljes) G ∑ , N , P , S P: minden szabály: A aB vagy
3-as osztály:
A a Megengedjük még az S
−szabály , de csak a mondatszimbólumra. Az üres szó akkor és csak akkor eleme L(G)-nek, ha P-ben van S szabály. Ezek a jobb-reguláris grammatikák. Ha minden szabály A Ba , akkor bal reguláris. Példa:
G{ a , b , c } , N ={ A , B , C , S } , P , S , ahol P : S cA , A aB , A aC , B cA , A a , B b , C c
Építsünk gépet, ami felismeri L(G)-t. Ötlet: Szabály alkalmazása: a baloldali nemtermálisból a jobboldal termálisa a jobboldal nemtermálisához, illetve befejezéshez / elfogadáshoz vezet. Ábrázoljuk irányított gráfban: Csomópontok: a nemtermálisok, és az elfogadó szimbólum: V Élek címkéje: termális Például: A aB -ből lesz. A G-hez tartozó gráf: Ez a gráf egy automatát ad meg, véges állapotú, nem determinisztikus, mert „A”-ból például „a” éllel 3 irányba mehetünk. A gráfban lehet kör. Ha van kör: rekurzív a nyelvtan. Amit kaptunk: egy nemdeterminisztikus véges automata megadása irányított gráffal.
: állapotmenetek, mozgási szabályok: A , a =B ; q 0 : kezdőállapot q 0 ∈Q F ⊆Q végállapotok, elfogadó állapotok. A
:Q×∑ ⇒ Q többértékű, nem determinisztikus
∗
w ∈ ∑ feldolgozása: M a q 0 -ból indul, olvassa w betűit, minden új olvasott betűre lép, valamelyik mozgási szabályt használva. Eljut egy q , w ' konfigurációhoz, ahol w' a w be nem olvasott része. M elfogadja w-t, ha q 0 -ból indulva a szó végén eljut egy F-beli állapotba (van ilyen feldolgozás). Jelölésben: Az M által elfogadott nyelv ∗
L M ={ w∣q0 , w M P , ∧P ∈ F } q 0 , w – kezdő konfiguráció ∗M - egymáshoz fűződő mozgások. P , végigolvasás konfigurációja. M nem fogadja el w-t, ha csak olyan mozgássorozat van, ami nem olvassa végig w-t, vagy ha végigolvassa, akkor nem elfogadó Fbeli állapotba jut Automata és jobb reguláris nyelv megfeleltetése: G – jobb reguláris nyelv – a példában konstruáltunk hozzá automatát. Általánosan: „A” szabályokhoz átmenetek: A aB <=> A , a = B A a <=> A , a =E , ahol E ∈ F , elég egy állapot egyben elfogadó állapot. Másként: S ,=E
q 0=S , S esetén S ∈ F . Vagyis a kezdő
A konstrukció speciális automatát eredményez: az egyetlen E elfogadó állapotból nem indul mozgás, a gráfban nem indul kivezető él belőle. Amennyiben S ∈P , ezt egy speciális mozgással, úgynevezett −mozgással adhatjuk meg: S-ből az üres jel (nem olvassuk az inputot) hatására léphetünk E-be.
13
Azt kaptuk Tétel: Minden G reguláris nyelvtanhoz létezik ekvivalens nemdeterminisztikus végállapotú automata, M, hogy L(G)=L(M). Igaz a tétel megfordítása is. Tétel: Minden M végállapotú nemdeterminisztikus automatához létezik ekvivalens reguláris nyelvtan, G, hogy L(M)=L(G). Bizonyítás: G megadása: Legyen M Q , , , q0 , F , akkor az ekvivalens G N , , P , S megadása: N =Q , vagyis a Q állapotai legyenek G nemterminálisai S=q0 , a mondatszimbólum legyen a kezdőállapot. P : három típusú szabályt képezünk: 1, P aq , ha p , a=q ∈ . Ezek a nem befejeződő mozgások 2, P a , ha p , a=q∈ , és még q ∈ F is teljesül
∑
3,
∑
q 0 , ha q 0 ∈F . Az egyetlen −mozgás. Az üres szó elfogadásához.
(Nézzük meg, milyen automatát kapnánk ebből a G-ből konstruálva! Nem egyezik a kiinduló M-mel!) Meg kell mutatni mindkét irányban az L(G)=L(M) teljesülését. A w szó elfogadását mind G-re, mind M-re a levezetést / mozgássorozatot szemléltető gráf egy útvonala adja. A konstrukciókat úgy készítettük, hogy G és M gráfja ugyanaz legyen. Balreguláris nyelvtanok: Szabályok: Automata mozgás – a gráfon visszafele: A Ba <=> B , a =A A a <=> q0 , a= A Lehet:
S <=> q0 ,=S
Ez az automata elfogadja w-t, ha van w útvonal
q 0 -ból S-be.
Tétel: A balreguláris grammatikák = jobb reguláris grammatikák. Biz.: A G balreguláris grammatikába M automata amire L(G)=L(M). Az M-hez létezik jobb reguláris G', amire L(M)=L(G'), tehát G-hez létezik ekvivalens jobb reguláris G' : L(G)=L(G'). Vegyes nyelvtan nem reguláris:
G N ={ X , S } , P , ∑ ={a , b} , S P={ S aX , X Sb , X b }esetén a L G ={a i bi ∣ i=1, ... , } nyelv nem reguláris.
Determinisztikus automaták: M determinisztikus, ha minden mozgása egyértelmű, azaz
A , a = B egyértelmű minden A∈Q , a ∈∑ −ra
Tétel: Minden nemdeterminisztikus automatához létezik ekvivalens determinisztikus automata. Biz.: (vázlatos) Az M Q , , , q0 , F -hez konstruálunk M det Q' , , ' , q 0 , F ' determinisztikus automatát, amelyen
∑
∑
L M =L M det . Q' megadása q ' ∈Q ' , q ' ⊆Q , az eredeti Q részhalmazai. ' ' ' ' Ha A , B∈Q , és ' q 1 , a=q2 ,akkor, ha A∈q 1 és A , a =B∈ , akkor B ∈q 2 . Példa:
Nemdeterminisztikus ⇒ Determinisztikus
A felépítés a q 0 -ból indul, rekurzívan megy előre. Az elfogadó állapot.
F ' elfogadó állapotok: q ' ∈Q ' elfogadó, ha van benne eredeti F-beli 14
A gráfban
(kettős körvonal) jelöli az elfogadható állapotot.
Teljes automata: Minden állapotban minden inputra lép. Állítás: Minden automata teljessé tehető. Ehhez csapdaállapotot vezetünk be: ha M-ben (A,a)-hoz nincs lépés, akkor M teljes -ben legyen
' T , a=T , ahol T a csapdaállapot. Legyen még M teljes −ben ' T , a =T , minden a ∈ ∑ -ra.
A determinisztikus és teljes automatákhoz egyértelműen (izomorfia erejéig [állapotok átnevezése]) szerkeszthető minimális automata, ami a legkevesebb állapotot használja. A következő átalakítási sorozat megadható:
M Determinisztikus Teljes Minimális : M min . L M = L M min .
Két automata akkor, és csak akkor ekvivalens, ha minimális automatájuk megegyezik. Ennek alapján automaták ekvivalenciája és ennek megfelelően reguláris grammatikák ekvivalenciája eldönthető. (A többi nyelvosztályra ez a tulajdonság már nem teljesül!)
15
6. Az önmaguk leírását elfogadó, illetve az önmaguk leírását nem elfogadó Turing gépek leírásai milyen nyelvosztályba tartoznak. A Turing gépek megállásának eldönthetetlensége. Ezek a 0-ás nyelvosztályba tartoznak!
Önmagukat elfogadó gépek: Tekintsük azoknak a gépeknek a leírásait amelyek elfogadják saját leírásukat. L01={ T ∣ T elfogadja T −t } . Állítás: az L01 nyelv elfogadásához létezik Turing-gép: - meghívja UT-t az T T inputra - Ha UT elfogadó választ ad, akkor T ∈ L 01 - Ha
T ∉ L 01 , akkor UT nem adhat elfogadó választ, vagy nem elfogadó állapotban áll meg, vagy nem áll meg.
Önmagukat nem elfogadó gépek: Borbély paradoxon: Athén borbélyának megparancsolják, hogy mindenkit, aki nem maga borotválkozik, borotváljon meg. Ki borotválja a borbélyt? Tekintsük azoknak a gépeknek a leírását, amelyek nem fogadják el saját leírásukat: L02={ T ∣ T nem fogadja el T −t } . Állítás: Az L02 nyelvhez nem létezik felismerő Turing-gép. (Az nincs eljárás, ami felismeri)
L02 nyelv nincs benne a 0-s nyelvosztályban, a Church-tézis szerint
Biz.: Indirekt módon tegyük fel, hogy a
T 02 gép felismeri az L02 nyelvet. Mit fog csinálni TU az T 02 T n bemenetre: - Ha elfogadja, az hiba, mert akkor egyrészt T 02 ∈L 02 lenne, hiszen T 02 felismeri T 02 -t. Viszont akkor T 02 felismeri saját leírását, tehát nem lehet T 02 ∈ L02 . - Ha nem fogadja el, akkor T 02 nem fogadja el saját leírását, tehát T 02 ∈ L02 . Viszont akkor T 02 -nek el kellene fogadnia T 02 -t. Ellenmondásra jutottunk! ( T 02 a „borbély”)
A megállási probléma eldönthetetlensége: Tétel: Nem létezik olyan Turing-gép, amely minden T w bemenetre eldönti, hogy a T gép a w bemenetre megáll-e. Biz.: Indirekt módon, tegyük fel, hogy létezik ilyen T ∞ gép. Akkor konstruáljuk a következő gépet L02 felismeréséhez: - Meghívja a T ∞ gépet az T T bemenetre. - Ha T ∞ azt válaszolja, hogy T az T -n nem áll meg, akkor T ∈ L 02 elfogadást nyert. - Ha T ∞ azt válaszolja, hogy T az T -n megáll, meghívja UT-t az T T bemenetre. UT nyílván megáll, és
T ∈ L 02 elfogadást nyert. - Egyébként, ha UT elfogadó állapotban állt meg, akkor T ∉ L 02 nyert elfogadást, vagyis Mivel az L02 nyelvhez nem létezik felismerő Turing-gép, ellentmondásra jutottunk. - Ha UT nem-elfogadó állapotban állt meg, akkor
T ∈ L 01 .
A megállás eldönthetetlenségéből igen sok eldönthetetlen probléma következik. A 3-as, 2-es, és 1-es nyelvosztály nyelveire a nyelvhez tartozás eldönthető, pontosabban, azt is igazolni tudjuk véges lépésben, hogy ha egy mondat nem eleme a nyelvnek. A 0-s nyelvosztály esetében az nem mindig teljesül.
Általános eldönthetetlenségi tétel Turing-gépben: a Turing-gépeknek egy részhalmaza, amit valamilyen tulajdonsággal adunk meg. Az U-nál használt T i rendezés szerint az A={i ∣ T i ∈ } halmaz akkor és csak akkor rekurzív ( tulajdonság eldönthető), ha az üres
Legyen
halmaz, vagy az összes Turing-gép.
16
7. Környezetfüggetlen nyelvek. A grammatika megadása. A levezetési fa és szerepe. A kettős pumpálási lemma. (Nagy Bar-Hillel lemma) A Chomsky hierarchiában a 2-es osztály. Def.: A G= N , , P , S grammatika 2-es osztályú, más néven környezetfüggetlen, ha a levezetési szabályok alakjai:
∑
A w , ahol A∈ N és w ∈ N ∪∑ , egyetlen kivétel az S
−szabály.
Megjegyzés: kiküszöbölhető, hogy a mondatszimbólum jobboldalon előforduljon, ugyanúgy, mint a reguláris nyelveknél. Egy mondat levezetését levezetési fán ábrázolhatjuk. (Reguláris nyelv esetében a levezetési út volt). Def.: A G egy levezetési fája: a, gyökere az S mondatszimbólum b, ha A∈ N -re egy A-val jelölt csúcs leszármazottjai balról jobbra
B1, B 2, … , B k , ahol Bi ∈ N ∪∑ , akkor
létezik P-ben A B 1, B2 ,... , B k szabály. A levezetési fa eredménye az a szó, ami a levelek balról jobbra végigolvasásával adódik. A levezetési fában akkor ér véget, ha minden levél terminálist tartalmaz. Példa: kifejezések: E – kifejezés, expression T – tag, term F – tényező, faktor
G : { E ,T , F } ; {a , ,∗, , } , P ; E P : E ET ∣T ; T T ∗F∣F ; F E ∣a
aa∗a levezetése :
Másik szabályrendszer:
P ' : E EE ∣ E∗E ∣ E ∣ a aa∗a levezetései :
Tétel: Környezetfüggetlen nyelvek is levezetési fák. A G környezetfüggetlen grammatika L(G) nyelvére teljesül, hogy w ∈ LG , akkor és csak akkor, ha létezik G-nek levezetési fája, aminek levelei w-t adják balról jobbra olvasva. Biz.: Terjesszük ki a levezetést mondatformákra. Nem követeljük meg, hogy a leveleken csak terminálisok álljanak. A fa által levezetett mondatformát a levelekben álló szimbólumok balról jobbra olvasásával kapjuk.
17
A tétel átfogalmazása: egy mondatforma akkor és csak akkor vezethető le, ha létezik levezetési fa, amelynek levelei balról jobbra a, Levezetéshez fa építése: S ⇒ 1 ⇒ …⇒ n levezetés. Teljes indukcióval: – n=0 eset : csak S lehet, a fa csak az S gyökérből áll. – 1 -et S 1 ∈ P alkalmazásával kapjuk. Legyen 1= A1 A2 … An , akkor a fa: n=1 eset :
–
-t adják.
indukciós lépés : S hosszú levezetésre igaz az állítás, a levezetési fa leveleiben S van balról jobbra. Az S1 ' '' hosszú levezetésben S ⇒ S 1 egy A B 1 … Bm ∈P alkalmazásával kaptuk, ahol S=S A S alakú, és A-ra alkalmazzuk a szabályt. Az új fa:
b, Levezetési fához levezetés rendelése: Az indukció a levezetési fa belső pontjainak száma szerint történik. – n=0 eset : az egyetlen S pontból álló fa csak akkor levezetési fája G-nek, ha S ∈ P. – n=1 eset : Csak akkor levezetési fa, ha S A1 A2 ... An ∈ P. A levelek olyan belső ponthoz kapcsolódnak, amelynek levezetési szabálya a leveleket adja. A levelek mondatformát adnak.
–
Indukciós lépés : s belső pontra igaz az állítás, a levelek mondatformát adnak, és ha a B1 , B 2 , … , B k levelek az A belső ponthoz kapcsolódnak balról jobbra, akkor A B 1 B 2 … B k ∈ P.
Tekintsünk egy S+1 belső pontból álló levezetési fát, és ebben leveleknek B1 ,… , Bm sorozatát, amelynek balról jobbra az A belső pont gyerekei. A levezetési fa tulajdonsága miatt A B 1 B 2 … B m ∈ P teljesül. Elhagyva „A” leveleit, „A” lesz a megmaradó fa levele, és a megmaradt fa is levezetési fa. Belső pontjainak száma S. Levelei az 1 A 2 mondatformát adják. Az A B 1 B 2 … B m ∈ P alkalmazásával 1 A 2 ⇒ 1 1 2 … m 2 levezetését kapjuk, ami éppen a kiinduló fa leveleinek balról jobbra felsorolása.
18
A kifejezések példa két szabályrendszere közül P szerint egyetlen fa felel meg aa∗a levezetésére, a P' szerint két különböző fa is megfelelt. Def.:Egyértelmű grammatika: minden levezetéshez egyetlen levezetési fa tartozik. Létezik bizonyíthatóan nem egyértelmű nyelvtan; pontosabban olyan nyelvtan, amihez nem létezik vele ekvivalens egyértelmű nyelvtan. (lásd: Bach Iván könyvének 83.oldala) Def.: Egy L környezetfüggetlen nyelv egyértelmű, ha megadható G egyértelmű környezetfüggetlen nyelvtan, amire L=LG . Tétel: A környezetfüggetlen nyelvek egyértelműsége eldönthetetlen. (Nem bizonyítjuk).
Nagy Bar-Hillel lemma (vwxyz szabály, kettős pumpálás): Mielőtt a felismerő gépre térnénk, a reguláris nyelvek pumpálási tulajdonságainak megfelelő nagy Bar-Hillel lemmát, másként a kettős pumpálást, vagy vwxyz szabályt mutatjuk meg. Legyen a G környezetfüggetlen nyelv terminálisainak száma n, a szabályok jobboldalának hossza legfeljebb k. Ha w ∈ LG , és hosszabb k n 1 -nél, akkor w=vwxyz alakba írható, és v w i x y i z ∈ LG , és y legalább egyike nem üres.
i=0,1 , .. , és w
Biz.: w levezetési fáján szemléltetve: A méret miatt van a levezetési fában S-ből egy a terminálisig legalább n1 hosszú út. Ezen egy nemterminális, A, ami legalább kétszer előfordul. Az A alatti részfákat nézzük: egymás helyére írhatók. Következmény: Az L={ x n y n z n ∣ n=1,2 , ... } nyelv nem környezetfüggetlen. A kettős pumpálást nem teljesíti. Az L nyelv előáll az alábbi két környezetfüggetlen nyelv metszeteként: ={a , b , c } , S közös. N ={ S , A , B} ;
∑
G1 N , ∑ , P 1 , S , P 1={ S AB , A aAb , A ab , B cB , B c } n n m L1= LG 1={ a b c ∣ n≥1 , m≥1 } , G2 N , ∑ , P 2 , S , P 2={ S AB , B bBc , B bc , A Aa , A a } , n m m L 2=L G 2 ={a b c ∣ n≥1 , m≥1} , L=L1∩ L2. . Tehát két környezetfüggetlen nyelv metszete nem mindig környezetfüggetlen.
19
8. Milyen műveletekre zártak, illetve nem zártak a környezetfüggetlen nyelvek. A tartalmazási kérdés eldönthetősége.
A környezetfüggetlen nyelvek néhány fontos tulajdonsága: 1, A kettős pumpálásnál láttuk, hogy nem zárt a nyelvek metszetére nézve: L1={a n bn c m ∣ n≥1, m≥1 } m n n L 2={a b c ∣ n≥1, m≥1 } , környezetfüggetlenek L=L1∩ L2= { a n b n c n ∣ n≥1 } , nem környezetfüggetlen. 2, Ha L1 és L2 környezetfüggetlenek, akkor L1∪ L2 is az. Az unióra zárt. Biz.: azonosan megy, mint reguláris nyelvekre: L1= LG1 , L2 =LG 2 , és a G1 ,G 2 grammatikákban minden nemterminális legyen különböző, a mondatszimbólum ne szerepeljen jobboldalon. Az L=L1∪ L2 G grammatikáját a két szabályrendszer egyesítésével, és a mondatszimbólumok azonossá tételével kapjuk.
G1 N 1 , ∑ , P 1 , S 1 , G 2 N 2 , ∑ , P 2 , S 2 , N 1∩N 2=0 , G N , ∑ , P , S = N = N 1∪N 2−{ S 1 }−{ S 2 }∪{ S } , ' ' P=P 1∪P 2 , ahol P 'i -t úgy kapjuk P i -ből, hogy S i helyére mindenütt S -et írunk.
Formálisan:
3, A komplementerképzésre nem zárt. Biz.: Ha zárt lenne, akkor L1 ∪L2 =L1∩L 2 is környezetfüggetlen lenne. 4, A sorozatra nézve zárt. A 2, alatti G1 ,G 2 -re: G={ ∑ ,{ S } ∪N 1∪N 2 , P={ S S 1 S 2 }∪P 1∪P 2 , S } L G =LG 1 LG 2
,
5, Tranzitív lezárás nem vezet ki. L=LG , és G-ben S ne legyen jobboldalon. L∗=L G∗ , ahol G N , ∑ , P , S . ∗ G = { N , ∑ , P∪S SS ∪S , S } (Az S az ∈ L∗ miatt szükséges. Felesleges, ha benne van P-ben.) A nemdeterminisztikus veremautomatákhoz nem lehet minden esetben ekvivalens determinisztikus automatát megadni. Ez lényegesen eltérő tulajdonság a véges állapotú automatáktól. Részosztály: determinisztikus veremautomaták, ennek megfelelően a determinisztikus környezetfüggetlen nyelvek. (L determinisztikus, ha van determinisztikus PM, amire L=L PM . ) (A determinisztikus környezetfüggetlen nyelvek zártak a komplementerképzésre, de nem zártak a metszetre és az unióra. Valódi részhalmazt képeznek a környezetfüggetlen nyelveken belül)
Tartalmazási kérdés eldönthetősége: 1, Ha w ∈ LG , akkor létezik véges levezetése, ami véges lépésben megtalálható. 2, Ha w ∉ LG : A környezetfüggetlen nyelvek levezetéseiben a mondatformák nem tudnak csökkenni. (Kivétel az S -szabály). Egy n hosszú mondatformából nem lehet n-nél rövidebb mondatot levezetni. Tehát, ha ∣w∣=n , w hossza n, akkor elég az n hosszú mondatformákig ellenőrizni a levezetéseket. Véges sok van belőlük.
Pumpálási lemma – Bar-Hillel lemma: q 0=S is állapotok között van!). Lemma: =a1 a 2 ... a m ∈ L , és m ≥n , akkor =uvw alakú, és ∣v∣ ≥1 , ∣uv∣ ≤n , ( ∣x∣ : az x hossza!) és uv i w ∈ L , minden i=0,1,2 ,... esetén. (Jelölés: v i : a v egymás utáni i-szer, i-szeres konkatenáltja saját
Legyen L reguláris nyelv. A felismerő M véges automata állapotainak száma legyen „n” (
magával). Biz.: A felismerő automata gráfjában csak n pont van, ezért az −t felismerő bejárás m ≥n miatt legalább n+1 pontot érint: a a a q 0 1 P i1 2 Pi2 … P imax m E , ezért P i1 , … , Pimax között van két azonos: P ij =P ik : ezt szemlélteti a csomópont a gráfban. A -ig elfogadott szó: u ; a körön elfogadott szó: v ; a -után elfogadott szó: w.
Minthogy az elfogadó út lehet: - a kör kihagyása uw elfogadása - a kör bejárása i-szer uv i w elfogadása Következmény:
G= N ={ S , X } , ∑ ={a ,b } , P={ S aX , X Sb , X b } , S grammatika által meghatározott nyelv: L G ={a i bi } , i=1,.. nem reguláris
Ha az lenne: valamilyen n-re teljesülne a pumpálási lemma. w=a m b m -ben valahol van a v szó. - Ha v csupa a, vagy b lenne, elhagyva az a-k és b-k száma nem egyezne. - Ha v=a i b j , akkor m−i i j m – j és
w=a a b b , m−i i j k m – j is L(G) eleme lenne, ami nyilván nem z =a a b b a n b n alakú.
Megjegyzés az −szabályhoz : Ha az S szabályt tartalmazza egy G grammatika, akkor nem. Megengedhető lenne tetszőleges A szabály, de ez kiküszöbölhető: { B aA , és A } helyett a { B aA , és B a } szabályokat vehetjük.
{}∈ LG , egyébként
A mondatszimbólum (S) ne szerepeljen a jobboldalon: G-hez G' , amiben S nem szerepel jobboldalon: G'-ben bevezetünk egy új S' állapotot, és ha G-ben A aS volt, akkor G'-ben A aS ' lesz. Ezen felül G-ben minden, S B -t megismételünk G'-ben S ' B szabályban is. ( S B is marad G'-ben!). L(G)=L(G')
Műveletek nyelvekkel: L , L1 , L 2 nyelvek ∗
L =∑ − L:
∑
felett (Halmazok!)
a komplementer
L1∪ L2 - unió L1∩ L2 - metszet L1⋅L2= L1 L 2 - a konkatenált nyelv, w ∈ L1 L 2 , ha w= ahol ∈ L1 és ∈ L2 . Ez a „szorzás” művelet. Li - i-szeres konkatenált, „hatvány”. L0 ={} - 0-adik hatvány, a szorzás egységeleme. ∞ ∗ L = ∪ Li - A tranzitív lezárt ( ∑∗ jelölés ennek felel meg) i=0 21
L
∞ = ∪ L i - (Ha ∈ L , akkor L =L∗ , ha nem, akkor ∉L ) i=0
Kérdés: a reguláris nyelvek halmaza melyik műveletre nézve zárt? Válasz: mindegyikre Bizonyítás: azt az alakot nézzük, amelyikben a bizonyítás szemléletesebb. Feltesszük, hogy L , L1 , L 2 reguláris nyelvek. Bizonyítjuk, hogy a belőlük képzett nyelv is az.
1,
L1∪ L2 : Legyen a két grammatika G1 és Feltesszük, hogy S nem szerepel a jobb oldalon.
G2. Csak a a mondatszimbólumuk legyen közös, S, N 1∩N 2={ S } .
G L ∪ L ={ N 1∪N 2 , ∑ , P={ P1 ∪P 2 } , S } 1
2
G1 automatája M 1 , G2 -é pedig M 2. Egyik se tér vissza a q 0=S kezdőpontba. Egyesítésük éppen G L ∪ L automatáját adja. Egy elfogadás vagy M 1 gráfját járja be, vagy M 2 -ét. Vagyis vagy L G 1 , vagy 1 2 L G 2 mondatát fogadja el.
Legyen
2, A komplementer, L : L-nek vegyük egy teljes, determinisztikus automatáját. Cseréljük fel benne az elfogató és a csapda állapotok szerepét. Az így kapott automata a komplementer nyelvet fogadja el. 3,
L1∩ L2= L 1∪ L 2 - de Morgan szabály. Közvetlen Bizonyítás: M 1 és M 2 állapotaiból képzett párok lesznek a metszetet előállító automata állapotai: M 1 Q1 , ∑ , 1 , q 0 , E 1 átmenet M 2 Q 2 , ∑ , 2 , q 0 , E 2 , P 1 q1 a P 2 q 2 , ha 1 P 1 , a =P 2 ∈1 , és 2 q1 , a =q 2 ∈ 2 - Elfogadó állapot: ha mindkettő elfogadó.
4, Konkatenáció:
L1 , L2−höz jobboldalon.
G1 N 1 , ∑ , P 1 , S 1 és G2 N 2 , ∑ , P 2 , S 2 , N 1∩N 2=0 , és mondatszimbólum nincs
G1∪G 2={ N 1∪N 2 , ∑ , P=P 1∪ P 2∪{ A aS 2 ∣ A a ∈ P1 } , S 1 } Szavakban: ha G 1−ben A a szabály van, akkor ez folytatjuk egy G 2 −beli mondattal, vagyis mondatszimbólummal: A aS 2 szabályt képezzük. M 1 és M 2 gráfjával szemléltetve: M 1 egyetlen elfogadó állapotát egyesítjük M 2 kezdő állapotával.
5, Tranzitív lezárás:
L , G N , ∑ , P , S , és P-ben S nem szerepel jobboldalon. L∗−hoz G ∗ : - minden A a ∈P -hez még hozzávesszük A aS szabályt, - ha S nincs P-ben, hozzávesszük G ∗−ban. ( Ez hozza be L∗={ } -t.)
Reguláris halmazok – reguláris kifejezések: Újabb módszer (algebrai jellegű) nyelv definiálására: műveletek segítségével építjük fel alaphalmazokból. Reguláris halmazok felett: Alaphalmazok: - 0 : üres halmaz - {} : üres szóból álló halmaz
∑
-
{ a } , ahol a ∈ ∑ ; egyelemű halmazok, egy betűből álló szavakból. (Szingletonok) 22
Halmazképzés: Ha P, Q reguláris halmaz, akkor az alábbiak is reguláris halmazok: - PQ : unió, két halmaz egyesítése - PQ : (konkatenáció) a P⋅Q – szorzás műveletek - P∗ : Tranzitív lezárt Műveleti precedencia: ∗ , ⋅ , . Ezeket lehet zárójelezni. Példák: ABC D b∗ a bab∗ a ∗ - páratlan sok „a” van benne, „b” tetszőleges helyen lehet. ∗
∗
bab a
- páros sok „a” van benne (lehet 0 is!), „b” tetszőleges helyen lehet.
Reguláris kifejezés: halmaznevekből, mint „konstansokból” és változókból épül fel a műveletekkel. Pl.: x 2 x , ahol , , konstans halmaz, x halmazváltozó. A kifejezések változói reguláris halmazokat vesznek fel behelyettesítési érték gyanánt. Az előző kifejezés x={a} helyén a 2a lesz.
, konstans halmazok, {}∉ legyen. x= x megadása: x=∗ - x= nyílván megoldás, kezdő megoldás, x 0 0 1 n ∗ x 0== , ebből x= x = x 0= , lehetséges megoldás, x 1= , … , x n= ⇒ x= a
Egyenletek is megadhatók:
megoldás. Az
x= x „lineáris” egyenlet mintájára lehet lineáris egyenletrendszert megadni, az is megoldható.
23
10. Nem determinisztikus Turing-géphez determinisztikus Turing gép szerkesztése.
Nem determinisztikus determinisztikus Tetszőleges T N nemdeterminisztikus Turing-géphez létezik (készíthetünk) vele ekvivalens T D determinisztikus Turing-gépet. Konstrukció alapötlete: a T N gép n hosszú lépéssorozatának mindegyikét lejátsszuk determinisztikusan a w inputra. Ha van közöttük elfogadó, kész; ha nincs, folytatjuk az n+1 hosszú lépéssorozatokkal. Szükséges szubrutinok: 1. A következő n hosszú lépéssorozat előállítása 2. A lépéssorozat végrehajtása, majd az induló szalagállapot visszaállítása. 3. n növelése. Legyen a feldolgozandó szó w=1 2 … k . A determinisztikus gép szalagján kettőzzünk meg w jeleit, két speciális jel (#) között:
A P N gép egy lehetséges determinisztikus lefutását csak az egyik i −n hajtjuk végre. A # jeleket a végrehajtás átugorja. A visszaállítás (sikertelen futás) után a # előtt, illetve a jobboldali után mindent felülír egy speciális ürest jelző szimbólummal, i−ket újra kettőzi
T N : n lépéses lefutásainak száma, n exponenciális függvénye. T D : Ezért az n hosszú lefutásokra exponenciálisan sok lépést fordít. A szalagon a # jelek előtt, illetve után, ugyanannyi cellát használ, mint T N .
24
11. Nyelvek (függvények) időbonyolultsága, bonyolultsági osztályok. (Determinisztikus, és nem – determinisztikus bonyolultság.)
A bonyolultságelmélet elemei: A Turing-gépek az algoritmusok bonyolultságának mérésében is jó eszköznek bizonyultak. Sokféle mérési lehetőség, mérőszám van, de a legfontosabb osztályok nem függenek a mérőszámtól. A Turing-gépek minden más gépet jól szimulálnak, hatékonyságromlás nélkül! Nézzük meg mi jellemzi egy T Turing-gép lefutását egy n hosszú w adaton. Mi jelentene költséget valós fizikai megvalósításnál? - A mozgás, a lépések száma, vagyis az idő. - A tároló mérete, a felhasznált cellák száma, vagyis a tár. Ha a lefutás „t” időt és „s” cellát használt, időköltsége t-vel, tárköltsége s-sel arányos. (Ha nem ér véget a futás, a költség végtelen). Kérdés: - a T gyors, vagy lassú megoldást jelent? - a T takarékosan használja a szalagot? A válasz nem egy w-re, hanem a w, az input hosszához viszonyítva adható meg. Egy T Turing-gépre nézve vizsgálhatjuk, hogy az input méretének függvényében van-e időkorlátja, és az milyen függvény, illetve van-e tárkorlátja, és az milyen függvény. Először a determinisztikus gépeket használjuk. Def.: A T Turing-gép időkorlátos, és időkorlátja t n , ha az „n” hosszú inputokon legfeljebb t n . A t n függvény monoton növekvő értékű függvény.
t n időt fut. Lépésszám legfeljebb
Nyelvek bonyolultsági osztályai: A TIME ( t(n) ) osztály: t n:
t : N N monoton növekvő függvény. ∗
TIME t n:={ L⊆∑ ∣ L felismerhető 0t n időkorlátos T Turing−géppel.} A O -nagy ordó- jelentése: az
f : N N függvény Ot n , ha létezik c0 konstans, vagy
f n≤c t n .
A legegyszerűbb osztály: a lineáris idő, t n=n TIME n Reguláris nyelvek (3-as nyelvosztály) ide tartoznak. Magyarázat: az L reguláris nyelvhez létezik determinisztikus (és teljes) véges állapotú automata, amely felismeri. Ez egyszeri végigolvasását igényli az inputnak. Illik tudni, hogy a rendezés, n elem rendezése nlogn időbonyolultságú. Fontos osztály a polinom időben megoldható feladatok osztálya. Ezek a „kezelhető” feladatok. Jele:P P= ∪k≥1 TIME n k . (Szokták PTIME-ként is jelölni) Ide tartoznak a környezetfüggetlen nyelvek. Kiszámítható függvények bonyolultsága A Turing-gépeket átalakítóként használva függvényekre is értelmezhető az idő- és tár-korlátosság. Megkülönböztetésként az F betűt szokták az osztály elé tenni. Például: Polinom idejű osztály FP :={ f : N N függvény∣ f −hez létezik kiszámító T Turing −gép , és T időkorlátja valamilyen k ≥1 -re.}
t n≤O n k ,
Bonyolultsági osztályok nemdeterminisztikus Turing-gépek szerint: A nemdeterminisztikus gépek szerinti osztályokat N kezdőbetűvel jelöljük. ∗
NTIME t n:={ L⊆∑
∣ létezik L−hez nemdeterminisztikus felismerő gép Ot nidőkorláttal.}
Láttuk, hogyan készíthetünk egy nemdeterminisztikus Turing-géphez ekvivalens determinisztikus gépet. Az idő a determinisztikus gépen exponenciálisan megnő. Ezért NTIME t n ≤TIME expt n
25
12. Nyelvek (függvények) tárbonyolultsága, bonyolultsági osztályok. (Determinisztikus, és nem – determinisztikus bonyolultság.) Def.: A T Turing-gép
S n tárkorlátos, ha az n hosszú inputokon legfeljebb S n cellát használ a munkaszalagon.
Mire jók ezek a tárkorlátos gépek? Feladatok bonyolultságát tudjuk jellemezni a tárkorlátos gépekkel. Legyen például L egy nyelv, és T egy felismerő Turing-gépe. Ha T t n időkorlátos, és s n tárkorlátos, akkor az L nyelv legfeljebb ilyen bonyolult. (Pontosabban fogalmazva: legfeljebb ilyen időbonyolultságú, illetve ilyen tárbonyolultságú.) Megjegyzés: 1, A két korlátfüggvény között s n≤t n nyilván teljesül, hiszen minden cella elérése legalább egy lépés. 2, A szalag-ábécé elemszáma befolyásolja t n és s n függvényeket, de csak konstans szorzó eltérést okoz. A konstans szorzóval való eltérést a bonyolultság mérésénél nem vesszük figyelembe. Gyakorlatban fontosak az alacsony bonyolultságú nyelvek, feladatok. Fontos tudni, melyek az alacsony osztályba tartozó nyelvek, melyek a gyakorlat számára kezelhetetlenül bonyolult feladatok. Hasonlóan definiálhatók a tárbonyolultság szerinti osztályok:
SPACE S n:=L ∣ Az L nyelv felismerhető O S n tárkorlátos T Turing −géppel. L=SPACE logn.
A legegyszerűbb osztály: a logaritmikus táron eldönthető nyelvek: Fontos osztály a polinom tárral felismerhető nyelvek osztálya: k
PSPACE= ∪k≥1 PSPACE n Kiszámítható függvények bonyolultsága A Turing-gépeket átalakítóként használva függvényekre is értelmezhető az idő- és tár-korlátosság. Megkülönböztetésként az F betűt szokták az osztály elé tenni. A tárbonyolultság esetén az input és az eredmény méretét sem szokták nézni, csak a munkaszalag mérete fontos.
FSPACE log n FSPACE n ∞ FSPACE= ∪ FSPACE n k . k =0
A rendezés az összehasonlítások száma alapján
FTIME n logn -ben van.
Bonyolultsági osztályok nemdeterminisztikus Turing-gépek szerint: A tár-bonyolultság: ∗
NSPACE S n :={ L⊆∑
∣ létezik L−hez nemdeterminisztikus felismerő gép O S n tárkorláttal.}
A determinisztikus gép konstrukciója csak polinom méretű tár-többletet igényel. Ezért
NPSPACE =U k ≥1 NSPACE nk =PSPALE A polinom-tár osztályok egybeesnek. Nevezetes osztályok:
NL= NSPACE logn k NP =U k ≥1 NTIME n - nemdeterminisztikus polinom-idő
Az 1-es nyelvosztály, a környezetfüggő nyelvek osztálya a binárisan korlátozott Turing-gépekkel ismerhető fel. Tehát: ∗
{ L⊆∑ ∣ L környezetfüggő }≤NSPACE n .
Fordítva is igaz,
NSPACE n=környezetfüggő nyelvek osztálya
A nyelvosztályok jellemzése: 3-as: TIME n , SPACE n konstans tár 2-es: PTIME , SPACE n 1-es: NSPACE n 0-ás: totális rekurzív függvény , parciális rekurzívan
26
felsorolható függvény.
13. Nyelvek és nemnegatív egész számokból álló halmazok megfeleltetése. Rekurzív (eldönthet halmazok), rekurzívan felsorolható halmazok. Turing-gépek, mint átalakítók. Kiszámítható függvények.
A reguláris halmazok és a reguláris nyelvek viszonya: Tétel: A reguláris nyelvek megegyeznek a reguláris halmazokkal: minden reguláris halmazhoz létezik reguláris grammatika, és minden reguláris grammatika reguláris halmazt generál. a, Reguláris halmaz, reguláris nyelv: - Az alaphalmazokhoz nyilván van reguláris nyelv. - A műveletek ,⋅,∗ nem vezetnek ki a reguláris nyelvekből. b, Reguláris grammatikához reguláris halmaz megadása Megjegyzés: a reguláris halmazokat képző műveletek monoton növekvőek, a reguláris nyelvek viszont a nem monoton komplementer képzésre is zártak. Mégis megegyezik a két nyelvcsalád. A konstrukciót az automata gráfjának bejárásán szemléltetjük. A gráf körei egy szó pumpálását jelentik, ami tranzitív lezárásként konkatenálható. Vegyük a G reguláris grammatika M automatáját. Legyen egy „v” út q 0 -ból F-be ( q 0 : kezdő állapot; F: elfogadó állapot), hagyjuk ki belőle a hurkokat, kapunk egy egyszerű, ismétlődés nélküli utat, ami elfogad egy „w” szót. A „w” szó útvonalát egyenesként rajzolva a „v” útvonala ennek pontjaiba kapcsolódó hurokutakból áll.
v 1, v 2, … , v k . A w=w1 v 1 w2 … v k w k1 alakba írható fel, ahol ∣v i∣≥1 , i=1, … , k . ∗ ∗ ∗ Az egyszerű w szóhoz, és v-hez a v 1, … , v k pumpálásával az =w1 v 1 w 2 v 2 … v k w k 1 reguláris halmazt kapjuk, ami A hurkokhoz tartozó szavak
L(G)-ben benne van. Ezt az észrevételt használjuk L(G) felépítéséhez. Lehetséges, hogy w útvonalában egy pontban több kör is kezdődik. Például a több kört fut be, és az egyes szavak a körök mentén u 1, u 2, .. , u m Akkor
v1
v ∗1 helyett az u1 u 2…u m∗ pumpálása is L(G)-ben marad.
Folytassuk a konstrukciót a v i , illetve u j típusú körökhöz tartozó szavak elemzésével, második mélység. Mindegyik felbontható egy ismétlődés nélküli körre, és azon elhelyezkedő körökre. Tehát v i , illetve u j is meghatároz egy-egy további reguláris halmazt, ami helyükre írható. Így tovább, amíg van még az i-edik mélységben olyan körút, ami nem egyszerű. Az i -edik mélységű kör kezdőpontja egy i−1 -edik mélységű egyszerű kör belső pontja, és az i−1 -edik mélységű kör kezdőpontját az i -edik mélységű kör nem tartalmazhatja. Felrajzolva a körök kezdőpontját mélység sorrendben:
Tehát a mélység nem lehet nagyobb, mint a gráf pontjainak száma. Következmény: A w ∈ LG mondatokhoz így felépíthető reguláris halmazok száma véges. Tehát minden egy ilyen reguláris halmaznak. Ezeknek a reguláris halmazoknak az uniója megegyezik L(G)-vel.
, [0,1]∗ , és az N ={0,1 ,2 ,... } halmazok között.
⇔ [ 0,1]∗ ⇔ N
A megfeleltetéssel egy
∗
L⊆∑
nyelvhez
A⊆ N részhalmaz rendelhető. Az A egész számokból álló halmaz örökli L
eldönthetőségi tulajdonságait. Legyen L=LG , G tetszőleges a 0-s osztályból. Az L nyelv elemeit fel tudjuk sorolni w 1 , w 2 , w 3, ... módon: Vesszük a G-hez tartozó (valamelyik) T Turing-gépet, futtatjuk az alábbi táblázatnak megfelelően, a mellékátlón látható lépésszámokat használva: az első n input szón n lépést hajtunk végre:
Amit T felismer, ebben a sorrendben egyértelműen mindent megkapunk. Ahol T nem áll meg, a sor végtelen lesz.
Az ilyen tulajdonságú halmazokat rekurzívan felsorolható halmaznak nevezzük. Az előző gondolatmenettel könnyen belátható, hogy egy A⊆ N halmaz akkor és csak akkor rekurzívan felsorolható, ha minden x ∈ A esetén véges lépésben igazolható, hogy x az A eleme (a lépésszám függ x-től!). A 0-s nyelvosztály esetén bizonyítottuk egy nyelvről, hogy a komplementere nem rekurzívan felsorolható: Az L01 : „saját leírásukat felismerő nyelvek leírásai” nyelv rekurzívan felsorolható, de komplementere: L02 : „saját leírásukat nem felismerő nyelvek leírásai” nyelv nem ismerhető fel, nem rekurzívan felsorolható. Rekurzív nyelv (halmaz): Az L rekurzív, ha rekurzívan felsorolható és (
∗
L =∑ − L
is rekurzívan felsorolható.
A⊆ N rekurzív, ha A rekurzívan felsorolható és A=N − A is rekurzívan felsorolható.) Ekkor w ∈ L eldönthető.
Ha L rekurzívan felsorolható, de nem rekurzív, akkor w ∈ L nem dönthető el. Az L nyelvhez (A halmazhoz) tartozást eldönthetetlennek mondjuk, ha vagy L, vagy felsorolható.
L (vagy mindkettő) nem rekurzívan
Példa: sem a nyelv, sem a komplementere nem rekurzívan felsorolható:
L012 ={ T ∣ T ∈ L 01 vagy T −ben az elején álló 1−esek száma páros} L021 ={ T ∣ T ∈ L 02 vagy T −ben az elején álló 1−esek száma páratlan }
L 012= L021 Megjegyzés: A rekurzív felsorolhatóságot (ha igaz) általában nem nehéz bizonyítani. Cáfolni általában nehéz.
Turing-gép, mint átalakító: Szalag kezdő állapota: input adat Elfogadó állapotban a szalag tartalma: output adat, eredmény. Egy T Turing-gép egy ∗ ⇒ ∗ leképzést ad meg. Ha T nemdeterminisztikus, a leképzés többértékű. Ha T determinisztikus, a leképzés egy kiszámítható függvényt jelent. Ha T minden bemenetet (inputot) elfogad, totális függvényt kapunk. Egyébként parciális a függvény: ahol T nem áll meg, ott nincs meghatározva. Pl.: ha ={ 0 ,1 , bl } , akkor a 0,1∗ 0,1∗ függvényeket az egész számok bináris kódolásával megfeleltethetjük az egészeken értelmezett egész értékű függvényeknek.
28
14. Véges ÁBC feletti nyelv fogalma. Grammatika megadása. A grammatika által generált nyelv. Nyelv: Adott véges ABC (alfabéta) véges szavainak részhalmaza. A részhalmaz elemei a nyelv mondatai. A grammatika a szerkezetet, a szintaxist adja meg, nem pedig a jelentést, a szemantikát. Formális nyelvek – grammatikák: : a jelek, karakterkészletek véges halmaza. Ez a nyelv ABC-je (alfabéta).
∑ ∗ ∑: i ∑:
A
∑
-ból alkotott véges sorozatok halmaza. Számossága: megszámlálhatóan végtelen.
a pontosan i hosszú sorozatok, i= 0, 1, 2, … ∗
∑
∞ =∪
i
∑
, üres szó.
I=0 eset: az üres sorozat. Jele:
i=0
∑
feletti nyelv: L, ahol
∗
L⊆∑
;
∗
∈∑
a nyelv egy mondata, ha
∈L
Speciális nyelvek::
L0 =0 0 : üres halmaz L ={ } , az üres szóból álló nyelv
Grammatikák – nyelvtanok: A nyelv mondatainak speciális részeit különítjük el. Ezeket speciális (új, nem megadjuk az építkezés szabályait.
∑ −beli
) szimbólumokkal jelöljük, majd
Def.: A G grammatika egy négyes: G= N , , P , S , ahol N : a nyelvi szimbólumok, más néven nemtermálisok véges halmaza P : a levezetési (produkciós) szabályok véges halmaza. : a nyelv ABC-je N ∩ =0 S : a mondatszimbólum, S ∈ N
∑
∑
∑
∗
alakúak, ahol , ∈ N U ∑ , -ban van N-beli elem. lehet üres, ilyenkor jelölést használunk −szabály ∗ szabály jelentése: Legyen w ∈ N ∪∑ , egy mondatszerű forma (lehet benne nemtermális). Ha látok benne egy részt, átírhatom −ra . Megjegyzés: A P maga is tekinthető egy nyelvnek az N ∪∑ ∪{ }∪{} alfabéta felett, véges sok mondatból áll. A P A levezetési szabályok, P megadása:
végessége miatt csak megszámlálhatóan véges sok különböző grammatika van, tehát így csak megszámlálhatóan sok nyelvet tudunk megadni.
szabály jelentése:
Az
∗
∈ N ∪∑ −ra.
Legyen
,egy mondatszerű forma (lehet benne nemtermális). Ha látok benne egy
részt, átírhatom
Jelölés: A szavak egymáshoz fűzését, konkatenálását egyszerűen egymás után írással jelöljük. Egy levezetési lépés formálisan: ∗
, ∈ N ∪∑ , akkor -ra az alkalmazása: lesz. Levezetési sorozat: egy 0 mondatszerű formából kiindulva: 0 ⇒ 1 ⇒... ⇒ n , ahol minden ⇒ egy P-beli szabály alkalmazása. ∗ Röviden: 0 ⇒G n : 0 -ból a G grammatika szerint a n végesen levezethető. Def.:
A G grammatikához tartozó (G által generált) nyelv: ∗
L G ={ ∈ ∑ ∣S ⇒∗G } , vagyis az S mondatszimbólumból végesen levezethető mondatok halmaza. Ha az N halmazt 1:1 leképezéssel egy N' halmazra képezzük, és G-t átírjuk G' grammatikává, ugyanazt a nyelvet kapjuk felett.
L G = LG ' . 29
∑
Nyelvosztályok: a szabályok alakjára vonatkozó megszorítások. Egyszerűtől a bonyolult felé haladunk, megadjuk a nyelveket felismerő gépet is. Felismerési feladat: w ∈ LG felismerése (tartalmazási kérdés) - Ha w ∈ LG igaz, akkor létezik hozzá véges levezetés S-ből. Generáljuk a levezetéseket: az összes 1 hosszút, majd 2 hosszút, stb. Előbb-utóbb megkapjuk w levezetését. - Ha w ∈ LG hamis, ezt nem midig tudjuk véges lépésben bizonyítani. Általánosan ez nem dönthető el. Speciális nyelvosztályokra eldönthető. Jelölési konvenció: elemei a terminális szimbólumok. Elnevezés oka: ha csak ilyen van egy szóban, akkor nem lehet rá szabályt alkalmazni. Jelölésük: a,b,c, - a Latin abc eleje, kis betűk. N elemei a nemtermálisok, jelei: A,B,C – nagybetűk Határozatlan szimbólum (változó): X,Y,Z – abc vége, nagy betűk Terminálisokból álló sorozat / szó: x,y,z – abc vége, kis betűk Tetszőleges sorozat: , , - görög kis betűk
∑
30
15. Veremautomaták. Veremautomaták és környezetfüggetlen grammatikák megfeleltetése. Veremautomata konstrukciója grammatikához.
Veremautomaták: Próbáljunk gépet konstruálni egy (felesleges szimbólumokat nem tartalmazó) w G nyelvtanhoz, ami végre. Példa: az aa∗a elfogadása. Szabályok: E ET ∣T ; T T⋅F∣ F ; F E∣a Levezetési fa:
w ∈ LG elfogadását hajtja
A legbaloldalibb levezetést keressük: (amit vizsgálunk áthúzzuk, helyére írunk egy szabályát, illetve elhagyjuk, ha terminális)
Mit vizsgálunk?
Lépés
E
1, kezdés: a gyökér E, E-szabályt keresünk, E ET -t vesszük. E helyére írjuk
E+T
2. lépés: Baloldalon E áll (a feljegyzés elején) E T -t vegyük.
T+T
3. lépés: T F -et vegyük
F+T a+ T
4. lépés: F a a+ elfogadása
T*F
5. lépés: T T ∗F szabály
F*F
6. lépés: T F szabály
a* F
7. lépés: F a szabály a* elfogadása
a
8. lépés: F a szabály a elfogadása
A □ (az ábrában a szürke hátterű) terminálisokat fogadtuk el: aa∗a A feljegyzések veremként viselkednek: az elején (tetején) álló jel helyére írunk, ha nemtermális; egyeztetjük a levezetendővel, ha termális.
31
A veremautomata felépítése: Működési séma:
Verem: a teteje olvasható, törölhető, írható. LIFO stack: push down stack
Formális megadás: PM (Push Down Machine) – el jelöljük. 7 összetevője van.
PM Q , ∑ , , , q 0 , z 0 , F
-
Q : állapotok véges halmaza
∑
:input szalag abc-je, véges halmaz
:a verem abc-je, véges halmaz :mozgási szabályok vége halmaza q0: q 0 ∈Q a kezdő állapot - z0 : z 0 ∈ , a verem alján álló szimbólum, más helyen nem állhat, nem törölhető. Ha csak ez áll a veremben, a verem -
-
F:
üres.
F ⊆Q -nak, az elfogadó állapotok halmaza
Működése: A kezdő állapotból és az üres veremből kiindulva olvassa a szalagot. Ha van olyan mozgássorozat, hogy mindent elolvasott, és a, F-beli állapotba jut: végállapotot elfogad. b, a verem aljára ér: üres veremmel elfogad. A mozgások megadása: A leképezés nem egyértelmű, nemdeterminisztikus. k
: Q× ∑ ∪{ } × ⇒Q× ∪{ } - Q : állapot, - ∑ ∪ {} : input betű. nem olvas. - : verem tetején álló jel - ∪ {}k : a leemelt jel helyére irt szó, a verem tetejére írja. Lehet üres is. Hossza legfeljebb k. Egy konkrét mozgást q , a , A= p , ad meg. A q állapotban az „a” input és a verem tetején „A” hatására átmegy p állapotba, „A” helyére -t ír, és az input következő cellájára lép, kivéve, ha a= . Ha a= , akkor inputot nem olvas, nem lép a szalagon. Ezek az -szabályok. Amit szerkesztettünk az aa∗a legbaloldalibb levezetéséhez speciális változat volt. A mozgásoknak három fő típusa van, példákkal illusztrálva: 1, q , a , A= p , BC – olvas inputot, ír a verem tetejére 2, q , , A=q , CB – nem olvas inputról, ír a verem tetejére, -szabály. 3, q , a , A=r , – törli a verem tetejét, ez jelenti a veremben az „A” feldolgozását. Ilyen lépésekkel ürítődik ki a verem. Az ábrában a verem alját jobboldalon ábrázoljuk, és balra nő a verem vízszintesen. Ez felel meg leginkább a legbaloldalibb levezetéseknek. Hasonlítsuk össze a veremautomatákat a véges állapotú automatákkal: A véges állapotú automata következő lépéssorozatát, amit az input hatására végre fog hajtani, (illetve végre hajthat) csak az aktuális állapota, és az átmenetek határozzák meg. A fizikai megvalósítás konstans méretű gépet igényel. A veremautomata esetében az állapoton túl a teljes veremmemória tartalmára is szükség van. Tulajdonképpen a teljes belső állapothoz a verem tartalma is hozzátartozik. A fizikai implementálásnál nem elég a konstans méret, a memória tetszőleges nagy lehet az input méretének függvényében.
32
Példa 3 lépés egymás utáni végrehajtására:
q , a , A= P , BC P , , B=r , CB r , b , C=q ,
1, 2, 3,
A belső állapotátmenetek gráfját itt is használhatjuk, két jel címkézi az éleket: olvasott input, verem teteje. Az állapotátmenetekhez a verembe írás tartozik még. Tétel: Minden
G= ∑ , N , S , P környezetfüggetlen grammatikához létezik üres veremmel elfogadó veremautomata: PM Q , ∑ , , , q 0 , z 0 (végállapotra nincs szükség)
Q : egyetlen állapot elég, -ban ezért az állapot komponenst elhagyjuk. ∑ : ugyanaz, mint G-ben - : ∑ ∪ N ∪z 0 -
Bizonyítás: Ötlet: - az automata a verem tetejére egy szabály jobboldalát írja a verem tetején álló nemterminális helyettesítéseként. - ha a verem tetején terminális áll, annak meg kell egyeznie az input betűvel.
Megadása: 1, , z 0 =S 2, a , a= 3, , A=w , ha A w∈ P Az 1, mozgás: a mondatszimbólum kerül a verembe. A 2, mozgás: Ha a verem tetején terminális áll, csak akkor van mozgás, ha megegyezik az input soron következő jelével. Ilyenkor a verem teteje törlődik, feldolgozódik. A 3, mozgás: Ha a verem tetején nemterminális áll, nem történik input olvasás, és a nemterminális helyére egy szabályának jobboldala íródik.
33
Ha
w ∈ LG , vegyünk w levezetési fáját. Ezen a legbaloldalibb levezetésnek megfeleltethető a veremautomata mozgássorozata. Az input elfogadása balról jobbra a levelek bejárását jelenti.
Fordítva: Ha a veremautomata w-t felismeri, lépéssorozatából w G-szerinti levezetési fáját építhetjük fel. Tehát L G = L PM . Tétel: Minden üres veremmel elfogadó automatához létezik ekvivalens végállapottal elfogadó és viszont. Kérdés: Az általános üres veremmel elfogadó veremautomaták milyen nyelvosztályt határoznak meg? Tudnak-e többet az egyállapotos veremautomatáknál? Válasz a következő tétel. Tétel: Minden üres veremmel elfogadó veremautomatához létezik vele ekvivalens környezetfüggetlen nyelvtan. Bizonyítás: A PM Q , , , , q 0 , z 0 -hoz konstruáljunk ekvivalens G , N , S , P grammatikát. A konstrukció szemléltetése: az automata működéséhez legbaloldalibb levezetőfát építünk, ebből kapjuk a grammatikát. Verem adja: jobb szélen, balra töltjük. Kiindulás: ha a verem tetején „Z” szimbólum áll, és q állapotban van, akkor valamilyen „p” állapotban lesz majd a „Z” töltésekor, más szóval „Z” feldolgozása után. Azt mondjuk: Z-t feldolgozta, és a q állapotból p állapotba jutott. Ahhoz, hogy ez megtörténjen, a q állapotban Z helyére Z 1 Z 2 … Z n szót írta, majd feldolgozza Z 1 -et P 1−ből P 2 −be jutva, stb, végül Z n -et dolgozza fel, P n−ből P−be jutva. A feldolgozást a Z , q , p hármasok jellemzik. Rajzoljuk fába a lépéseket:
∑
∑
Olyan, mint egy levezetési fa, csak a
∑
Legyenek ennek alapján a nemterminálisok: A levezetési szabályok: három típusú
értékű levelek hiányoznak. Ezek a pontok a nemterminálisok szerepét játsszák.
N ={ S }∪{ N Z , q , p ∣ z ∈ , p ∈Q , q∈Q } (Véges N)
a)
S N Z , q0 , p
b)
N Z , q , p a N Z 1 , p1 , p2 N Z 2 , p2 , p3 ... N Z n , pn , p
0
, minden
P ∈Q -ra
a ∈ ∑ ∪{ } - −szabály is lehet, nem olvas a szalagról - és P i -k tetszőleges állapotok, és a legfontosabb: p1, z 1 z 2 … z n ∈ q , a , z . (Ez felel meg az előző oldalon szereplő előkészítő szemléltetésnek. Fontos, hogy a verem bal felé töltődik, z i kerül előre. Ha a ≠ , akkor az „a” input betű elfogadásra kerül, és a levezetési fán N Z , q , p alatt a legbaloldalibb , ahol
levél lesz)
c)
N Z , q , p a , minden p , q ∈Q , a ∈ ∑ ∪{} -ra, ha P , ∈ q , a , z . Ez felel meg a verem tetején álló Z közvetlen, egy lépéses feldolgozásának. - Ha a ≠ , akkor a levezetési fában „a” értékű levél keletkezik.
- Ha a= , akkor lépéssel történik Z törlése. Ez okoz némi problémát: N Z , q , p szabályt eredményez. Ez a grammatikából is kiküszöbölhető, valamint a veremautomata is helyettesíthető ilyen átmenetet nem tartalmazó automatával. Ezt az esetet kizárhatjuk. Állítás: Az így kapott G -re L G = L PM . Bizonyítása a levezetési fa konstrukciójára alapul. G -hez és PM -hez ugyanazt a levezetési fát rendeljük. Ami az egyikben levezetés, a másikban is az lesz.
Összegzés: Adott: n elemű tömb, valós értékekkel Feladat: Vegyük sorra a tömb elemeit, és összegezzük azokat! Megvalósítás: Ciklusunkkal végig megyünk a tömb elemein, és egy harmadik változóba összegezzük azokat. Index := 0; for index=1 to n do begin tombosszeg := tombosszeg + tomb[index]; end;
Számlálás: Adott: n elemű tömb, valós értékekkel Feladat: Vegyük sorra a tömb elemeit, majd nézzünk meg egy meghatározott elemet, hogy hányszor szerepel benne! Megvalósítás: Ciklusunkkal végigmegyünk a tömb elemein, és egyenként megvizsgálva az elemeket, eldöntjük, hogy az éppen aktuális elem-e a keresett elem. Ha igen, akkor feljegyezzük, ha nem, akkor shiftelünk. Index := 0; keresendo := 5; szamlalo = 0; for index=1 to n do begin if keresendo = tomb[index] then inc(szamlalo); end;
Minimum, maximumkeresés: Adott: n elemű tömb, valós értékekkel Feladat: Vegyük sorra a tömb elemeit, és keressük meg benne a legnagyobb elemet! Megvalósítás: Ciklusunkkal végigmegyünk a tömb elemein, és egyenként megvizsgálva az elemeket, eldöntjük, hogy az éppen aktuális elem nagyobb-e mint a maximális elem. Ha igen, akkor feljegyezzük, ha nem, akkor shiftelünk. var k,i,max : integer; k := 1; max := tomb[1]; while (k <> n) do begin if (tomb[k] >= max) then begin max := tomb[k]; end; inc(k); end;