AP8, IN8 Regulární jazyky

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

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

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)

Definice 1.2. ¹⁾

Gramatika G je čtveřice (N, , P, S), kde

• N je neprázdná konečná množina neterminálních symbolů (neterminálů),
• je konečná množina terminálních symbolů (terminálů) taková, že ; je množina všech symbolů gramatiky,
• P V*NV* x V* je konečná množina pravidel. Pravidlo obvykle zapisujeme ve tvaru (čteme „alfa přepiš na beta“),
• S 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 → //, pokud se //S nevyskytuje na pravé straně žádného pravidla.
Je to gramatika typu 3 podle Chomského hierarchie gramatik.

: Q x //* //→ Q definována 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

: Q x //* //→ 2^Q, definována induktivně vzhledem k délce slova ze *:

• (q, ) = {q}
• (q, wa) =

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

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

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

1. , a a pro každé a jsou (základní) regulární výrazy nad .
2. Jsou-li E, F regulární výrazy nad , jsou také (E.F), (E + F) a (E*) regulární výrazy nad .
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 popisuje jazyk L(E) nad abecedou podle těchto pravidel:

• L() =
• L() =
• L(a) = {a} pro každé a
• L(E.F) = L(E).L(F)
• L(E+F) = L(E) L(F)
• L(E*) = L(E)*

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

Lemma 2.13. (o vkládání)³⁾

Nechť L je regulární jazyk. Pak existuje n takové, že slovo w L, jehož délka je alespoň n, lze psát ve tvaru w = xyz, kde |xy| ≤ n, y ≠ a xyⁱz L pro každé i ₀.

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 (pumpovací konstanta)
• existuje takové w 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 y ≠
• existuje alespoň jedno i ₀ takové, že xyⁱz L

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

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

Definice – prefixová ekvivalence

Nechť L je libovolný (ne nutně regulární) jazyk nad abecedou . Na množině * definujeme relaci ~_L zvanou prefixová ekvivalence pro L takto:
u ~_L v w * : uw L vw 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 . 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 */~_L.

Věta 2.28 Myhill-Nerodova věta⁴⁾

Nechť L je jazyk nad , 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 * s konečným indexem.
3. Relace ~_L má konečný index.

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

• sjednocení (L₁ L₂),
• průnik (L₁ L₂),
• rozdíl (L₁ \ L₂),
• komplement (co–L),
• zřetězení (L₁.L₂)
• iteraci (L*),
• pozitivní iteraci (L⁺),
• zrcadlový obraz (reverzi) (L^R)

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 *, platí w L(M)?
• prázdnost (jazyka): je L(M) = ?
• univerzalita (jazyka): je L(M) = *?
• konečnost (jazyka): je L(M) konečný jazyk?

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.

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

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 S → , 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 S → , tak i pravostranné výskyty S) nalezneme ekvivalentní regulární gramatiku.

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í platí s eventuelní výjimkou pravidla pokud se nevyskytuje na pravé straně žádného pravidla.

• typ 2

Gramatika je typu 2, též bezkontextová, jestliže každé její pravidlo je tvaru , kde s eventuelní výjimkou pravidla pokud se nevyskytuje na pravé straně žádného pravidla.

• typ 3

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

Skripta Automaty a formální jazyky I
Slidy k předmětu Automaty a gramatiky

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

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