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, hogyuw ∈ 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, , 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ú.
Kategória:Formális nyelvek Kategória:Számítógép-tudomány