Википедија

Индексирана граматика — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м ispravke
м Бот: исправљена преусмерења
Ред 1:
'''Индексирана граматика''' је [[формална граматика]] која описује [[индексиранииндексиран језик|индексиране језике]]. Индексиране граматике имају три дискјунктна скупа симбола: поред уобичајених завршних и незавршних симбола садржи и индексе, који се појављују само у средишњим корацима извођења.
 
Правила извођења могу да замене незавршни симбол ниском завршних и незавршних симбола као у контекстно слободним граматикама, али могу такође да замене незавршни симбол незавршним симболом иза кога следи индекс, као и незавршни симбол иза кога следи индекс незавршним симболом.
 
Индекси могу да се појављују само након незавршног симбола или другог индекса, тако да сваки незавршни симбол може да се сматра ''власником'' индекаса који следе иза њега, а који формирају [[стек (структураапстрактни тип података)|стек]].
 
У пракси, стекови индекаса могу да броје и памте која правила су примењена којим редоследом. На пример, индексиране граматике могу да опишу овај не-контекстно слободни језик:
Ред 21:
Стек -{''g''}--ова који расте у средини броји колико пута (<math>n-1</math>) је A било замењено једним -{''a''}- и једним -{''c''}-; свако -{''g''}- на крају постаје завршни симбол -{''b''}-.
 
Проблем одређивања да ли дату ниску препознаје дата индексирана граматика је [[НП-комплетносткомплетни проблеми|НП-комплетан]].<ref name=Hopcroft_and_Ullman/>
 
== Линеарне индексиране граматике ==
Преузето из „https://sr.wikipedia.org/wiki/Индексирана_граматика”