IB102 — úkol 1, příklad 1 — řešení
Odevzdání: 1.10. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body]
a) [1 bod] Mějme následující deterministický konečný automat A nad abecedou {a, b}:
S použitím (libovolného, konečného počtu) níže uvedených povolených úprav (pouze a jen povolených úprav) změňte zadaný automat tak, aby akceptoval jazyk
La = {wE {a, b}* | #aH mod 4 = 2}.
Povolené úpravy jsou:
— přidávání libovolných přechodů pod b,
— označování akceptujících stavů,
Řešení: V automatu je potřeba označit stavy q2 a q$ jako akceptující, tak, aby automat akceptoval jazyk {w G {a}* | #a(w) mod 4 = 2}. Dále je potřeba zařídit, aby automat uměl akceptovat i slova obsahující znaky b. Přitom přítomnost nebo nepřítomnost znaků b ve slově neovlivňuje, jestli je slovo akceptováno nebo ne. Proto přechody pod b nemění stav automatu a jsou znázorněny jako smyčky.
b b b b
b b b b
b) [1 bod] S použitím stejných povolených úprav jako u v zadání a) změňte následující automat nad abecedou {a, b} tak, aby akceptoval jazyk
Lb = {w e {a, b}* | (#aH + 7 • #6H) mod 4 = 0}.
Řešení: Zadání jazyka nám říká, že každé b se započítává stejně jako 7a, a že zbytek takto váženého součtu po dělení 4 má být 0. Každý čtvrtý stav tedy musíme označit jako akceptující a přechody pod b z každého stavu vést tam, kam vede sekvence sedmi přechodů pod a.