Reguláris nyelv
Egy reguláris nyelv minden esetben egy formális nyelv (ugyanis: egy véges ábécéből létrehozható, véges hosszúságú sorozatokból álló, valószínűleg végtelen halmaz), ami kielégíti a következő ekvivalencia jellemzőket:
- elfogadja egy determinisztikus véges állapotú gép
- elfogadja egy nemdeterminisztikus véges állapotú gép
- elfogadja egy váltakozó véges automata
- leírható reguláris kifejezések alkalmazásával
- generálható egy reguláris nyelvtan által
- generálható egy prefix nyelvtan által
- elfogadja egy csak olvasó Turing-gép
- meghatározható egy monadikus másodrendű logika használatával
Reguláris nyelv egy adott ábécé felett
Egy adott Σ ábécé felett létező összes reguláris nyelvet a következő rekurzív definíciókkal adhatjuk meg:
- Az üres nyelv, Ø szabályos nyelv.
- Az üres string nyelv, {ε} szabályos nyelv.
- Ha a ∈ Σ, akkor az {a} által alkotott, egyelemű halmaz szabályos nyelv.
- Ha A és B szabályos nyelvek, akkor az A U B (union), az A • B (konkatenáció), és az A* (Kleene csillag) nyelvek szintén reguláris nyelvek.
- Az egyéb, Σ felett nem létező nyelv reguláris nyelv.
Minden véges nyelv szabályos. Például az {a, b} ábécé felett értelmezett nyelv, amely az összes páros számú a tartalmazza, vagy az a nyelv, amely tartalmazza az összes, a következő formában meghatározható stringet: különböző számú ak, amelyeket különböző számú bk követnek.
Ha egy nyelv nem szabályos, akkor a felismeréséhez legalább Ω(log log n) munkaterületre van szükség (ahol n a bemenő szimbólumsorozat hossza). A gyakorlatban a legtöbb nem reguláris probléma gépi megoldásához logaritmikus tér szükséges.
Zártsági tulajdonságok
A reguláris nyelvek zártak a következő műveletek szempontjából (abban az esetben, ha "L" és "P" reguláris nyelvek, akkor a következő nyelvek szintén reguláris nyelvek lesznek):
- a kiegészítő L-re
- a Kleene csillag L* L-re
- a homomorfizmus φ(L) L-re
- a konkatenáció LP, L és P között
- a unió L∪P , L és P között
- a közösrész L∩P,L és P között
- a különbség \, L és P között
Hogyan dönthető el egy nyelvről, hogy reguláris-e?
A reguláris nyelvek Chomsky-féle hierarchiabeli helye szerint minden reguláris nyelv környezetfüggetlen. A megállapítás visszafelé azonban nem igaz: például az a nyelv, amely tartalmazza az összes olyan stringet, amelyekben ugyanannyi a's van, mint b, az környezetfüggetlen, de nem reguláris. Annak bizonyítására, hogy a fenti nyelv nem reguláris, a Myhill–Nerode-tétel vagy a pumping lemma használható.
A következőkben két tisztán algebrai megközelítést mutatunk a szabályos nyelvek meghatározásra.
- Ha Σ véges ábécé és Σ* jelöli a Σ feletti szabad monoidot, amely tartalmazza a Σ feletti összes stringet, f : Σ* → M egy monoid homomorfizmus ahol M egy véges monoid, és S M részhalmaza, akkor az f ‒1(S) halmaz reguláris. Minden reguláris nyelv létrehozható ilyen módon.
- Ha L Σ* valamilyen részhalmaza, és definiáljuk a ~ ekvivalenciarelációt Σ* ra a következők alapján:
- u ~ v ami azt jelenti, hogy
- uw ∈ L akkor és csak akkor, ha vw ∈ L minden w ∈ Σ* esetén.
Az L nyelv akkor és csak akkor szabályos, ha az ~ ekvivalencia osztályainak száma véges; ebben az esetben, ez a szám azonos az L nyelvet elfogadó minimálautomata átmeneteinek számával.
Angol nyelvű forrás
- Michael Sipser "Introduction to the Theory of Computation", 1997, PWS Publishing, ISBN 0-534-94728-X, Chapter 1: Regular Languages, pp. 31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
Egyéb kapcsolat
- Department of Computer Science at the University of Western Ontario: Grail+, https://web.archive.org/web/20060404094049/http://www.csd.uwo.ca/Research/grail/. Szoftvercsomag reguláris kifejezések, véges állapotú gépek és véges nyelvek kezelésére. Nem kereskedelmi célokra szabad felhasználású.
Informatikai portál • összefoglaló, színes tartalomajánló lap