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

a
== Hogyan dönthető el egy nyelvről, hogy reguláris-e? ==
 
A reguláris nyelvek [[Form%C3%A1lis_nyelvtanFormális nyelvtan#A_ChomskyA Chomsky-f%C3%A9le_hierarchiaféle hierarchia|Chomsky-féle hierarchia]]beli helye szerint minden reguláris nyelv [[környezetfüggetlen nyelvtan|kö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örnyezetfüggetlen, de nem reguláris. Annak bizonyítására, hogy a fenti nem nem reguláris, a [[MyhillMyhill–Nerode-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 ''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'' ∈ ''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.
 
== Angol nyelvű forrás ==