Kontekstno nezavisni jezik – razlika između verzija

Uklonjeni sadržaj Dodani sadržaj
Legobot (razgovor | doprinos)
m Bot: migracija 1 međuwiki veza sada dostupnih na stranici d:q729271 na Wikidati
Kolega2357 (razgovor | doprinos)
m robot kozmetičke promjene
Red 5:
 
<center>
<math>\delta(q_0, a, z) = (q_0, a)</math><br />
<math>\delta(q_0, a, a) = (q_0, a)</math><br />
<math>\delta(q_0, b, a) = (q_1, x)</math><br />
<math>\delta(q_1, b, a) = (q_1, x)</math><br />
<math>\delta(q_1, \lambda, z) = (q_f, z)</math>
 
<math>\delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})</math><br />
where <math>z</math> je početni simbol steka a <math>x</math> predstavlja akciju skidanja sa steka.
</center>
Red 30:
 
=== Nezatvorenost u odnosu na presek ===
Kontekstno slobodni jezici nisu zatvoreni za presek. Ovo se može videti ako se uzmu jezici <math>A = \{a^m b^n c^n \mid m, n \geq 0 \}</math> i <math>B = \{a^n b^n c^m \mid m,n \geq 0\}</math>, koji su oba konetksno slobodna. Njihov presek je <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math>, za šta se može pokazati da nije kontekstno slobodan jezik [[pamping lema za kontekstno slobodne jezike|pamping lemom za kontekstno slobodne jezike]].
 
== Svojstva odlučivosti ==
Sledeći problemi su [[odlučivost|neodlučivi]] za proizvoljne [[kontekstno-slobodna gramatika|kontekstno slobodne gramatike]] -{A}- i -{B}-:
* Ekvivalencija: da li je <math>L(A)=L(B)</math>?
* da li je <math>L(A) \cap L(B) = \emptyset </math> ?
* da li je <math>L(A)=\Sigma^*</math> ?
* da li je <math>L(A) \subseteq L(B)</math> ?
 
Sledeći problemi su odlučivi za proizvoljne kontekstno slobodne gramatike:
* da li je <math>L(A)=\emptyset</math>?
* da li je <math>L(A)</math> konačan?
* Pripadnost: za svaku datu reč <math>w</math>, da li je <math>w \in L(A)</math> ? (problem pripadnosti je čak odlučiv u polinomijalnom vremenu - videti -{[[algoritam CYK]]}-)
 
== Svojstva kontekst-slobodnih jezika ==