N-AP13

Zadání

Regulární jazyky. Konečné automaty, regulární gramatiky a regulární výrazy. Minimalizace konečného automatu. Převod nedeterministického konečného automatu na deterministický automat. Vztah mezi konečnými automaty a regulárními jazyky. Použití pumping lemmatu pro regulární jazyky.

Regulární jazyky

Abeceda je libovolná konečná množina, jejíž prvky se nazývají znaky. Abeceda může být i prázdná množina, zapisuje se Σ.
Slovo je libovolná konečná posloupnost znaků z abecedy.
Jazykem se rozumí libovolná množina slov nad nějakou abecedou. Jazyky mohou být konečné i nekonečné.
Regulární jazyk je jazyk generovatelný regulární gramatikou. Též je to jazyk rozpoznatelný konečným automatem nebo popsaný regulárním výrazem.

Vlastnosti regulárních jazyků

Popis vlastností regulárních jazyků je důležitý pro popis regulárních výrazů.

  • Ø je regulární jazyk.
  • { ε } je regulární jazyk.
  • { a } je regulární jazyk.

Pokud jsou A a B regulární jazyky, pak sjednocení, průnik, rozdíl, zřetězení a iterace jsou regulární jazyky.
Pokud je A regulární jazyk, pak komplement A je regulární jazyk.
Pokud je A regulární jazyk, pak zrcadlový obraz jazyka A je regulární jazyk.
Všechny konečné jazyky jsou regulární.
Příklad: Iterace jazyka {„ab“, „c“}* je { ε, „ab“, „c“, „abab“, „abc“, „cab“, „cc“, „ababab“, … }

Jazyk L je regulární, právě když:

  • může být vygenerován regulární gramatikou (tzn. existuje regulární gramatika G taková, že L(G) = L),
  • je akceptovaný nějakým deterministickým konečným automatem (tzn. existuje deterministický konečný automat M takový, že L(M) = L),
  • je akceptovaný nějakým nedeterministickým konečným automatem (tzn. existuje nedeterministický konečný automat M takový, že L(M) = L),
  • může být popsán regulárním výrazem (tzn. existuje regulární výraz RE takový, že L(RE) = L)

Uzávěrové vlastnosti regulárních jazyků

Třída regulárních jazyků je uzavřena na:

  • sjednocení (L1 union L2),
  • průnik (L1 inter L2),
  • rozdíl (L1 \ L2),
  • komplement (co–L),
  • zřetězení (L1.L2)
  • iteraci (L*),
  • pozitivní iteraci (L+),
  • zrcadlový obraz (reverzi) (LR)

Konečné automaty

Definice 2.1. 1)

Konečný automat M je pětice (Q, Sigma, delta, q0, F), kde
  • Q je neprázdná konečná množina stavů,
  • Sigma je konečná množina vstupních symbolů (vstupní abeceda),
  • delta: Q x Sigma → Q je parciální přechodová funkce (delta: Q x Sigma → 2Q totální v případě nedeterministického konečného automatu),
  • q0 in Q je počáteční stav,
  • F ⊆ Q je množina koncových stavů

Slovo akceptované automatem M je právě takové slovo, pod kterým automat přejde z počátečního stavu do koncového stavu.
Jazyk akceptovaný automatem M je množina všech slov, na kterých automat přejde z počátečního stavu do koncového stavu.

Rozšířená přechodová funkce deterministického konečného automatu:

Abychom mohli definovat jazyk akceptovaný automatem, je třeba zavést rozšířenou přechodovou funkci

hat{delta}: Q x Sigma* → Q definována induktivně vzhledem k délce slova ze Sigma*:

  • hat{delta}(q, epsilon) = q pro každý stav q in Q
  • hat{delta}(q, wa) =
    • delta(hat{delta}(q, w), a) je-li hat{delta}(q, w) i delta(hat{delta}(q, w), a) definováno
    • ortho jinak

Jazyk akceptovaný konečným automatem M, označovaný L(M) je tvořen právě všemi takovými slovy, pod kterými automat přejde z počátečního stavu do některého z koncových.
L(M) = {w in Sigma* | hat{delta}(q0,w) in F}

Rozšířená přechodová funkce nedeterministického konečného automatu:

hat{delta}: Q x Sigma* → 2Q, definována induktivně vzhledem k délce slova ze Sigma*:

  • hat{delta}(q, epsilon) = {q}
  • hat{delta}(q, wa) = bigcup{p in hat{delta}(q,w)}{}{delta(p,a)}

Jazyk akceptovaný nedeterministickým konečným automatem M, označovaný L(M) je tvořen právě všemi takovými slovy, pod kterými automat přejde z počátečního stavu do některého z koncových.
L(M) = {w in Sigma* | hat{delta}(q0,w) inter F != varnothing}

Regulární gramatiky

Definice 1.2. 2)

Gramatika G je čtveřice (N, Sigma, P, S), kde
  • N je neprázdná konečná množina neterminálních symbolů (neterminálů),
  • Sigma je konečná množina terminálních symbolů (terminálů) taková, že N inter Sigma = varnothing; N union Sigma = V je množina všech symbolů gramatiky,
  • P ⊆ V*NV* x V* je konečná množina pravidel. Pravidlo (alpha, beta) obvykle zapisujeme ve tvaru alpha right beta (čteme „alfa přepiš na beta“),
  • S in N je počáteční neterminál, neboli kořen gramatiky.

Gramatika je regulární, jestliže každé její pravidlo je tvaru A → aB (nebo A → Aa, tzv. levo lineární gramatika) nebo A → a s výjimkou S → epsilon, pokud se S nevyskytuje na pravé straně žádného pravidla.
Je to gramatika typu 3 podle Chomského hierarchie gramatik.

Regulární výrazy

Množina regulárních výrazů nad abecedou Sigma, označovaná RE(Sigma), je definována induktivně takto:

  1. epsilon, varnothing a a pro každé a in Sigma jsou (základní) regulární výrazy nad Sigma.
  2. Jsou-li E, F regulární výrazy nad Sigma, jsou také (E.F), (E + F) a (E*) regulární výrazy nad Sigma.
  3. Každý regulární výraz vznikne po konečném počtu aplikací kroků 1–2.

Závorky je možné vypouštět s tím, že největší prioritu má operátor „ * “, pak „ . “ a nakonec „ + “ Každý regulární výraz E nad abecedou Sigma popisuje jazyk L(E) nad abecedou Sigma podle těchto pravidel:

  • L(epsilon) = {epsilon}
  • L(varnothing) = varnothing
  • L(a) = {a} pro každé a in Sigma
  • L(E.F) = L(E).L(F)
  • L(E+F) = L(E) union L(F)
  • L(E*) = L(E)*

Regulární výrazy jsou tedy výrazy, které popisují množinu slov. Jsou ekvivalentní nějakému automatu případně gramatice. Využívají vlastností sjednoceni, průniku, rozdílu, iterace, zřetězení a komplementu. Lze napsat algoritmus, který rozhodne, zda jsou dva regulární výrazy ekvivalentní, tj. popisují stejný jazyk a redukovat daný jazyk na nějaký minimální automat.

Ekvivalenci mezi regulárními výrazy a konečnými automaty shrnuje Kleeneho veta:

Kleeneho věta

Libovolný jazyk je popsatelný regulárním výrazem, právě když je rozpoznatelný konečným automatem.

Minimalizace konečného automatu

Minimální automat je automat s nejmenším počtem stavů, který rozpoznává daný regulární jazyk L. Lze jej sestrojit z jakéhokoliv automatu rozpoznávající nějaký jazyk L.
Existence minimálního konečného automatu souvisí s Myhill–Nerodovou větou (viz otázka AP8,IN8 Regulární jazyky), kterou můžeme přeformulovat takto:

Věta 2.29 Myhill–Nerodova, 2. varianta3)

Počet stavů libovolného minimálního automatu rozpoznávajícího jazyk L je roven indexu prefixové ekvivalence ~L. (Takový konečný automat existuje právě když index ~L je konečný.)

Důsledek M-N věty

Minimální konečný automat akceptující jazyk L je určen jednoznačně až na isomorfismus (tj. přejmenování stavů).

Minimalizace konečného automatu probíhá tak, že nejprve jsou odstraněny nedosažitelné stavy a poté jsou ztotožněny jazykově ekvivalentní stavy.

Odstranění nedosažitelných stavů

Definice - dosažitelné a nedosažitelné stavy

Nechť M = (Q, Sigma, delta, q0, F) je konečný automat. Stav q in Q nazveme dosažitelný, pokud existuje w in Sigma* takové, že hat{delta}(q0, w) = q. Stav je nedosažitelný, pokud není dosažitelný.

Algoritmus pro eliminaci nedosažitelných stavů konečného automatu

Vstup: Konečný automat M = (Q, Sigma, delta, q0, F)
Výstup: Ekvivalentní automat M' bez nedosažitelných stavů.

Algoritmus

i := 0
Si := {q0}
repeat Si+1 := Si union {q | existsp in Si, a in Sigma: delta(p, a) = q}
i := i + 1
until Si = Si–1 Q' := Si M' = (Q', Sigma, delta|Q', q0, F inter Q')

Poznámka: Zápis delta|Q' znamená, že funkce delta je omezena na množinu Q'.
Intuitivně: Množina Si je množina stavů dosažitelná v automatu v maximálně i krocích.

Ztotožnění jazykově ekvivalentních stavů

Nechť M = (Q, Sigma, delta, q0, F) je konečný automat bez nedosažitelných stavů, jehož přechodová funkce je totální.

Definice - jazykově ekvivalentní stavy

Stavy p, q nazveme jazykově ekvivalentní, psáno pq, pokud
pq doubleleftright forallw in Sigma* : (hat{delta}(p, w) in F doubleleftright hat{delta}(q, w) in F).

Definice - Redukt

Reduktem automatu M = (Q, Sigma, delta, q0, F) nazveme konečný automat M/ = (Q/, Sigma, eta, [q0], F/), kde:
  • Stavy jsou třídy rozkladu Q/ (třída obsahující stav q je [q]).
  • Přechodová funkce eta je funkce splňující:

forallp,q in Q, foralla in Sigma: delta(q, a) = p doubleright eta([q], a) = [p].

  • Počáteční stav je třída rozkladu Q/ obsahující stav q0.
  • Koncové stavy jsou právě ty třídy rozkladu Q/, které obsahují alespoň jeden koncový stav.

Věta

Nechť M = (Q, Sigma, delta, q0, F) je konečný automat bez nedosažitelných stavů s totální přechodovou funkcí. Pak L(M) = L(M/).

Definice

Pro každé i in bbN0 definujeme binární relaci ≡i na Q předpisem
pi q doubleleftright forallw in Sigma*.|w| <= i : (hat{delta}(p, w) in F doubleleftright hat{delta}(q, w) in F)
  • pi q právě když p a q nelze „rozlišit“ žádným slovem délky <= i
  • pq právě když pi q pro každé i in bbN0. (≡ = bigcap{i=0}{infty}{≡}i)
  1. 0 = {(p, q) | p in F doubleleftright q in F}
  2. i+1 = {(p, q) | pi q wedge foralla in Sigma : delta(p, a) ≡i delta(q, a)}

Algoritmus konstrukce minimálního automatu

Vstup: Konečný automat M = (Q, Sigma, delta, q0, F) bez nedosažitelných stavů s totální přechodovou funkcí
Výstup: Redukt M/.

Algoritmus

i := 0
0 := {(p, q) | p in F doubleleftright q in F}
repeati+1 := {(p, q) | pi q wedge foralla in Sigma : delta(p, a) ≡i delta(q, a)}
i := i + 1
untili = ≡i–1 ≡ = ≡i M/ := (Q/, Sigma, eta, [q0], F/)
Příklad

Konstrukce minimálního automatu

  • První tabulka obsahuje nedostupné stavy (stav 7).
  • Druhá tabulka ukazuje přechodovou funkci po úpravě na totální, přidáním nového stavu N a nasměrováním všech nedefinovaných přechodů do něj.
  • Ostatní čtyři tabulky reprezentují postupnou minimalizaci automatu.

Praktické vysvětlení algoritmu

Na začátku tabulku přechodové funkce rozdělíme do dvou částí(tříd), do druhé části zaznamenáme výstupní stavy, do první části ty ostatní. Obě části označíme římskými číslicemi. Postupně procházíme stavy automatu který chceme minimalizovat, a pro jednotlivé prvky abecedy zjišťujeme, ve které části tabulky se nachází stav do kterého se při přechodu dostaneme. Číslo této části zapíšeme do tabulky k prvku abecedy u zpracovávaného stavu. (tabulka 3)

Tabulku opět rozdělíme, do částí(tříd) které označíme římskými číslicemi, v každé necháme stavy ze kterých se pod všemi prvky abecedy dostaneme do stejných částí tabulky. Aplikujeme předchozí krok.(tabulka 4,5)

Tento postup aplikujeme dokud každá část tabulky neobsahuje jen stavy přecházející do stejných tříd. Ve výsledné tabulce nezapisujeme názvy stavů, ale jen označení tříd s jejich přechody(tabulka 6).

Převod nedeterministického automatu na deterministický

Věta

Pro každý NFA M = (Q, Sigma, delta, q0, F) existuje ekvivalentní DFA.

Nedeterministický konečný automat je definován stejne jako deterministický automat s tím rozdílem, že přechodová funkce se definuje jako totální zobrazení do množiny všech podmnožin stavů.

Jinými slovy z každého stavu může nedeterministický automat pod stejným vstupním symbolem přejít do různých stavů.

Obecně algortimus převodu vypadá tak, že:

1. Stavy nového automaty jsou z množiny všech podmnožin stavů Q.
2. Přechodová funkce je z množiny podmnožin do množiny podmnožin Q a na pravé straně přechodové funkce je množina všech stavů Q, kam by se NFA mohl dostat. V další iteraci je pak na pravé straně množina všech stavů, kam by se NFA mohl dostat ze všech stavů z podmnožiny z předchozí iterace.
3. Konečné stavy jsou pak ty, kde se v podmnožině vyskytuje alespoň jeden z koncových stavů z předchozího NFA.

Algoritmus transformace NFA na DFA

Vstup: NFA M = (Q, Sigma, delta, q0, F).
Výstup: Ekvivalentní DFA M' = (Q', Sigma, delta', {q0}, F') bez nedosažitelných stavů a s totální přechodovou funkcí.

Algoritmus

Q' := { {q0} }; delta' := varnothing; F' := varnothing; Done := varnothing;
while (Q'Done) <>varnothing do M := libovolný prvek množiny Q'Done if M inter F <>varnothing then F' := F' union {M} fi foreach a in Sigma do N := bigcup{p in M}{}{delta(p,a)} Q' := Q' union {N}
delta' := delta' union {( (M, a),N)} od Done := Done union {M}
od M' = (Q', Sigma, delta', {q0}, F')

Příklad

Mějme nedeterministický konečný automat :

a b
→ 1 1,2 1,7
2 - 3
3 - 4
4 5 -
← 5 5 5
6 - 5
7 6 -


Převod nedeterministického automatu na deterministický provedeme pomocí algoritmu následovně:

Praktické vysvětlení algoritmu

Začínáme vstupním stavem, který napíšeme do tabulky (1). Zjistíme množinu stavů, do kterých se dostaneme pomocí prvků abecedy. (pro a 1,2, pro b 1,7). Poté vždy vytvoříme (pokud ještě neexistuje) nový stav pojmenovaný jako sjednocení stavů (pro a 12, pro b 17) a zaznamenáme do tabulky. Vezmeme poté následující nezpracovaný stav v nově tvořené tabulce (12) a zjistíme do jaké množiny stavů se lze dostat ze stavů 1 a 2 a provedeme jejich sjednocení (pro a 1,2 , pro b 1,3,7) poté opět zaznamenáme případný nový stav. Od této chvíle pokračujeme obdobně.

Algoritmus končí, ve chvíli kdy není možné nalézt žádný nový stav. Vstupní stavy zůstávají stejné, koncové stavy jsou ty, které obsahují některý z původních koncových stavů.

Takto vytvořený automat nemusí být minimální, ale je bez nedosažitelných stavů, s totální přechodovou funkcí.

a b
→ 1 12 17
12 12 137
17 126 17
137 126 147
126 12 1357
147 1256 17
← 1357 1256 1457
← 1256 125 1357
← 1457 1256 157
← 125 125 1357
← 157 1256 157

Vztah mezi konečnými automaty a regulárními jazyky

Platí věta, že pro každý jazyk popsatelný nějakým regulárním výrazem existuje automat, který jej rozpoznává.

Dále platí věta, že pokud je jazyk rozponávaný nějakým DFA, pak je popsatelný regulráním výrazem.

Tj. obě třídy jazyku jsou ekvivalentní (Kleeneho věta).

Pumping Lemma pro regulární jazyky

Lemma 2.13. (o vkládání)4)

Nechť L je regulární jazyk. Pak existuje číslo n in bbN takové, že všechna slova w in L, jejichž délka je alespoň n, lze psát ve tvaru w = xyz, kde |xy| ≤ n, yepsilon a xyiz in L pro každé i in bbN0.

Je to prostředek jak dokázat, že nějaký daný jazyk není regulární. Představuje nutnou (nikoliv postačující) podmínku, kterou musí každý regulární jazyk splňovat.
Pumping lemma prakticky říká, že v dostatečně dlouhém slově w, které patří do jistého jazyka, lze nalézt tři části x, y a z, přičemž y může být i celé slovo. y lze pak libovolně opakovat (napumpovat), či zcela vyloučit a výsledné slovo bude patřit do jazyka. Délka slova musí být větší nebo rovna pumpovací konstantě n a délka části xy musí být menší nebo rovna n.

Postupujeme tak, že ukážeme, že pokud platí obměna lemmatu o vkládání (jde o implikaci), potom jazyk L není regulární:

  • pro libovolné (všechna) n in bbN (pumpovací konstanta)
  • existuje takové w in L délky alespoň n, pro které platí, že
  • při libovolném (všech) rozdělení slova w na tři části x, y, z, že |xy| ≤ n, yepsilon
  • existuje alespoň jedno i in bbN0 takové, že xyiz notin L

Potom z lemmatu o vkládání plyne, že L není regulární.

Intuitivní důkaz tvrzení říká:

• Pro konečné jazyky se jako pumpovací konstanta vezme délka nejdelšího slova.
• Pro nekonečné jazyky musí existovat nějaký minimální konečný automat, který je akceptuje. Spočítá se počet jeho stavů a vezme se jako pumpovací konstanta p. Pokud automat akceptuje i slova delší než p, pak musí některými stavy procházet vicekrát. Jeden tento stav označíme S. Transakce, které automat posunou ze stavu S, a zpět do stavu S, akceptují nějaký řetězec. Tento řetězec je y v pumping lemmatu, tj. platí tvrzení lemma, že lze slovo nafukovat i že lze nafukování přeskočit rovnou dál.

Předměty

IB102 Automaty a gramatiky
IB005 Formální jazyky a automaty

Vypracoval

Marek Menšík UČO 255679
Nevím přesně, kdo otázky zpracoval přede mnou, pouze jsem je sem umístil, doplnil chybějící věci a opravil nepřesnosti. Připomínám, že věci zde uvedené nemusí být korektní a zatím neprošly kontrolou žádného z profesorů. Z mé strany je tato otázka dokončena a případné chybějící věci a chyby mě můžete napsat na UČO mail nebo se registrujte a upravte je sami.

1)
viz skripta Automaty a formální jazyky I, str. 11
2)
viz skripta Automaty a formální jazyky I, str. 4
3)
viz skripta Automaty a formální jazyky I, str. 26
4)
viz skripta Automaty a formální jazyky I, str. 18
You could leave a comment if you were logged in.
mgr-szz/ap-ap/13-obr.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0