IB102 – úkol 2, příklad 1 Odevzdání: 29. 9. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body]
a) [1 bod] Mějme následující deterministický konečný automat nad abecedou Σ = {a, b}:
a a a
a
b
b
b
b
S použitím libovolného počtu níže uvedených povolených úprav (pouze a jen povolených
úprav) změňte zadaný automat tak, aby akceptoval jazyk
L = {w ∈ Σ∗
| #a(w) mod 4 = #b(w) mod 2}.
Povolené úpravy jsou:
• přidávání libovolných přechodů,
• označování akceptujících stavů.
Váš automat musí být deterministický. Stavy automatu si můžete pojmenovat podle vlastního
uvážení.
b) [1 bod] Zadejte automat A, který rovněž akceptuje výše uvedený jazyk L a zároveň
využívá méně stavů než automat v části (a).