IB 102 — úkol 3, příklad 1 — řešení
Odevzdání: 8.10. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Uvažme jazyk
L = {w G {a, b}* | právě každý 2. symbol ve w je a anebo právě každý 3. symbol ve w je a}. (Tedy například slovo babab do tohoto jazyka patří, zatímco slovo babaaa nebo babba nikoliv.)
Rozhodněte, zda jazyk L je či není regulární a dokažte:
• Pokud L je regulární, uveďte regulární gramatiku generující anebo konečný deterministický automat akceptující daný jazyk. Gramatiku/automat zapište se všemi formálními náležitostmi.
• Pokud L není regulární, dokažte tuto skutečnost pomocí Lemmatu o vkládání (tzv. Pumping Lemma).
Řešeni: Jazyk je regulární.
G = ({S, A, B, C, D, E, F}, {a, b}, P, S)
P = {   S -+ b\bA\e,
A —> a I aB \ b \ bD,
B -> b\bC,
C —> a I aB,
D —^ a I aE,
E b\bF,
F -> b j bD}