IB102 – úkol 2, příklad 1 – řešení 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).
IB102 – úkol 2, příklad 1 – řešení Odevzdání: 29. 9. 2014
Vypracoval(a): UČO:
Skupina:
a) Výsledný automat vypadá následovně:
q0,2 q1,2 q2,2 q3,2
q0,3 q1,3 q2,3 q3,3
q0,0 q1,0 q2,0 q3,0
q0,1 q1,1 q2,1 q3,1
a a a
a
a a a
a
a a a
a
a a a
a
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
Automat učiní vždy po načtení znaku a horizontální přechod a po načtení znaku b
vertikální.
IB102 – úkol 2, příklad 1 – řešení Odevzdání: 29. 9. 2014
Vypracoval(a): UČO:
Skupina:
b) Můžeme si všimnout podobnosti horní a dolní poloviny automatu, což je zapříčiněno
tím, že používáme 4 stavy pro zapamatování počtu znaků b modulo 2. Tedy menší automat
A můžeme zadefinovat následovně:
q0,0 q1,0 q2,0 q3,0
q0,1 q1,1 q2,1 q3,1
a a a
a
a a a
a
bb bb bb bb