20 - Regulární jazyky a jejich modely

Základní pojmy

pro pochopení látky je třeba mít přehled nad základními pojmy, jsou triviální, přesto je zde pro jistotu uvádím

Abeceda - konečná a neprázdná množina elementů, keré nazýváme symboly (Σ = {a,b,1,2} … abeceda sigma obsahuje symboly a,b,1,2)

Abeceda

Řetězec - Nechť Σ je abeceda.

ε je řetězec nad abecedou Σ

pokud x je řetězec nad Σ a a ∈ Σ, potom xa je řetězec nad abecedou Σ

Vlastnosti a operaci s řetězci … nechť x = 1010

délka - počet znaků … |x| = 4

konkatenace - zřetězení … x.x = 10101010

mocnina - říká nám, kolikrát za sebe zkonkatenujeme řetězec … x3 = 101010101010

reversace - obrátíme řetězec … reversal(x) = 0101

prefix - „předpona“ řetězce - prefix(„1010“) = { ε, 1, 10, 101, 1010 }

sufix - „přípona“ řetězce - sufix(„1010“) = { ε, 0, 10, 010, 1010 }

vlastní prefix/sufix - není obsaženo ε a samotný řetězec

podřetězec - prefix ∪ sufix ∪ vnitřní řetězce

vlastní podřetězec - podřetězec - { ε, celý řetězec }

Jazyk - Nechť Σ* značí množinu všech řetězců nad Σ. Každá podmnožina L ⊆ Σ* je jazyk nad Σ.

kardinalita - počet všech možných řetězců (slov)

konečný jazyk - má konečnou kardinalitu - např. ∅ , {ε}, {x: |x| = 1}

nekonečný jazyk - má nekonečnou kardinalitu - např. {x: 10 je podřetězec x}

Jazyky

Operace nad jazyky … nechť L1 = {0, 1, 00, 01}, L2 = {00, 01, 10, 11}, L3 = {0, 01}

sjednocení … L1 ∪ L2 = {0, 1, 00, 01, 10, 11}

průnik … L1 ∩ L2 = {00, 01}

rozdíl … L1 – L2 = {0, 1}

doplněk … L1' = { 10, 11, 001, 010, … }

konkatenace … L1.L2 = { 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, 0011, 0100, 0101, 0010, 0011 }

reversace …reversal L1 = { 0, 1, 00, 10 }

mocnina … L32 = { 00, 001, 010, 0101 }

iterace

L* = L0 ∪ L1 ∪ L2 ∪ … ∪ Li ∪ …

L+ = L1 ∪ L2 ∪ … ∪ Li ∪ …

Sjednocení	Průnik	Rozdíl	Doplněk
Sjednocení	Průnik	Rozdíl	Doplněk

Konečný automat

Definice

Konečný automat (KA) je pětice: M = (Q, Σ, R, s, F), kde:

Q je konečná množina stavů

Σ je vstupní abeceda

R je konečná množina pravidel tvaru: pa → q, kde p, q ∈ Q, a ∈ Σ ∪ {ε}

s ∈ Q je počáteční stav

F ⊆ Q je množina koncových stavů

Ostatní informace

dá se zobrazit grafem i tabulkou

KA - grafová reprezentace	KA - tabulková reprezentace

další pojmy:

konfigurace - řetězec χ ∈ QΣ* (př. pax, qx, …)

přechod - výpočetní krok KA - hrana mezi dvěma konfiguracemi (př. pax |- qx)

přijímaný jazyk - Jazyk přijímaný konečným automatem M, L(M), je definován: L(M) = {w: w ∈ Σ*, sw |–* f, f ∈ F}

máme nějakou posloupnost znaků w (vstup/jazyk), jsme v počátečním stavu w, …, pokud jsme schopni dojít v nějaké konečné posloupnosti do některého z koncových stavů, je tento jazyk přijímaný

Převod RV na KA

Konkatenace

Převod na KA - konkatenace

Sjednocení

Převod na KA - sjednocení

Iterace

Převod na KA - iterace

Modely pro regulární jazyky

Fundamentální modely pro regulární jazyky jsou: Regulární výrazy Konečné automaty Regulární výraz značí a generuje RJ. Konečný automat přijímá RJ.

Speciální konečné automaty

v praxi je třeba vyřešit problém nedeterminičnosti - pokud KA není deterministický, špatně se programuje

navrhnout nedeterministický automat je mnohem jednodušší jak deterministický, proto navrhujeme nedeterministický a poté se ho snažíme převést na deterministický

nedeterministický automat

obsahuje ε-přechody … ε-uzávěr stavu je množina stavů, kam až dojdeme bez načtení znaku (přes ε-přechod)

obsahuje více cest pro jeden znak z daného stavu

deterministický KA - odstranění předchozích dvou problémů

může obsahovat i 0 cest pro daný znak - dá se vyřešit stavem qfalse - nemůže se tedy zaseknout → Úplný DKA

může obsahovat nedostupné stavy a více neukončujících stavů → odstraněním získáme Dobře specifikovaný KA (jeden neukončující stav qfalse)

může obsahovat nerozlišitelné stavy (stavy, které jdou sloučit do jednoho)- odstraněním získáme Minimální konečný automat

Každý regulární jazyk má pouze jeden Minimální konečný automat

Druhy konečných automatů

Zdroj

Čerpal jsem z materiálů IFJ - konkrétně 1., 3. a 4. slajd

Potvrzení