IB102 – úkol 2, příklad 1 – řešení Odevzdání: 30. 9. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Mějme následující jazyk:
L = {w ∈ {l, o, s}∗
| každý výskyt podslova los ve slově w
se nachází uvnitř podlova losos}
Sestrojte totální deterministický konečný automat přijímající jazyk L.
Jazyk L přijímá například následující totální deterministický konečný automat A
A = ({qε, ql, qlo, qlos, qloso, qpeklo}, {l, o, s}, δ, qε, {qε, ql, qlo})
kde přechodová funkce δ je definována následovně:
δ(qε, l) = ql δ(qε, o) = qqε δ(qε, s) = qε
δ(ql, l) = ql δ(ql, o) = qqlo
δ(ql, s) = qε
δ(qlo, l) = ql δ(qlo, o) = qqε δ(qlo, s) = qlos
δ(qlos, l) = qpeklo δ(qlos, o) = qqloso
δ(qlos, s) = qpeklo
δ(qloso, l) = qpeklo δ(qloso, o) = qqpeklo
δ(qloso, s) = qε
δ(qpeklo, l) = qpeklo δ(qpeklo, o) = qqpeklo
δ(qpeklo, s) = qpeklo
Tentýž automat vypadá ve formě přechodového grafu následovně:
qε ql qlo qlos
qloso
qpeklo
l o s
o
l, s
s
o, s l
s
o
l
l, o, s
l, o
1