Főmenü megnyitása

Módosítások

Egyelőre szabályos → reguláris, aztán majd végig kell még nézni
Egy '''szabályosregulá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ó [[szabályosreguláris kifejezések]] alkalmazásával
* generálható egy [[szabályosregulá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
 
==SzabályosReguláris nyelv egy adott ábécé felett==
Egy adott Σ ábécé felett létező összes szabályosregulá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 szabályosreguláris nyelvek.
* Az egyéb, Σ felett nem létező nyelv szabályosregulá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ú ''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ályosreguláris probléma gépi megoldásához [[logaritmikus tér]] szükséges.
 
== Zártsági tulajdonságok ==
A szabályosreguláris nyelvek [[zárt (matematika)|zárt]]ak a következő műveletek szempontjából (abban az esetben, ha "L" és "P" szabályosreguláris nyelvek, akkor a következő nyelvek szintén szabályosreguláris nyelvekenyelvek lesznek):
 
* a [[komplemens|kiegészítő]] <math>\bar{L}</math> ''L''-re
* a [[különbség]] <math>L</math>\<math>P</math>, ''L'' és ''P'' között
 
== Hogyan dönthető el egy nyelvről, hogy szabályosreguláris-e? ==
 
A szabályosreguláris nyelvek [[Chomsky-féle hierarchia]]beli helye szerint minden szabályosreguláris nyelv [[környezet függetlenkörnyezetfüggetlen nyelvtan|környezet függetlenkö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örnyezet függetlenkörnyezetfüggetlen, de nem szabályosreguláris. Annak bizonyítására, hogy a fenti nem nem szabályosregulá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 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ályosregulá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:
== Egyéb kapcsolat ==
 
* Department of Computer Science at the University of Western Ontario: ''Grail+'', http://www.csd.uwo.ca/Research/grail/. Szoftvercsomag szabályosreguláris kifejezések, véges állapotú gépek és véges nyelvek kezelésére. Nem kereskedelmi célokra szabad felhasználású.
 
{{Portál|Informatika|i }}