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

(1 forrás archiválása és 0 megjelölése halott linkként. #IABot (v2.0beta9))
 
== Hogyan dönthető el egy nyelvről, hogy reguláris-e? ==
 
A reguláris nyelvek [[Formális nyelvtan#A Chomsky-fé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 nemnyelv nem regulá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.
Névtelen felhasználó