Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 70:
 
[[Контекстно слободна граматика]] је граматика у којој се лева страна правила састоји само од једног [[Завршни и незавршни симболи|нетерминалног симбола]]. Ово ограничење није нетривијално; контексно слободна граматика не може генерисати све језике. Оне које може зовемо контексно слободним језицима.
Језик дефинисан у претходном примеру ''није'' контексно слободан, и то се може строго доказати кориштењем [[леме о проширењуразрастању]] за контексно слободне језике, али, на пример језик <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> почетни незавршни симбол, а правила су:
 
: 1. <math>S \rightarrow aSb</math>
Ред 76:
 
Контексно слободан језик може бити препознат у времену <math>O(n^3)</math> користећи алгоритме као што је [[Ојлер|Ојлеров]] алгоритам. Другим речима, за сваки контексно слободан језик се може изградити машина која на улазу прима неки низ знакова и одређује у <math>O(n^3)</math> времену да ли ниска припада [[језик|језику]], при чему је <math>n</math> дужина низа симбола за ту ниску. Надаље, неки важни подскупови контекстно слободних језика могу бити препознати у линеарном времену користећи друге алгоритме.
 
 
== Други облици генеративних граматика ==
Преузето из „https://sr.wikipedia.org/wiki/Формална_граматика”