Szabályos nyelv

A reguláris nyelv ( reguláris halmaz ) a formális nyelvek elméletében olyan szavak halmaza , amely felismer valamilyen véges automatát . A szabályos halmazok osztálya kényelmesen tanulmányozható, és a kapott eredmények a formális nyelvek meglehetősen széles körére alkalmazhatók.

Definíció

Legyen véges ábécé . Az ábécé reguláris nyelvei az indukcióval meghatározott szavak halmazai az alábbiak szerint: $\Sigma$ $\Sigma$

Az üres halmaz ( ) egy reguláris nyelv. $\varnothing$
A csak egy üres karakterláncból ( ) álló halmaz reguláris nyelv. ${\displaystyle \{\varepsilon \))$
Az egybetűs szóból ( , ahol ) álló halmaz reguláris nyelv. ${\displaystyle \{a\))$ $a\in\Sigma$
Ha a és reguláris nyelvek, akkor az egyesülésük ( ), az összefűzésük ( ) és a Kleene csillag felvétele ( ) is reguláris nyelvek. $\alpha$ $\beta$ $\alpha \cup \beta$ $\alpha \beta$ $\alpha ^{*}$
Nincsenek más szabályos nyelvek.

Kapcsolat az automaták és a reguláris nyelvek között

Kleene tétele kimondja, hogy a reguláris nyelvek osztálya ugyanaz, mint a véges automata által felismert nyelvek osztálya . Ez azt jelenti, hogy bármely véges állapotú gép esetében az általa megengedett szavak halmaza reguláris nyelv. És fordítva, minden reguláris nyelvhez létezik egy automata, amely engedélyezi az ebből a nyelvből származó szavakat, és csak azokat.

Egy monoid felismerhető részhalmaza

Ez a fogalom tetszőleges monoidra általánosítható. Egy M monoid L részhalmazát felismerhetjük M felett , ha létezik M felett olyan véges automata , amely elfogadja L -t. Az M feletti véges automata olyan automata, amely M - ből veszi az elemeket bemenetként . Az M monoid felismerhető részhalmazainak családját általában [1] jelölik . $\mathrm {Rec} (M)$

Tehát ha M egy szabad monoid az ábécé felett , akkor a család egyszerűen reguláris nyelvek családja . $\Sigma ^{*}$ $\Sigma$ $\mathrm {Rec} \left(\Sigma ^{*}\right)$ $\mathrm {Reg} \left(\Sigma ^{*}\right)$

Lásd még

A reguláris nyelvek zárt tulajdonsága

Jegyzetek

↑ Jean-Eric Pin, Mathematical Foundations of Automata Theory Archiválva : 2014. szeptember 10., a Wayback Machine , IV. fejezet: Felismerhető és racionális halmazok

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus