„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 |
→Hogyan dönthető el egy nyelvről, hogy reguláris-e?: Link a Chomsky-féle hierarchiára |
||
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.
|