Formális nyelvek gyakorlat (5)

2005. október 20., csütörtök
1. Add meg reguláris kifejezéssel az alábbi véges automata által elfogadott nyelvet!



2. Adjunk reguláris kifejezést az alábbi automatához!



3. Add meg reguláris kifejezéssel az alábbi automata által elfogadott nyelv komplementerét! ( $\Sigma = \{a,b\}$)




4. Adott az alábbi három reguláris nyelv:
${(b^*ab^*a)}^*b^*$ $a^*b{(a^*ba^*b)}^*a^*$ ${(a+b)}^*a$
Legyen az $L$ nyelv azon szavak halmaza, amelyek a fenti három nyelv közül legalább kettônek mondatai!
Adja meg az $L$-t elfogadó minimálautomatát!

5. Adott két nyelv az alábbi két egyenletrendszerrel. Készítse el a két nyelv metszetét felismerő minimálautomatát!

$S_1=aS_1+b(A+\epsilon)$ $S_2=aS_2+b(B+\epsilon)$

$A=bS_1+a(A+\epsilon)$		$B=aS_2+b(B+\epsilon)$

6. Adott az alábbi $CF$ nyelvtan:

$$\begin{eqnarray*} S& \ensuremath{\rightarrow}& 00S\;\vert\;RP\;\vert\;QT\\ P&\e... ...emath{\rightarrow}&11 \\ T & \ensuremath{\rightarrow}&\epsilon \end{eqnarray*}$$

(i) Adja meg a nyelvet reguláris kifejezésként!
(ii) Készítsen hozzá harmadosztályú nyelvtant!
(iii) Adja meg a nyelvet elfogadó minimálautomatát!

7. Reguláris-e az $\{\; a^mb^n\;\vert\; m\leq n\leq 2m\;\}$ nyelv?

8. Reguláris-e az $\{a^ib^j\;\vert\; i>j\geq 1\}$ nyelv?

9. Reguláris-e a $\{0^i1^j \;\vert\; lnko(i,j)\not = 1\}$ nyelv?

10. Reguláris-e a $\{0^n1^m0^{n+m}\vert n, m\geq 1\}$ nyelv?

11. Küszöböljük ki az $\epsilon$-szabályokat az alábbi CF nyelvtanból!
$S\ensuremath{\rightarrow}ACb\;\vert\;a$, $A\ensuremath{\rightarrow}aCBb\;\vert\;\epsilon$, $B\ensuremath{\rightarrow}\epsilon\;\;a$, $C\ensuremath{\rightarrow}AB$

12. Küszöböljük ki az $\epsilon$-szabályokat!
$S\ensuremath{\rightarrow}ABC$, $A\ensuremath{\rightarrow}BB\vert\epsilon$, $B\ensuremath{\rightarrow}CC\vert a$, $C\ensuremath{\rightarrow}AA\vert b$

13. Küszöböljük ki a láncszabályokat!
$E\ensuremath{\rightarrow}E+T\vert T$, $T\ensuremath{\rightarrow}T*F\vert F$, $F\ensuremath{\rightarrow}(E)\vert a$

14. Küszöböljük ki a láncszabályokat!
$S\ensuremath{\rightarrow}A\vert B$, $A\ensuremath{\rightarrow}B\vert D\vertB\vert 1$, $B\ensuremath{\rightarrow}C$, $C\ensuremath{\rightarrow}B\vert A0$, $D\ensuremath{\rightarrow}C$