Formális nyelvek gyakorlat (6) 2001. március 20., kedd 1. Adj meg egy olyan véges automatát, melyben nincs $\epsilon$-átmenet és amelynek nyelve az $(11+0)^* (00+1)^*$ reguláris kifejezéssel írható le. 2. Add meg reguláris kifejezéssel az alábbi automata által elfogadott nyelv komplementerét! ( $\Sigma = \{a,b\}$) 3. Legyen $L_1$ azon $\{a,b\}$ feletti szavak nyelve, mely szavakban páros sok $a$ van, $L_2$ pedig azon $\{a,b\}$ feletti szavak nyelve, mely szavakban páratlan sok $b$ van. (a) Adj minimálautomatát az $L_1$, $L_2$, $L_\cup L_2$, $L_1\cap L_2$, ${L_1}^*$, ${L_2}^*$, $L_1L_2$ és $\overline{L_1}$ nyelvekre! (b) Adj reguláris kifejezést $L_1$-re és $L_2$-re! 4. Reguláris-e az $\{\; a^mb^n\;\vert\; m\leq n\leq 2m\;\}$ nyelv? 5. Döntsük el, hogy az alábbi két reguláris kifejezés által leírt nyelv azonos-e! $$((a+b) b^* a)^* \quad \quad \mbox{\rm és} \quad \quad (a+b) (b+a(a+b))^* a + \epsilon$$ 6. 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! 7. 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)$ 8. Az $L$ nyelvbe tartozzanak azok a szavak, melyekben van páratlan teljes homogén részsorozat. Szerkesszen minimálautomatát az alábbi nyelvekre: $L$, $L^2$, $L^*$! Az elsõ és az utolsó nyelvet adja meg reguláris kifejezéssel is! ( $\Sigma = \{a,b\}$)