Regularni jezik: razlika između inačica

Izbrisani sadržaj Dodani sadržaj
Addbot (razgovor | doprinosi)
m Bot: brisanje 20 međuwiki poveznica premještenih u stranicu d:q752532 na Wikidati
Nema sažetka uređivanja
Redak 35:
== Odlučivanje regularnosti jezika ==
 
Da bismo locirali regularne jezike u [[Chomskyjeva hijerarhija|Chomskyjevoj hijerarhiji]], možemo prvo primjetitiprimijetiti da je svaki regularni jezik [[kontekstno neovisni jezik|kontekstno neovisan]]. Obrat ne vrijedi: primjer je jezik koji sadrži jednak broj znakova ''a'' i ''b'', koji je neregularan kontekstno neovisan jezik. Za dokaz neregularnosti jezika poput takvog može se koristiti [[Myhill-Nerode teorem]] ili [[svojstvo napuhavanja]].
 
Postoje dva čisto algebarska pristupa prilikom definiranja regularnih jezika. Ako je &Sigma; konačna abeceda i &Sigma;* označava slobodni monoid nad &Sigma; ako se sastoji od svih nizova znakova nad &Sigma;, &nbsp;''f'' : &Sigma;* &rarr; ''M'' je monoidni homeomorfizam pri čemu je ''M'' ''konačni'' monoid, ''S'' podskup skupa ''M'', i pri tome je skup ''f''<sup>&nbsp;&minus;1</sup>(''S'') regularan. Svaki regularni jezik može iznići na ovakav način.