Формална граматика — разлика између измена

 

 

Језик дефинисан у претходном примеру није контексно слободан, и то се може строго доказати кориштењем леме о проширењу за контексно слободне језике, али, на пример језик <math>\left \{ a^{n}b^{n} | n \ge 1 \right \}</math> (тј. бар један знак <math>a</math> након кога следи исто толико знакова <math>b</math>) јесте контексно слободан, пошто га генерише граматика <math>G_2</math> са <math>N=\left \{S\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math>, при чему је <math>S</math> почетни незавршни симбол, а правила су:

 

 

Контексно слободан језик може бити препознат у времену <math>O(n^3)</math> користећи алгоритме као што је Ојлеров алгоритам. Другим речима, за сваки контексно слободан језик се може изградити машину која на улазу прима неки низ знакова и одређује у <math>O(n^3)</math> времену припада ли ниска језику, при чему је <math>n</math> дужина низа симбола за ту ниску. Надаље, неки важни подскупови контекстно слободних језика могу бити препознати у линеарном времену користећи друге алгоритме.

 

==Практична примена==