IB102 - úkol 3 - řešení
Odevzdání: 17.10. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
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).
Řešení: L není regulární. Důkaz provedeme pomocí PL.
• Nechť n je libovolné přirozené číslo.
• Zvolíme slovo w = a2nbn. Zřejmě w G L a \w\ > n.
• Všechna možná rozdělení w = xyz, \xy\ < n, y ^ e vypadají takto:
x = ak k > 0
y = a1 / > 0, k + l <n
z = a2n-k-lbn
• Zvolíme i = 3, slovo xy%z pak vypadá takto:
xy3z = aka3la2n-k-lbn = a2n+2lbn
Zřejmě a2n+2lbn ^ L, neboť 2n + 21 je sudé, ale 2n + 21 ^ 2n (protože / > 0). Podle Lemmatu o vkládání tedy L není regulární.
IB 102 - úkol 3 - řešení
Odevzdání: 17.10. 2011
Vypracoval: James Bond Skupina: MI6
UCO: 007
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).
Řešení: Není možno najít dvě přirozená čísla n, m tak, aby obě byla lichá a zároveň platilo n = 2m. Proto L = 0, a tedy je L regulární jazyk.
Regulární gramatika generující L může vypadat například takto:
G = ({S},{a,b},{S ^aS},S)
Konečný automat přijímající L může vypadat například takto:
A = (M, K b}, S, Q, 0), kde 5(q, a) = 5(q, b) = q.