AP8, IN8 Regulární jazyky

Zadání

regulární jazyky, způsoby jejich reprezentace, vlastnosti regulárních jazyků, vztah mezi konečnými automaty a regulárními gramatikami

Základní pojmy

Abeceda je libovolná konečná množina znaků (písmen, symbolů)
Slovo nad abecedou Sigma je libovolná konečná posloupnost znaků této abecedy
Jazyk nad abecedou Sigma je libovolná množina slov nad Sigma

Reprezentace regulárních jazyků

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)

Regulární gramatika

Definice 1.2. 1)

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 → 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.

Konečný automat

Definice 2.1. 2)

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ů

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

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

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)}

Konečný automat je možné reprezentovat:

  • uspořádanou pěticí
  • tabulkou
  • přechodovým grafem
  • výpočetním stromem

více viz otázka AP9,IN9 Konečné automaty

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)*

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.

Lemma o vkládání (pumping lemma)

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

Nechť L je regulární jazyk. Pak existuje n in bbN takové, že slovo w in L, jehož 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.

Lemma o vkládání je nutnou (nikoliv postačující) podmínkou pro regularitu jazyka a lze jej použít pro důkaz toho, že nějaký jazyk není regulární (NE pro důkaz toho, že jazyk je regulární!!!). Postupujeme tak, že ukážeme, že pokud platí „negace“ lemmatu o vkládání, potom jazyk L není regulární:

  • pro libovolné n in bbN (pumpovací konstanta)
  • existuje takové w in L, délky alespoň n, pro které platí, že
  • při libovolném rozdělení slova w na tři části x, y, z, že |xy| ≤ n a 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í.

Myhill-Nerodova věta

Myhill-Nerodova věta představuje nutnou a postačující podmínku pro regularitu jazyka.
Pro formulaci M-N věty potřebujeme několik pomocných pojmů:

Definice – pravá kongruence

nechť Sigma je abeceda a nechť ~ je ekvivalence na Sigma*. Řekněme, že ~ je zprava invariantní (pravá kongruence), pokud pro každé u, v, w in Sigma* platí u ~ v doubleright uw ~ vw. Index ~ je počet tříd rozkladu Sigma*/~ (pokud je těchto tříd nekonečně mnoho, klademe index ~ roven infty).

Definice – prefixová ekvivalence

Nechť L je libovolný (ne nutně regulární) jazyk nad abecedou Sigma. Na množině Sigma* definujeme relaci ~L zvanou prefixová ekvivalence pro L takto:
u ~L v doubleleftright forallw in Sigma* : uw in L doubleleftright vw in L Tedy ~L obsahuje právě ty dvojice (u, v) které mají tu vlastnost, že po připojení libovolného w vzniklá slova uw, vw budou do jazyka L patřit buď obě, nebo ani jedno z nich.

Lemma

Nechť L je libovolný jazyk nad Sigma. Pak relace ~L je pravá kongruence a L lze vyjádřit jako sjednocení některých (ne nutně konečně mnoha) tříd rozkladu Sigma*/~L.

Věta 2.28 Myhill-Nerodova věta4)

Nechť L je jazyk nad Sigma, pak tato tvrzení jsou ekvivalentní:
  1. L je rozpoznatelný konečným automatem.
  2. L je sjednocením některých tříd rozkladu určeného pravou kongruencí na Sigma* s konečným indexem.
  3. Relace ~L má konečný index.

Vlastnosti regulárních jazyků

Uzávěrové vlastnosti

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)

Rozhodnutelné problémy pro třídu regulárních jazyků

Mějme konečné automaty M a M'.
Následující problémy jsou rozhodnutelné:

  • ekvivalence: jsou M a M' ekvivalentní? (platí L(M)=L(M')?)
  • inkluze (jazyků): platí L(M) ⊆ L(M')?
  • příslušnost (slova k jazyku): je-li dáno w in Sigma*, platí w in L(M)?
  • prázdnost (jazyka): je L(M) = varnothing?
  • univerzalita (jazyka): je L(M) = Sigma*?
  • konečnost (jazyka): je L(M) konečný jazyk?

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

Třídy jazyků, které lze generovat regulárními gramatikami, resp. rozpoznat konečnými automaty, jsou si rovny. To znamená, že k dané regulární gramatice lze sestrojit ekvivalentní (deterministický, nedeterministický, …) konečný automat a naopak.

Regulární gramatika → konečný automat

Lemma 2.695)

Ke každé regulární gramatice G =(N, Sigma, P, S) existuje nedeterministický konečný automat M = (Q, Sigma, delta, q0, F) takový, že L(G) = L(M).
(Důkaz viz skripta z Automatů a formálních jazyků I, str. 49)

Myšlenka důkazu:

Stavy automatu budou odpovídat neterminálům gramatiky, tj. pro každý neterminál A bude existovat stav overline{A}. Pro každé pravidlo AaB přidáme do delta(overline{A}, a) stav overline{B}. Abychom se mohli vypořádat také s pravidly tvaru Ca, zavedeme speciální koncový stav qf, který přidáme do delta(overline{C}, a). Počáteční stav bude overline{S}, koncový stav qf a případně také overline{S}, pokud gramatika obsahuje pravidlo Sepsilon.

Konečný automat → regulární gramatika

Lemma 2.716)

Pro každý konečný automat M = (Q, Sigma, delta, q0, F) existuje regulární gramatika G =(N, Sigma, P, S) taková, že L(M) = L(G).
(Důkaz viz skripta z Automatů a formálních jazyků I, str. 50)

Myšlenka důkazu:

Neterminály budou odpovídat stavům, pravidla budou simulovat přechodovou funkci. Je tu však jeden problém – pokud automat přijímá prázdné slovo (tj. počáteční stav je koncovým stavem), musí každá ekvivalentní gramatika nutně obsahovat pravidlo Sepsilon, kde S je kořen. Pak se ale S nesmí vyskytovat na pravé straně žádného pravidla. Přitom je ale možné, že některé přechody automatu končí v počátečním stavu a mají být simulovány pravidly, které mají na pravé straně S, což by vedlo ke konfliktu s požadavkem pravostranných výskytů S. Tento problém vyřešíme tak, že ke zkonstruované gramatice (mající jak Sepsilon, tak i pravostranné výskyty S) nalezneme ekvivalentní regulární gramatiku.

Poznámka

Lingvista Noam Chomsky rozdělil gramatiky do čtyř skupin (typů) na základě různých omezení na tvar pravidel a podle jejich popisné síly.

Chomského hierarchie rozlišuje tyto čtyři (základní) typy gramatik:

  • typ 0

Libovolná gramatika je gramatikou typu 0; na tvar pravidel se nekladou žádné omezující požadavky. Někdy též se takové gramatiky označují jako gramatiky bez omezení či frázové gramatiky.

  • typ 1

Gramatika je typu 1 nebo též kontextová, jestliže pro každé její pravidlo platí alpha right beta platí delim{|}{alpha}{|} <= delim{|}{beta}{|} s eventuelní výjimkou pravidla S right epsilon pokud se S nevyskytuje na pravé straně žádného pravidla.

  • typ 2

Gramatika je typu 2, též bezkontextová, jestliže každé její pravidlo je tvaru A right alpha, kde delim{|}{alpha}{|} >= 1 s eventuelní výjimkou pravidla S right epsilon pokud se S nevyskytuje na pravé straně žádného pravidla.

  • typ 3

Gramatika je typu 3, též regulární, jestliže každé její pravidlo je tvaru A right aB nebo A right a s eventuelní výjimkou pravidla S right epsilon, pokud se S nevyskytuje na pravé straně žádného pravidla.

Literatura

Vypracoval

Lukáš Hala, 173454@mail.muni.cz
Pokud si myslíte, že tady něco chybí, přebývá nebo že je něco blbě, tak to prosím upravte ;-)

FIXME Je potřeba ještě zapracovat poznámky od Jitky Pospíšilové.

1) viz skripta Automaty a formální jazyky I, str. 4
2) viz skripta Automaty a formální jazyky I, str. 11
3) viz skripta Automaty a formální jazyky I, str. 18
4) viz skripta Automaty a formální jazyky I, str. 25
5) viz skripta Automaty a formální jazyky I, str. 49
6) viz skripta Automaty a formální jazyky I, str. 50

Diskuze

, 2008/06/06 15:58

Doplnil som cast „Regularni vyrazy“ podla mna o dost dolezitu Kleeneho vetu a pravidla generovania jazyka z reg. vyrazov.

, 2008/06/16 21:43

K pumping lematu - neni nahodou pumpovaci konstanta i? n je přece délka slova

, 2008/06/16 22:57

Podle skript je jako pumpovací konstanta označeno n.

, 2009/06/09 15:59

Je to pumpovaci _konstanta_, takze i to byt nemuze, to je cislo ktere se „pumpuje“

, 2008/06/17 21:46

Neměla by tu být prefixová ekvivalence místo pravá kongruence??

(Třetí Lemma M-N věty)
Lemma: Nechť L je libovolný jazyk nad Sigma. Pak relace ~L je _pravá kongruence_ a L lze vyjádřit jako sjednocení některých (ne nutně konečně mnoha) tříd rozkladu Sigma*/~L.

, 2008/06/18 12:38

Myslím, že ne. Prefixová ekvivalence (~L) je zároveň i pravou kongruencí(~) (důkaz je ve skriptech na straně 24 dole).

, 2009/06/20 18:31

Ta Definice 1.2 není regulární gramatika ale obecná gramatika, regulární by měla mít množinu pravidel P ⊆ N x \Sigma*(N+ε)

You could leave a comment if you were logged in.
home/inf/ap8.txt · Poslední úprava: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
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