Konečné automaty
Definice 1. Konečný automat (Finite Automaton, FA) M je pětice
(Q, , , q0, F), kde
* Q je neprázdná konečná množina stavů.
*  je konečná vstupní abeceda.
*  : Q ×   Q je parciální přechodová funkce.
* q0  Q je počáteční (iniciální) stav.
* F  Q je množina koncových (akceptujících) stavů.
IB102 Automaty a gramatiky, 22. 9. 2008 1
Příklad a zápis tabulkou
IB102 Automaty a gramatiky, 22. 9. 2008 2
Zápis grafem
IB102 Automaty a gramatiky, 22. 9. 2008 3
Výpočet konečného automatu
Rozšířená přechodová funkce ^: Q × 
 Q je parciální funkce
definovaná induktivně vzhledem k délce slova ze 
:
* ^(q, ) = q pro každý stav q  Q.
* ^(q, wa) =
(^(q, w), a) je-li ^(q, w) i (^(q, w), a) definováno,
 jinak.
Slovo w je akceptováno automatem M právě když ^(q0, w)  F.
Slovo w je zamítáno automatem M právě když ^(q0, w)  F.
IB102 Automaty a gramatiky, 22. 9. 2008 4
Jazyk přijímaný (akceptovaný, rozpoznávaný) automatem M je
L(M) = {w  
| ^(q0, w)  F}.
Jazyk, který je rozpoznatelný (nějakým) konečným automatem,
nazveme regulární.
Ekvivalenci konečných automatů definujeme podobně jako v případě
gramatik: konečné automaty M a M
jsou ekvivalentní, pokud L(M) =
L(M
).
IB102 Automaty a gramatiky, 22. 9. 2008 5
Parcialita přechodové funkce
Přechodová funkce  zavedena jako parciální.
Parcialita přechodové funkce nemá podstatný vliv na výpočetní sílu
konečných automatů.
Lemma 1. Ke každému FA M existuje ekvivalentní FA M
s totální
přechodovou funkcí.
Idea důkazu
//gfed`abcq0
a
''
b
//gfed`abc_^]\XYZ[q1 gfed`abc_^]\XYZ[q2
BC@A
a
GF
//
b
++
gfed`abcq3
a
kk
IB102 Automaty a gramatiky, 22. 9. 2008 6
Důkaz. Nechť M = (Q, , , q0, F).
Nechť automat M
je definován předpisem
M
= (Q  {p}, , 
, q0, F), kde p  Q a

(q, a) =
(q, a) je-li (q, a) definováno,
p jinak.
Zejména 
(p, a) = p pro každé a  .
Důkaz korektnosti:
* M' má totální přechodovou funkci ­ zřejmé z definice M
.
* M a M' jsou ekvivalentní ­ dokážeme.
IB102 Automaty a gramatiky, 22. 9. 2008 7
Indukcí k délce slova ověříme, že pro každé q  Q a w  
platí
(q, w) =
^(q, w) je-li ^(q, w) definováno,
p jinak.
Jelikož p  F, platí L(M) = L(M
). 2
IB102 Automaty a gramatiky, 22. 9. 2008 8
Konstrukce konečných automatů
Máme za úkol sestrojit automat rozpoznávající jazyk
L = {w  {a, b}
| w obsahuje podslovo abaa}
Označení stavů automatu zvolíme tak, aby bylo patrné, jaká část
požadovaného podslova abaa již byla automatem přečtena:
IB102 Automaty a gramatiky, 22. 9. 2008 9
Příklad
{w  {a, b}
| w obsahuje podslovo abaa  (w = b  w začíná i končí
na a a mezi dvěma výskyty
b je alespoň jedno a)}
gfed`abc
1 gfed`abc
2 gfed`abc
3 gfed`abc
4 gfed`abc
5
gfed`abcq gfed`abc
q1 gfed`abc
q2 gfed`abc
q3 gfed`abc
q4 gfed`abc
q5
gfed`abc
r gfed`abc
r1 gfed`abc
r2 gfed`abc
r3 gfed`abc
r4 gfed`abc
r5
gfed`abc
s gfed`abc
s1 gfed`abc
s2 gfed`abc
s3 gfed`abc
s4 gfed`abc
s5
gfed`abc
t gfed`abc
t1 gfed`abc
t2 gfed`abc
t3 gfed`abc
t4 gfed`abc
t5
IB102 Automaty a gramatiky, 22. 9. 2008 10
Synchronní paralelní kompozice automatů
Pro dané automaty M1 a M2 umožňuje sestrojit automat rozpoznávající
průnik (sjednocení, rozdíl) jazyků L(M1) a L(M2).
Nechť M1 = (Q1, , 1, q1, F1), M2 = (Q2, , 2, q2, F2)
a přechodové funkce 1, 2 jsou totální.
Definujeme FA M3 = (Q3, , 3, q3, F3), kde
* Q3 = Q1 × Q2 = {(p, q) | p  Q1, q  Q2}
* F3 = F1 × F2 = {(p, q) | p  F1, q  F2}
* q3 = (q1, q2)
* 3((p, q), a) = (1(p, a), 2(q, a))
Tvrzení: L(M3) = L(M1)  L(M2)
IB102 Automaty a gramatiky, 22. 9. 2008 11
Důkaz. Nejprve dokážeme toto tvrzení:
3((q1, q2), w) = (p, q)  1(q1, w) = p  2(q2, w) = q
Důkaz se provede indukcí vzhledem k |w|.
* Základní krok |w| = 0:
Z definice 3((q1, q2), ) = (q1, q2), 1(q1, ) = q1, 2(q2, ) = q2.
Pro w =  je tedy ekvivalence platná.
* Indukční krok: Nechť w = va, kde v  
, a  . Platí:
3((q1, q2), va) = (p, q) 
3((q1, q2), v) = (r, s)  3((r, s), a) = (p, q) 
1(q1, v) = r  2(q2, v) = s  1(r, a) = p  2(s, a) = q 
1(q1, va) = p  2(q2, va) = q
IB102 Automaty a gramatiky, 22. 9. 2008 12
Nyní již lze snadno dokázat vlastní tvrzení věty:
w  L(M3) 
3((q1, q2), w) = (p, q) kde p  F1 a q  F2 
1(q1, w) = p  2(q2, w) = q 
w  L(M1)  L(M2). 2
Modifikace pro sjednocení, tj. L(M3) = L(M1)  L(M2):
DÚ: Modifikujte konstrukci tak, aby platilo L(M3) = L(M1) L(M2).
IB102 Automaty a gramatiky, 22. 9. 2008 13
Automat pro komplement
K automatu M = (Q, , , q0, F) s totální přechodovou funkcí
sestrojíme automat M rozpoznávající jazyk co­L(M) jako
M = (Q, , , q0, Q - F).
//gfed`abcq0
a
%%
b
//gfed`abc_^]\XYZ[q1 gfed`abc_^]\XYZ[q2
BC@A
a
GF
//
b
**
gfed`abcq3
a
jj
//gfed`abcq0
a
%%
b
//gfed`abcq1 gfed`abcq2
BC@A
a
GF
//
b
**
gfed`abcq3
a
jj
IB102 Automaty a gramatiky, 22. 9. 2008 14