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

[ellenőrzött változat][nem ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
a ISBN/PMID link(ek) sablonba burkolása MediaWiki RfC alapján
34. sor:
== Hogyan dönthető el egy nyelvről, hogy reguláris-e? ==
 
A reguláris nyelvek [[Form%C3%A1lis_nyelvtan#A_Chomsky-f%C3%A9le_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 [[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.