IB102 - úkol 7 - řešení                                    Odevzdání: 16.11. 2009
Vypracoval: James Bond                                UCO: 007
Skupina: MI6
1. [2 body] Pomocí regulárního výrazu popište následující jazyk:
L = {w E {a, b, c}* | #fe(w) = 2k, k > 0, c se ve w vyskytuje nejvýše jednou }
Řešení:    Například a*(ba*ba*)*(e + c + ba*ca*b)(a*ba*b)*a*.
IB 102 - úkol 7 - řešení
Odevzdání: 16.11. 2009
Vypracoval: James Bond Skupina: MI6
UCO: 007
2. [2 body] K zadanému konečnému automatu zkonstruujte ekvivalentní regulární výraz.
	a	b
->■ 1	{1,2}	{1,4}
2	{1,2}	{1,3,4}
3	{1}	0
^4	{1,2}	{1,4}
Řešeni: Automat transformujeme na regulární přechodový graf a začneme odstraňovat stavy. Výsledný regulární výraz závisí na pořadí, ve kterém stavy odstraníme.
Zrušíme stav 3:
Zrušíme stav 2:
a-\-b-\-a.a* .(a-\
a-\-b-\-a.a*. (a-\-b-\-ba)
Pokračování na další straně.
Zrušíme stav 4:
a-\-b-\-a.a*. (a-\-b-\-ba) -\-(b-\-a.a* .b) .(b-\-a.a* .b) * .(a-\-b-\-a.a* .(a-\-b-\-ba))
(b-\-a.a* .b). (b-\-a.a* .b) *
Zrušíme stav 1:
( a-\-b-\-a.a*.(a-\-b-\-ba)-\-(b-\-a.a*.b).(b-\-a.a*.b)*.(a-\-b-\-a.a*.(a-\-b-\-ba)) j   .(b-\-a.a*.b).(b-\-a.a*.b)*
Regulárni výraz ekvivalentní automatu ze zadání je tedy: a+b+a.a*.{a+b+ba)+{b+a.a*.b).{b+a.a*.b)*.[a+b+a.a*.(a+b+baj) J .{b+a.a*.b).{b+a.a*.b)*