Rozšírení konečných automatů II Automaty s £-kroky
IB102 Automaty a gramatiky, 26.10.2009
1
Definice 2.46.     Nedeterministický FA s £-kroky je
A4 = (Q, £, 5, go, ^), kde význam všech složek je stejný jako v definici N FA s výjimkou přechodové funkce 5. Ta je definována jako totální zobrazení í:Qx(SU {e}) -► 2Q.
Rozšířená přechodová funkce
Definujeme funkci D£ : Q —» 2^ následujícím předpisem. D£(p) je nejmenší množina ICQ taková, že platí:
•  ^1,
•  pokud q £ X a r G 5(g, e), pak také r G X.
Rozšíření funkce Z^ na množiny stavů: pro Y C Q položíme
DeiY) = U De(q).
qeY
IB102 Automaty a gramatiky, 26.10.2009
2
Příklad -
IB102 Automaty a gramatiky, 26.10.2009
výpočet D
3
Definice rozšířené přechodové funkce 5 : Q x S* —» 2^ • %,e) = D£(q),
Lemma 2.47.          V přechodovém grafu automatu A4 existuje cesta
Pi —> ... —> pm —> q\ —» ... —» gn, kde m, n > 1, a G S, právě když Qn e 5(pi,a).
Jazyk přijímaný automatem A4 s e-kroky je
L(M) = {w e S* I %o, w) n F ^ 0}
IB102 Automaty a gramatiky, 26.10.2009
Příklad - výpočet rozříšeřené přechodové funkce
pro automat s £-kroky
IB102 Automaty a gramatiky, 26.10.2009
5
Ekvivalence automatů s e-kroky a N FA
Věta 2.48.      Ke každému N FA M = (Q, E, 5, g0? F) s £-kroky existuje ekvivalentní NFA (bez £-kroků).
Důkaz. Konstrukce M = (Q, S, 7, go, G) bez £-kroků:
7(q, a) = S(q, a) pro každé gGQ,a6S
G= í F                pokud L»£(%)nF = 0,
\FU{go}   jinak.
Korektnost:     Dokážeme,   že  pro  libovolné p E Q,   w e S+  platí
5(p, w) = 7(p, w) (indukcí vzhledem k délce slova w).
Algoritmus                                                                                                  □
IBIO2 Automaty a gramatiky, 26.10.2009
6
Uzáverové vlastnosti regulárních jazyků
Věta 2.49. a 2.51. Třída regulárních jazyků je uzavřená na sjednocení, průnik, rozdíl a komplement.
Důkaz, synchronní paralelní kompozice automatů + komplement.   □
Příklad.                Li    =    {aW | 2i > j > 0}
L2    =    {a}*.{6}* L3    =    {anbn | n > 0}
Li n L2 = L3
Jazyk L2 je regulární, L3 není regulární =^ Li není regulární.
IBIO2 Automaty a gramatiky, 26.10.2009
7
Věta 2.52.       Třída regulárních jazyků je uzavřená na zřetězení Důkaz.
Necht  Li   a   L2 jsou   regulární jazyky,   rozpoznávané   N FA  Mi  = (Qi, Ei, <Ji, gi, Fi) a M2 = (Q2, E2,82, q2, F2), kde Qľ n Q2 = 0.
Definujeme NFA s e-kroky Mi 0 M2 = (Qi U Q2, Si U S2,5, gi, F2), kde
5 = <Ji U ô2 U {((p, e), {q2}) | p G Fi}.
IB102 Automaty a gramatiky, 26.10.2009
8
Korektnost: Chceme dokázat L(Mi © M2) = L(Aíi).L(AÍ2)
I):    Necht u G L(Aíi), tedy 3r G Fi splňující r G öi(qi,u). Necht i; G L(AÍ2), tedy S (92,v)nf2^ 0. Pak
5(gi,wv)=     (J     5(p,v)   3  <J(r,v)   3  ô(q2,v)  = <S2(<?2,
peS(qi,u)
Protože S(92, v) n F2 ^ 0, tak 5(?1, uv) n F2 ^ 0. Tedy m; G L (Ali © Aí2).
IB102 Automaty a gramatiky, 26.10.2009
55
Věta 2.53.       Třída regulárních jazyků je uzavřená na iteraci Důkaz.
Necht L je regulární jazyk akceptovaný NFA M = (Q, S, 5, Qo^F). Definujeme NFA s £-kroky M* = (QU {p}, £,5',p, {p}), kde p 0 Q a
5' = 5 U {((p, e), {go}} U {((g, e), {p}) | q e F}.                D
IB102 Automaty a gramatiky, 26.10. 2009                                                                                                                                                                       10
Uzáverové vlastnosti regulárních jazyků - Shrnutí
IB102 Automaty a gramatiky, 26.10.2009
11
Regulární výrazy
Definice  2.58.          Množina  regulárních  výrazů  nad  abecedou  E,
označovaná RE(Ľ), je definována induktivně takto:
1.  e, 0 a a pro každé a G S jsou regulární výrazy nad S fŕzv. základní regulární výrazy).
2.  Jsou-li E,F regulární výrazy nad E, jsou také (E.F), (E + F) a (£*) regulární výrazy nad E.
3.  Každý regulární výraz vznikne po konečném počtu aplikací kroků 1-2.
IB102 Automaty a gramatiky, 26.10.2009
12
Každý regulární výraz E nad abecedou S popisuje (jednoznačně určuje) jazyk L (E) nad abecedou S podle těchto pravidel:
L{e)   M   {s}
L(0)    =7   0
L(a)   =   {a} pro každé a G S
L(E.F)   =7   L(E).L(F)
L{E + F)   =   L(E)UL(F)
L(E*)   ='  L(E)
*
IB102 Automaty a gramatiky, 26.10.2009
13
Příklady
IB102 Automaty a gramatiky, 26.10.2009
14
Ekvivalence konečných automatů a reg. výrazů
DFA
Věta   2.43
NFA
Věta   2.48
NFA s e-kroky
Věta 2.60.             Necht E je regulární výraz.    Pak existuje konečný
automat rozpoznávající L{E).
Důkaz. Pro libovolnou abecedu S lze zkonstruovat konečné automaty, které rozpoznávají jazyky popsané základními regulárními výrazy, tj. 0, {e} a {a} pro každé a £ S. Tvrzení věty pak plyne z uzavřenosti jazyků rozpoznatelných konečnými automaty vůči operacím sjednocení, zřetězení a iteraci.                                                                                       □
IB102 Automaty a gramatiky, 26.10.2009
15
Příklad
IB102 Automaty a gramatiky, 26.10.2009
16
Věta   2.43
Věta   2.48
Věta 2.62.              Necht L je akceptovaný nějakým  DFA,  pak L je
popsatelný nějakým regulárním výrazem.
Důkaz bude podán později pomocí regulárních přechodových grafů.
Kleeneho věta 2.63.            Libovolný jazyk je popsatelný regulárním
výrazem právě když je rozpoznatelný konečným automatem.
Ekvivalentní formulace: Třída jazyků rozpoznatelných konečnými automaty je nejmenší třída, která obsahuje všechny konečné množiny a je uzavřena na sjednocení, zřetězení a iteraci.
IB102 Automaty a gramatiky, 26.10.2009
17