„Reguláris nyelv” változatai közötti eltérés

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:

Egy adott Σ ábécé felett létező összes szabályos nyelvet a követekezőkövetkező rekurzív definíciókkal adhatjuk meg:

* 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.

* a [[konkatenáció]] ''LP'', ''L'' és ''P'' között

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,  ''f'' : Σ* → ''M'' egy [[monoid homomorfizmus]] ahol ''M'' egy ''véges'' monoid, és ''S'' ''M'' részhalmaza, akkor az ''f''^ ‒1(''S'') halmaz szabályos, reguláris. Minden szabályos nyelv létrehozható ilyen módon.

:''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.

* [[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.