Kontekstno neovisni jezik: razlika između inačica

'''Kontekstno neovisni jezik''' (rjeđe još i '''kontekstno slobodni jezik''') je [[formalni jezik]] koji je element skupa jezika kojeg definiraju [[kontekstno neovisna gramatika|kontekstno neovisne gramatike]]. Skup kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju [[potisni automat|potisni automati]].

 

Kanonski primjer kontekstno neovisnog jezika jest <math>L = \{a^nb^n:n\geq1\}</math>, jezik svih nepraznih nizova znakova (simbola) parne duljine, čiju prvu polovicu čine znakovi <math>a</math>, dok drugu polovicu čine znakovi <math>b</math>. <math>L</math> generira gramatika <math>S\to aSb ~|~ ab</math> te prihvaća potisni automat <math>M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\})</math> gdje je funkcija prijelaza <math>\delta</math> definirana na sljedeći način: