Bezkontextový jazyk: Porovnání verzí

'''Bezkontextový jazyk''' je [[formální jazyk]], který je akceptovaný nějakým [[zásobníkový automat|zásobníkovým automatem]]. Bezkontextové jazyky mohou být vygenerovány bezkontextovými gramatikami (viz [[Chomského hierarchie]]).

 

Typickým příkladem bezkontextového jazyka je <math>L = \{a^nb^n:n\geq1\}</math>, jazyk všech slov sudé délky ve kterých první polovinu tvoří znaky <math>a</math> a druhou polovinu znaky <math>b</math>. <math>L</math> je generovaný [[formální gramatika|gramatikou]] <math>S\to aSb ~|~ ab</math> a je akceptovaný [[zásobníkový automat|zásobníkovým automatem]] <math>M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\})</math> kde <math>\delta</math> je definována následovně:

 

<center>

</center>

 

Bezkontextové jazyky jsou využívány především v [[programovací jazyk|programovacích jazycích]]. Například ''dobře uzávorkovaný výraz'' (tj. výraz, kde počet '(' je stejný jako počet ')') je generován gramatikou <math>S\to SS ~|~ (S) ~|~ \lambda</math> nebo také <math>S\to S(S) ~|~ \lambda</math>

 

Bezkontextové jazyky jsou [[uzávěr množiny|uzavřeny]] na zřetězení, [[sjednocení]] a [[rozdíl množin|rozdíl]] s [[regulární jazyk|regulárním jazykem]], ale ne na [[průnik]] a [[rozdíl množin|rozdíl]].

 

Pro bezkontextové jazyky existuje [[lemma o vkládání]] (pumping lemma) které udává nezbytnou podmínku, kterou musí jazyk splňovat, aby byl bezkontextový.