Sziasztok! Hirdetnivalók: 1.A nagy zh terembeosztása: A-D : E. I. C. E-F meg a németesek : I.B. 027 G-Ó : St. Nagy P-végig : E.I.B A zh-n minden korábban készült írásos segédeszköz használható, számológépek, mobiltelefonok nem. 2. A zh elõtt konzi az én csoportjaimnak: nov. 7. kedd, 14.00-tól az E. I. C.-ben. Az óra anyaga: 1. Az elõadáson tanult két konstrukció arra, hogy hogyan kell CF nyelvtanból a nyelvtan által generált nyelvet elfogadó veremautomatát csinálni. Ennek átismétlése, majd a múltkori feladatsor utolsó példájának megoldása. A megoldás itt 2. Említve, hogy visszafele is megy a konstrukció: PDA-ból is lehet CF nyelvtant csinálni, elõadáson volt a konstrukció, a példát nézzétek meg a jegyzetben. (Ugye már megszereztétek?) 3. Feladatmegoldás, önállóan. A múltkoriból kimaradt feladatok, meg a mostaniak. Megbeszéltük a múltkori 3. és 6.-nak az elvét, meg a mostani 2.-at. 4. Van nehéz feladatsor is, be lehet adni a megoldásokat lapon. De be lehet adni bármilyen megoldást is lapon, ha azt szeretnbétek, hogy megnézzem. Formális nyelvek gyakorlat (8) 2000. november 2., csütörtök 1. Mi lenne, ha két vermet engednénk mega veremautomatában? Azaz, ha a veremautomata szabályai $Q\times(\epsilon\cup \Sigma)\times {\Gamma}_1\times {\Gamma}_2\ensuremath{\rightarrow}Q\times {{\Gamma}_1}^*\times {{\Gamma}_2}^*$ alakúak volnának? Növekedne-e az automata ereje? (Az $a^nb^nc^n$ nyelv nem CF.) 2. Az ismert $E\ensuremath{\rightarrow}E+T\;\vert\;T$, $T\ensuremath{\rightarrow}T*F\;\vert\;F$, $F\ensuremath{\rightarrow}(E)\;\vert\;a$ nyelvtan generál felesleges zárójeleket. Például az $(a*a)+a$ generálásakor. Alakítsuk át úgy a nyelvtant, hogy ne tegye ezt! Cseles kérdések: Megoldás Igazak-e az alábbi állítások? Az indoklás nem elhanyagolható része a válasznak. Minden többállapotú PDA-hoz létezik vele egyenértékû egyállapotú PDA. Egy reguláris nyelv minden részhalmaza reguláris. Ha az $L_1, \ldots ,L_n$ nyelvek ($n\geq 1$) regulárisak, akkor az ${\cup}_{i=1}^nL_i$ nyelv is reguláris. Megszámlálhatóan végtelen sok reguláris nyelv uniója nem feltétlenül reguláris Megszámlálhatóan végtelen sok reguláris nyelv uniója lehet reguláris Megszámlálhatóan végtelen sok reguláris nyelv van Attól. hogy $L_1$ és $L_2$ nem reguláris, $L_1\cup L_2$ még lehet reguláris $(r^*+s^*)(s^*+r^*)={(r+s)}^*$ Ha $L$ reguláris, akkor az $L'=\{ww\;\vert\;w\in L\}$ nyelv is reguláris, hiszen $L'=L^2$ Ha $L$ reguláris, akkor $L^{-1}$ is reguláris Ha $L$ egy reguláris nyelv a $\Sigma$ ábécé felett, akkor az $L'=\{w\in{\Sigma}^*\;\vert\;\exists x\in L:\vert x\vert=\vert w\vert\}$ nyelv is reguláris. Ha $M$ egy PDA, akkor $L_u=L_a$, ahol $L_u$ azon nyelv, amit az automata üres veremmel elfogad, míg $L_a$ az a nyelv, amit végállapottal elfogad. Ha $L$ egy CF nyelv és $\epsilon\in L$, akkor van olyan $L$-t generáló nyelvtan, ami pontosan egy $\epsilon$-szabályt tartalmaz.