Sziasztok! A mai óra anyaga: 1. Technikai megbeszélnivalók: Nagyzh lesz nov. 8-án, a terembeosztást a jövõ héten megmondom. Elõtte konzultáció lesz nov. 7-én 14.00-tól végkimerülésig, hogy hol azt majd megírom. A nagyzh anyaga minden a reguláris és CF nyelvekkel, nyelvtanokkal kapcsolatban. Mindent lehet használni, úgyhogy szerezzetek jegyzetet addigra! 2. Megbeszéltük a múlt heti 3d példát, meg elmondtam, hogy a 3c-t ugyanúgy kell, mint a 3b-t, és a generált nyelvre ugyanaz is jön ki, viszont ez a nyelvtan nem egyértelmû, pl. az abab szónak két levezetési fája van. 3. Pumpálási lemma CF nyelvekre: Ha egy $L$ nyelv CF, akkor létezik olyan $N\geq 0$ szám, hogy minden olyan $w\in L$ szónak, mely hosszabb N-nél van olyan felbontása $w=uxyvz$ részre, hogy $ux^iyv^iz\in L$ és $xv\not =\epsilon$. Ezzel a lemmával beláttuk, hogy az $a^nb^nc^n$ nyelv nem CF. Pontosabban lásd a jegyzetben. 4. Veremautomata: definíció, üres veremmel és állapottal elfogadás. Megcsináltuk az 1. és 2. feladatot, HF a 3. A 2. feladat megoldása . 5. Elõadáson lesz majd, hogy a veremautomaták és a CF nyelvtanok egyenértékûek, úgy értve ezt, hogy pontosan azok a nyelvek generálhatók CF nyelvtannal, amik veremautomatával elfogadhatók. Elõadáson lesz vagy volt két konstrukció, hogy hogyan kell CF nyelvtanhoz veremautomatát szerkeszteni. Ezekre a konstrukciókra vonatkozik az utolsó feladat, csináljátok meg. Formális nyelvek gyakorlat (7) 2000. október 26., csütörtök 1. PDA kell ahhoz a nyelvhez, melynak ábécéje az $\{a,b\}$ és szavaiban az $a$ és a $b$ karakterek száma megegyezik. 2. Automata kell: $\{a^ib^jc^k\;\vert\;i+k=j\geq 0\;\}$ 3. PDA kell a következõ nyelvhez: $\{a^mb^n\;\vert\;1\leq m\leq n\leq 2m\;\}$ 4. A kétirányú PDA, olyan mint a sima PDA, csak bír visszafele is menni. (Ahogy a 2VA-nál volt.) Akkor fogad el, ha végigolvassa a szót és elfogadó állapotba kerül. Kérdés: erõsebb-e ez, mint a sima PDA? (Segítség: az $a^nb^nc^n$ nyelv nem CF nyelv.) 5. Mutasd meg, hogy az $\{x\in {\{a,b,c\}}^*\;\vert\; {\vert x\vert}_a={\vert x\vert}_b={\vert x\vert}_c\}$ nyelv nem CF nyelv. (Nehezebb feladat, a pumpálási lemmát kell élesíteni a megoldásához) Gyakorolni még... 6. Az $L_1$ és az $L_2$ nyelveket is az definiálja, hogy bennük az $ab$ és a $ba$ minirészsorozatok száma azonos. Viszont $L_1$ ábécéje az $\{a,b\}$, $L_2$-é pedig az $\{a,b,c\}$. Mindkét nyelvre kell automata vagy nyelvtan. 7. Tervezzen automatát azon $\Sigma=\{a,b\}$ feletti nyelvhez, melynek szavaiban a magányos b-k száma meghaladja az egynél hosszabb homogén a sorozatok számát. 8. HÁZI FELADAT!!! Az $S\ensuremath{\rightarrow}XY$, $X\ensuremath{\rightarrow}aXb\;\vert\;ab$, $Y\ensuremath{\rightarrow}bYc\;\vert\;bc$ nyelvtanhoz készítsünk PDA-t, mindkét konstrukcióval, amit tanultunk (vagy tanulni fogunk)! Elemezzük az $a^2b^5c^3$ szót mindkét automatával!