Zh-k, kis zh-k 1. kis zh Adott az alábbi nyelvtan. Determinisztikus véges automata kell a generált nyelvhez. $$\begin{eqnarray*} S &\ensuremath{\rightarrow}& aA \mid aC, \\ A &\ensuremath{\r... ...math{\rightarrow}& bF,\\ F &\ensuremath{\rightarrow}& \epsilon \end{eqnarray*}$$ Megoldás Második kis zh Adj minimálautomatát és reguláris kifejezést az alábbi $L$ nyelvre: $L=\{w\in {\{a,b\}}^*\;\vert\; w$-ben minden páratlan teljes homogén $a$-sorozatot legalább két $b$ követ közvetlenül$\}$ Megoldás Formális nyelvek zárthelyi 2001. március 26. 1. Adj meg egy olyan, egy kezdõállapottal rendelkezõ, determinisztikus véges automatát, mely a tizes számrendszerben felírt, 124-nél nagyobb természetes számokat fogadja el! Egy természetes szám nem kezdõdhet nullával, kivéve ha õ maga a 0 szám. 2. Adj meg egy egyirányban mozgó, egy kezdõállapottal rendelkezõ, determinisztikus véges automatát, mely egyenértékû az alábbi kétirányban mozgó véges automatával (vagyis ugyanazt a nyelvet fogadja el)! $\delta(S,a)=(A,e)$ $\delta(S,b)=(B,e)$ $\delta(A,a)=(A,e)$ $\delta(A,b)=(B,h)$ $\delta(B,a)=(B,h)$ $\delta(B,b)=(A,e)$ Kezdõállapot az $S$, elfogadó állapot az $A$, $e$ jelentése: elõre, $h$ jelentése: hátra. 3. Add meg az alábbi nyelvtan által generált nyelvhez tartozó minimálautomatát! $S\ensuremath{\rightarrow}A1$$\;\vert\;B1$ $A\ensuremath{\rightarrow}S1$$\;\vert\;\epsilon$ $B\ensuremath{\rightarrow}B0$$\;\vert\;A1\;\vert\;A0$ 4. Azonos-e az alábbi két reguláris kifejezés által megadott nyelv? ${(a{(ba)}^*+ba)}^*$ $(\epsilon+a^*){(baa^*)}^* + \epsilon$ 5. Döntsd el, hogy reguláris-e a következõ két nyelv! $L_1=\{\;w\in {\{\;a,b\;\}}^*\;\vert\; w$ minden $y$ prefixére fennáll, hogy $\vert\;{\vert y\vert}_a-{\vert y\vert}_b\;\vert\leq 2\;\}$ $L_2=\{\;w\in {\{\;a,b\;\}}^*\;\vert\; \vert\;{\vert w\vert}_a-{\vert w\vert}_b\;\vert\leq 2\;\}$ Egy $w=x_1\ldots x_n$ szó ( $x_j\in \{a,b\}$) prefixei az $\epsilon$ és az $y_i=x_1\ldots x_i$ szavak, ahol $1\leq i\leq n$. $\vert y\vert _a$ jelentése: az $a$ betûk száma $y$-ban. Mindegyik feladat 6 pontot ér. Válaszaidat mindig indokold meg, magyarázat nélküli megoldásokat nem fogadunk el. Jó munkát! Megoldás Harmadik kis zh Adj olyan veremautomatát, ami az $L=\{a^ib^jc^k\;\vert\; 1\leq i,j,k, k=2i+2\;\}$ nyelvet fogadja el! Megoldás Pót zh feladatsor Pótz h megoldás Negyedik kis zh (a) Adj véges fordítót, ami minden {a,b} feletti szót lefordít, mégpedig úgy, hogy az utoljára olvasott két karakter alapján ír ki. Ha ez a két betû aa vagy bb, akkor nem ír semmit, ha ab, akkor x-et ír, különben y-t. Tehát pl. az aabbaba fordítása xyxy. (b) Ezzel a fordítóval lefordítjuk azt az {a,b} feletti nyelvet, mely az a-val kezdõdõ és végzõdõ szavakat tartalmazza. Minél egyszerûbb osztályú nyelvtan kell a lefordított nyelvre. Megoldás Az utolsó kis zh, megoldással együtt