Szabályos nyelv

A Wikipédiából, a szabad lexikonból.

Egy szabályos 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ó szabályos kifejezések alkalmazásával
• generálható egy szabályos 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

Tartalomjegyzék 1 Szabályos nyelv egy adott ábécé felett 2 Zártsági tulajdonságok 3 Hogyan dönthető el egy nyelvről, hogy szabályos-e 4 Angol nyelvű forrás 5 Egyéb kapcsolat

[szerkesztés] Szabályos nyelv egy adott ábécé felett

Egy adott Σ ábécé felett létező összes szabályos nyelvet a követekező 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 szabályos nyelvek.
• Az egyéb, Σ felett nem létező nyelv szabályos 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 szabályos probléma gépi megoldásához logaritmikus tér szükséges.

[szerkesztés] Zártsági tulajdonságok

A szabályos nyelvek zártak a következő műveletek szempontjából (abban az esetben, ha "L" és "P" szabályos nyelvek, akkor a következő nyelvek szintén szabályos nyelveke 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\P, L és P között

[szerkesztés] Hogyan dönthető el egy nyelvről, hogy szabályos-e

A szabályos nyelvek Chomsky féle hierarchiabeli helye szerint minden szabályos nyelv környezet független. A megállapítás visszafelé azonban nem igaz: pédául az a nyelv, amely tartalmazza az összes olyan stringet, amelyekben ugyanannyi a's van, mint b, az környezet független, de nem szabályos. Annak bizonyítására, hogy a fenti nem nem szabályos, a Myhill-Nerode tétel vagy a pumping lemma használható.

A következőkben két tisztán algebarai 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 ⁻¹(S) halmaz szabályos, reguláris. Minden szabályos nyelv létrehozható ilyen módon.

• Ha L Σ* valamilyen részhalmaza, és definiáljuk a ~ ekvivalencia relácó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.

[szerkesztés] 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.

[szerkesztés] Egyéb kapcsolat

• Department of Computer Science at the University of Western Ontario: Grail+, http://www.csd.uwo.ca/Research/grail/. Szoftvercsomag szabályos kifejezések, véges állapotú gépek és véges nyelvek kezelésére. Nem kereskedelmi célokra szabad felhasználású.