IB 102 - úkol 3
Odevzdání: 17.10. 2011
Vypracoval (a): Skupina:
UCO:
1. [2 body] Mějme následující jazyk:
L = {anbm | n, m > 0, n, m jsou lichá nebo n
2m}
Rozhodněte, zda je zadaný jazyk regulární. Dále:
• Pokud je L regulární, sestrojte pro zadaný jazyk konečný automat i regulární gramatiku. Automat i gramatiku zapište úplně formálně správně.
• Pokud L není regulární, dokažte tuto skutečnost pomocí Lemmatu o vkládání (tzv. Pumping lemma).
IB 102 - úkol 3
Odevzdání: 17.10. 2011
Vypracoval (a): Skupina:
UCO:
2. [2 body] Mějme následující jazyk:
L = {aabm I n, m > 0, n, m jsou lichá a n
2m}
Rozhodněte, zda je zadaný jazyk regulární. Dále:
• Pokud je L regulární, sestrojte pro zadaný jazyk konečný automat i regulární gramatiku. Automat i gramatiku zapište úplně formálně správně.
• Pokud L není regulární, dokažte tuto skutečnost pomocí Lemmatu o vkládání (tzv. Pumping lemma).