„Reguláris nyelv” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a kategóriák új sorba rendezése |
aNincs szerkesztési összefoglaló |
||
1. sor:
{{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]]
9. sor:
* elfogadja egy csak olvasó [[Turing-gép]]
* meghatározható egy [[monadikus]] [[másodrendő logika]] használatával
==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:
| |||