Kontekstno nezavisni jezik – razlika između verzija
Uklonjeni sadržaj Dodani sadržaj
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
== 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 ==
|