Sziasztok! A mai óra anyaga: 1. Technikai megbeszélnivalók: a jövõ heti gyakorlat ugye elmarad, mert nov. 1. lesz. Helyette lesz egy alkalom, amire nem kötelezõ jönni : november 2., csütörtök, reggel (hajnal) fél kilenc, az I.B. 134-ben. 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 3c és 3d példákat. 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 25., szerda 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!