Főmenü megnyitása

Módosítások

nincs szerkesztési összefoglaló
{{lektor|2006 februárjábó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]]
 
==Szabályos nyelv egy adott ábécé felett==
Egy adott Σ ábécé felett létező összes szabályos nyelvet a követekező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 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ú ''a''k, amelyeket különböző számú ''b''k 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.
 
== Zártsági tulajdonságok ==
* a [[Kleene csillag]] ''L''<sup>*</sup> ''L''-re
* a [[homomorfizmus]] φ(L) ''L''-re
* a [[konkatenáció]] ''LP'', ''L'' és ''P'' között
* a [[unió (halmazelmélet)|unió]] ''L''∪''P'' , ''L'' és ''P'' között
* a [[közösrész]] ''L''∩''P'',''L'' és ''P'' között
== Hogyan dönthető el egy nyelvről, hogy szabályos-e ==
 
A szabályos nyelvek [[Chomsky -féle hierarchia]]beli helye szerint minden szabályos nyelv [[környezet független nyelvtan|környezet fü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ö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 algebaraialgebrai megközelítést mutatunk a szabályos nyelvek meghatározásra.
*Ha Σ véges ábécé és Σ* jelöli a Σ feletti [[szabad monoid]]ot, amely tartalmazza a Σ feletti összes stringet, &nbsp;''f'' : Σ* → ''M'' egy [[monoid homomorfizmus]] ahol ''M'' egy ''véges'' monoid, és ''S'' ''M'' részhalmaza, akkor az ''f''<sup>&nbsp;‒1</sup>(''S'') halmaz szabályos, reguláris. Minden szabályos 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'' &isin; ''L'' akkor, és csak akkor, ha ''vw'' &isin; ''L'' minden ''w'' &isin; &Sigma;* 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 ==
69 449

szerkesztés