Изворни код странице Контекст-слободни језик

У [[формална теорија језика|формалној теорији језика]], '''контекстно слободни језик''' је [[формални језик|језик]] који генерише нека [[контекстно-слободна граматика]]. Скуп свих контекстно слободних језика је идентичан скупу језика које прихватају [[потисни аутомат]]и.

== Примери ==
Класичан пример контекстно слободног језика је <math>L = \{a^nb^n:n\geq1\}</math>, језик свих непразних [[ниска|ниски]] парне дужине, чије ја прва половина састављена од слова <math>a</math>, а друга половина је састављена од слова <math>b</math>. <math>L</math> је генерисан граматиком <math>S\to aSb ~|~ ab</math>, а прихвата га потисни аутомат <math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, \{q_f\})</math> где је <math>\delta</math> дефинисано на следећи начин:

<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> је почетни симбол стека а <math>x</math> представља акцију скидања са стека.
</center>

Контекстно слободни језици имају многе примене у [[програмски језик|програмским језицима]]; на пример, [[Дајков језик|језик свих исправно упарених заграда]] је генерисан граматиком <math>S\to SS ~|~ (S) ~|~ \lambda</math>. Такође, већина аритметичких израза су генерисани контекстно слободним граматикама.


== Својства затворења ==
Контекстно слободни језици су [[затворење (математика)|затворени]] у односу на следеће операције. То јест, ако су ''-{L}-'' и ''-{P}-'' контекстно слободни језици, а ''-{D}-'' је [[регуларан језик]], онда су и следећи језици контекстно-слободни:

* [[Клинијева звезда]] <math>L^*</math> од ''-{L}-''
* слика -{φ(L)}- од ''-{L}-'' за [[хомоморфизам]] -{φ}- 
* [[конкатенација]] (дописивање) <math>L \circ P</math> језика ''-{L}-'' и ''-{P}-''
* [[унија (теорија скупова)|унија]] <math>L \cup P</math> језика ''-{L}-'' и ''-{P}-''
* [[пресек (теорија скупова)|пресек]] (са регуларниим језиком) <math>L \cap D</math> језика ''-{L}-'' и ''-{D}-''

Контекстно слободни језици нису затворени за комплемент, пресек и разлику.

=== Незатвореност у односу на пресек ===
Контекстно слободни језици нису затворени за пресек. Ово се може видети ако се узму језици <math>A = \{a^m b^n c^n \mid m, n \geq 0 \}</math> и <math>B = \{a^n b^n c^m \mid m,n \geq 0\}</math>, који су оба конетксно слободна. Њихов пресек је <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math>, за шта се може показати да није контекстно слободан језик [[пампинг лема за контекстно слободне језике|пампинг лемом за контекстно слободне језике]].

== Својства одлучивости ==
Следећи проблеми су [[одлучивост|неодлучиви]] за произвољне [[контекстно-слободна граматика|контекстно слободне граматике]] -{A}- и -{B}-:
* Еквиваленција: да ли је <math>L(A)=L(B)</math>?
* да ли је <math>L(A) \cap L(B) = \emptyset </math> ?
* да ли је <math>L(A)=\Sigma^*</math> ?
* да ли је <math>L(A) \subseteq L(B)</math> ?

Следећи проблеми су одлучиви за произвољне контекстно слободне граматике:
* да ли је <math>L(A)=\emptyset</math>?
* да ли је <math>L(A)</math> коначан?
* Припадност: за сваку дату реч <math>w</math>, да ли је <math>w \in L(A)</math> ? (проблем припадности је чак одлучив у полиномијалном времену - видети -{[[алгоритам CYK]]}-)

== Својства контекст-слободних језика ==
* Језик обратан контекстно слободном језику је контекстно слободан, али његов комплемент не мора да буде.
* Сваки [[регуларан језик]] је контекстно слободан јер може да се опише [[регуларна граматика|регуларном граматиком]]. 
* Пресек контекстно слободног језика и регуларног језика је увек контекстно слободан. 
* Постоје [[контекстно сензитиван језик|контекстно сензитивни језици]] који нису контексткно слободни.
* У доказивању да неки језик није контекстно слободан може да се користи [[пампинг лема за контекстно слободне језике]].

== Литература ==
* {{Cite book |ref= harv|author=Seymour Ginsburg | title = The Mathematical Theory of Context-Free Languages |url= https://archive.org/details/mathematicaltheo0000gins|year=1966| publisher = McGraw-Hill, Inc. | location = New York, NY, USA}}
* {{Cite book |ref= harv|author=Michael Sipser |year=1997| title = Introduction to the Theory of Computation |url= https://archive.org/details/introductiontoth00sips| publisher = PWS Publishing |isbn=978-0-534-94728-6|chapter=Context-Free Languages|pages=pp-91–122}}

{{формални језици и граматике}}

{{нормативна контрола}}

[[Категорија:Формални језици]]