Obsah

AP8, IN8 Regulární jazyky
Diskuze

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. ¹⁾

Gramatika G je čtveřice (N, Sigma

, 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 → 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. ²⁾

Konečný automat M je pětice (Q, Sigma

, q₀, F), kde

Q je neprázdná konečná množina stavů,
je konečná množina vstupních symbolů (vstupní abeceda),
: Q x → Q je parciální přechodová funkce (: Q x → 2^Q totální v případě nedeterministického konečného automatu),
q₀ 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 *:

(q, ) = q pro každý stav q Q
(q, wa) =
- ((q, w), a) je-li (q, w) i ((q, w), a) definováno
- jinak

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

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

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

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:

, a a pro každé a jsou (základní) regulární výrazy nad .
Jsou-li E, F regulární výrazy nad , jsou také (E.F), (E + F) a (E*) regulární výrazy nad .
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() =
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:

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í)³⁾

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 ≠ epsilon

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

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 Sigma

*. Řekněme, že ~ je zprava invariantní (pravá kongruence), pokud pro každé u, v, w

* 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

* : uw

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ěta⁴⁾

Nechť L je jazyk nad Sigma

, 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 * s konečným indexem.
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í (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)

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 *, platí w L(M)?
prázdnost (jazyka): je L(M) = ?
univerzalita (jazyka): je L(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

Lemma 2.69⁵⁾

Ke každé regulární gramatice G =(N, Sigma

, P, S) existuje nedeterministický konečný automat M = (Q, Sigma

, q₀, 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 A → aB přidáme do delta (, a) stav overline{B} . Abychom se mohli vypořádat také s pravidly tvaru C → a, zavedeme speciální koncový stav q_f, který přidáme do delta ( overline{C} , a). Počáteční stav bude overline{S} , koncový stav q_f a případně také , pokud gramatika obsahuje pravidlo S → epsilon .

Konečný automat → regulární gramatika

Lemma 2.71⁶⁾

Pro každý konečný automat M = (Q, Sigma

, q₀, 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 S → epsilon , 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 → epsilon , 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 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 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 s eventuelní výjimkou pravidla S right epsilon , pokud se nevyskytuje na pravé straně žádného pravidla.