====== 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 <m>Sigma</m> je libovolná konečná posloupnost znaků této abecedy
**Jazyk** nad abecedou <m>Sigma</m> je libovolná množina slov nad <m>Sigma</m>


===== 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 ====
<box 90% round blue|Definice 1.2. ((viz skripta Automaty a formální jazyky I, str. 4))>**Gramatika** //G// je čtveřice (//N//, <m>Sigma</m>, //P//, //S//), kde
  * //N// je neprázdná konečná množina neterminálních symbolů (**neterminálů**),
  * <m>Sigma</m> je konečná množina terminálních symbolů (**terminálů**) taková, že <m>N inter Sigma = varnothing</m>; <m>N union Sigma = V</m> je množina **všech symbolů** gramatiky,
  * //P// <m>⊆</m> //V*NV* x V*// je konečná množina **pravidel**. Pravidlo <m>(alpha, beta)</m> obvykle zapisujeme ve tvaru  <m>alpha right beta</m> (čteme "alfa přepiš na beta"),
  * //S// <m>in</m> //N// je **počáteční** neterminál, neboli kořen gramatiky.
</box> 

**Gramatika** je **regulární**, jestliže každé její pravidlo je tvaru //A -> aB// nebo //A -> a// s výjimkou //S -> //<m>epsilon</m>, pokud se //S// nevyskytuje na pravé straně žádného pravidla. 
Je to gramatika typu 3 podle //Chomského hierarchie gramatik//.

==== Konečný automat ====
<box 90% round blue|Definice 2.1. ((viz skripta Automaty a formální jazyky I, str. 11))>**Konečný automat** //M// je pětice (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//), kde
  * //Q// je neprázdná konečná množina **stavů**,
  * <m>Sigma</m> je konečná množina **vstupních symbolů** (vstupní abeceda),
  * <m>delta</m>: //Q x //<m>Sigma</m> //-> Q// je parciální **přechodová funkce** (<m>delta</m>: //Q x //<m>Sigma</m>// -> 2<sup>Q</sup>// totální v případě nedeterministického konečného automatu),
  * //q<sub>0</sub>// <m>in</m> //Q// je **počáteční stav**,
  * //F// <m>⊆</m> //Q// je množina **koncových stavů**
</box>

=== Rozšířená přechodová funkce deterministického konečného automatu: ===
<m>hat{delta}</m>: //Q x //<m>Sigma</m>* //-> Q// definována induktivně vzhledem k délce slova ze <m>Sigma</m>*:
  * <m>hat{delta}</m>(//q//, <m>epsilon</m>) = //q// pro každý stav //q// <m>in</m> //Q//
  * <m>hat{delta}</m>(//q//, //wa//) = 
    *<m>delta</m>(<m>hat{delta}</m>(//q//, //w//), //a//) je-li <m>hat{delta}</m>(//q//, //w//) i <m>delta</m>(<m>hat{delta}</m>(//q//, //w//), //a//) definováno
    *<m>ortho</m> jinak

=== Rozšířená přechodová funkce nedeterministického konečného automatu: ===
<m>hat{delta}</m>: //Q x //<m>Sigma</m>* //-> 2<sup>Q</sup>//, definována induktivně vzhledem k délce slova ze <m>Sigma</m>*:
  * <m>hat{delta}</m>(//q//, <m>epsilon</m>) = {q}
  * <m>hat{delta}</m>(//q//, //wa//) = <m>bigcup{p in hat{delta}(q,w)}{}{delta(p,a)}</m>

=== 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 [[home:inf:ap9|AP9,IN9 Konečné automaty]]

==== Regulární výrazy ====
Množina **regulárních výrazů** nad abecedou <m>Sigma</m>, označovaná //RE//(<m>Sigma</m>), je definována induktivně takto:
  - <m>epsilon</m>, <m>varnothing</m> a //**a**// pro každé //a// <m>in</m> <m>Sigma</m> jsou (základní) regulární výrazy nad <m>Sigma</m>.
  - Jsou-li //E//, //F// regulární výrazy nad <m>Sigma</m>, jsou také (//E.F//), (//E// + //F//) a (//E*//) regulární výrazy nad <m>Sigma</m>.
  - 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 <m>Sigma</m> popisuje jazyk //L(E)// nad abecedou <m>Sigma</m> podle těchto pravidel:
  * L(<m>epsilon</m>) = <m>{epsilon}</m>
  * L(<m>varnothing</m>) = <m>varnothing</m>
  * L(**a**) = {a} pro každé //a// <m>in</m> <m>Sigma</m>
  * L(E.F) = L(E).L(F)
  * L(E+F) = L(E) <m>union</m> L(F)
  * L(E*) = L(E)*
Ekvivalenci mezi regulárními výrazy a konečnými automaty shrnuje **Kleeneho veta**:
<box 95% round green|Kleeneho věta>Libovolný jazyk je popsatelný regulárním výrazem, právě když je rozpoznatelný konečným automatem.</box>

==== Lemma o vkládání (pumping lemma) ====
<box 90% round green|Lemma 2.13. (o vkládání)((viz skripta Automaty a formální jazyky I, str. 18))>Nechť //L// je regulární jazyk. Pak existuje //n// <m>in</m> <m>bbN</m> takové, že slovo //w// <m>in</m> //L//, jehož délka je alespoň //n//, lze psát ve tvaru //w// = //xyz//, kde |//xy//| ≤ //n//, //y// ≠ <m>epsilon</m> a //xy<sup>i</sup>z// <m>in</m> //L// pro každé //i// <m>in</m> <m>bbN</m><sub>0</sub>.
</box>

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// <m>in</m> <m>bbN</m> (pumpovací konstanta)
  * existuje takové //w// <m>in</m> //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// ≠ <m>epsilon</m>
  * existuje alespoň jedno //i// <m>in</m> <m>bbN</m><sub>0</sub> takové, že //xy<sup>i</sup>z// <m>notin</m> //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ů:
<box 90% round | Definice -- pravá kongruence >nechť <m>Sigma</m> je abeceda a nechť ~ je ekvivalence na <m>Sigma</m>*. Řekněme, že ~ je **zprava invariantní (pravá kongruence)**, pokud pro každé //u//, //v//, //w// <m>in</m> <m>Sigma</m>* platí //u// ~ //v// <m>doubleright</m>  //uw// ~ //vw//. Index ~ je počet tříd rozkladu <m>Sigma</m>*/~ (pokud je těchto tříd nekonečně mnoho, klademe index ~ roven <m>infty</m>).
</box>

<box 90% round | Definice -- prefixová ekvivalence>Nechť //L// je libovolný (ne nutně regulární) jazyk nad abecedou <m>Sigma</m>. Na množině <m>Sigma</m>* definujeme relaci ~//<sub>L</sub>// zvanou **prefixová ekvivalence** pro //L// takto:
//u// ~//<sub>L</sub>// //v// <m>doubleleftright</m>  <m>forall</m>//w// <m>in</m> <m>Sigma</m>* : //uw// <m>in</m> //L// <m>doubleleftright</m>  //vw// <m>in</m> //L//
Tedy ~//<sub>L</sub>// 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.
</box>

<box 90% round green | Lemma> Nechť //L// je libovolný jazyk nad <m>Sigma</m>. Pak relace ~//<sub>L</sub>// je pravá kongruence a //L// lze vyjádřit jako sjednocení některých (ne nutně konečně mnoha) tříd rozkladu <m>Sigma</m>*/~//<sub>L</sub>//.
</box>

<box 90% round green|Věta 2.28 Myhill-Nerodova věta((viz skripta Automaty a formální jazyky I, str. 25))>Nechť //L// je jazyk nad <m>Sigma</m>, pak tato tvrzení jsou ekvivalentní:
  - //L// je rozpoznatelný konečným automatem.
  - //L// je sjednocením některých tříd rozkladu určeného pravou kongruencí na <m>Sigma</m>* s konečným indexem.
  - Relace ~//<sub>L</sub>// má konečný index.
</box>

===== Vlastnosti regulárních jazyků =====

==== Uzávěrové vlastnosti ====
Třída regulárních jazyků je uzavřena na:
  * **sjednocení** (//L<sub>1</sub>// <m>union</m> //L<sub>2</sub>//),
  * **průnik** (//L<sub>1</sub>// <m>inter</m> //L<sub>2</sub>//),
  * **rozdíl** (//L<sub>1</sub>// \ //L<sub>2</sub>//),
  * **komplement** (co--//L//),
  * **zřetězení** (//L<sub>1</sub>//.//L<sub>2</sub>//)
  * **iteraci** (//L//*),
  * **pozitivní iteraci** (//L//<sup>+</sup>),
  * **zrcadlový obraz (reverzi)** (//L<sup>R</sup>//)

==== 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//) <m>⊆</m> //L//(//M'//)?
  * **příslušnost** (slova k jazyku): je-li dáno //w// <m>in</m> <m>Sigma</m>*, platí //w// <m>in</m> //L//(//M//)?
  * **prázdnost** (jazyka): je //L//(//M//) = <m>varnothing</m>?
  * **univerzalita** (jazyka): je //L//(//M//) = <m>Sigma</m>*?
  * **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 ====
<box 90% round blue|Lemma 2.69((viz skripta Automaty a formální jazyky I, str. 49))>Ke každé regulární gramatice //G// =(//N//, <m>Sigma</m>, //P//, //S//) existuje nedeterministický konečný automat //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) takový, že //L//(//G//) = //L//(//M//).
(Důkaz viz skripta z Automatů a formálních jazyků I, str. 49)
</box>

=== Myšlenka důkazu: ===
Stavy automatu budou odpovídat neterminálům gramatiky, tj. pro každý neterminál //A// bude existovat stav <m>overline{A}</m>. Pro každé pravidlo //A// -> //aB// přidáme do <m>delta</m>(<m>overline{A}</m>, //a//) stav <m>overline{B}</m>. Abychom se mohli vypořádat také s pravidly tvaru //C// -> //a//, zavedeme speciální koncový stav //q<sub>f</sub>//, který přidáme do <m>delta</m>(<m>overline{C}</m>, //a//). Počáteční stav bude <m>overline{S}</m>, koncový stav //q<sub>f</sub>// a případně také <m>overline{S}</m>, pokud gramatika obsahuje pravidlo //S// -> <m>epsilon</m>.

==== Konečný automat → regulární gramatika ====
<box 90% round blue|Lemma 2.71((viz skripta Automaty a formální jazyky I, str. 50))>Pro každý konečný automat //M// = (//Q//, <m>Sigma</m>, <m>delta</m>, //q<sub>0</sub>//, //F//) existuje regulární gramatika //G// =(//N//, <m>Sigma</m>, //P//, //S//) taková, že //L//(//M//) = //L//(//G//).
(Důkaz viz skripta z Automatů a formálních jazyků I, str. 50)
</box>

=== 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 //S// -> <m>epsilon</m>, 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// -> <m>epsilon</m>, 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í <m>alpha right beta</m> platí <m>delim{|}{alpha}{|} <= delim{|}{beta}{|}</m> s eventuelní výjimkou pravidla <m>S right epsilon</m>  pokud se <m>S</m> nevyskytuje na pravé straně žádného pravidla.

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

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

===== Literatura =====
[[http://is.muni.cz/elportal/estud/fi/js06/ib005/Formalni_jazyky_a_automaty_I.pdf|Skripta Automaty a formální jazyky I]]
[[http://www.fi.muni.cz/~xstrejc/IB102/slajdy/slajdy_corr.pdf|Slidy k předmětu Automaty a gramatiky]]

===== 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 [[http://statnice.dqd.cz/tmp/regularni_jazyky.pdf|poznámky od Jitky Pospíšilové]].

~~DISCUSSION~~