Formális nyelvek gyakorlat (3) 2001. február 27., kedd 1. A következõ véges automata input ábécéje $\{a,b,c\}$. (a) Küszöböljük ki az $\epsilon$-szabályt! (b) Determinizáljuk az így kapott automatát! (c) Mi az elfogadott nyelv? 2. Determinizálni kell az alábbi véges automatát: 3. (a) Jobbreguláris és (b) balreguláris nyelvtan kell az alábbi véges automata által elfogadott nyelvhez. 4. Adjuk meg az alábbi automatához tartozó minimálautomatát! 5. (a) Minimálautomata kell az alábbi nyelvtan által generált nyelvre. (b) Mi a nyelv? $S\;\ensuremath{\rightarrow}\; aA\;\vert\;bB\;\vert\;b$ $A\;\ensuremath{\rightarrow}\; aS\;\vert\;bC$ $B\;\ensuremath{\rightarrow}\;aC\;\vert\; bS$ $C\;\ensuremath{\rightarrow}\;aB\vert\;bA \vert\; a$ 6. Minimálautomata kell az alábbi nyelvtan által generált nyelvre. $S\;\ensuremath{\rightarrow}\; Aa$ $A\;\ensuremath{\rightarrow}\; Ca\;\vert\;Fb\;\vert\;\epsilon$ $C\;\ensuremath{\rightarrow}\;Aa$ $F\;\ensuremath{\rightarrow}\;Fa\vert\;Fb \vert\; \epsilon$ 7. Adjunk determinisztikus véges automatát a következõ nyelvhez: $L=\{w\in {\{a,b\}}^*\;\vert\;w$-ben jobbról a 3. betû b$\}$ 8. Adjunk determinisztikus véges automatát a következõ nyelvre: $L=\{w\in {\{0,1\}}^*\;\vert\;$ létezik két $0$ $w$-ben, melyek között néggyel osztható számú egyes áll$\}$.