Индексирана граматика

С Википедије, слободне енциклопедије

Индексирана граматика је формална граматика која описује индексиране језике. Индексиране граматике имају три дискјунктна скупа симбола: поред уобичајених завршних и незавршних симбола садржи и индексе, који се појављују само у средишњим корацима извођења.

Правила извођења могу да замене незавршни симбол ниском завршних и незавршних симбола као у контекстно слободним граматикама, али могу такође да замене незавршни симбол незавршним симболом иза кога следи индекс, као и незавршни симбол иза кога следи индекс незавршним симболом.

Индекси могу да се појављују само након незавршног симбола или другог индекса, тако да сваки незавршни симбол може да се сматра власником индекаса који следе иза њега, а који формирају стек.

У пракси, стекови индекаса могу да броје и памте која правила су примењена којим редоследом. На пример, индексиране граматике могу да опишу овај не-контекстно слободни језик:

[1]

следећим скупом правила извођења (f and g су индекси):

Стек g-ова који расте у средини броји колико пута () је A било замењено једним a и једним c; свако g на крају постаје завршни симбол b.

Проблем одређивања да ли дату ниску препознаје дата индексирана граматика је НП-комплетан.[1]

Линеарне индексиране граматике[уреди | уреди извор]

Џералд Газдар је дефинисао другу класу, линеарно индексираних граматика, захтевајући да највише један нетерминал у сваком кораку извођења буде одређен за примање стека; у класичној индексираној граматици сви незавршни симболи примају копије стека. Он је показао да ова нова класа граматика дефинише строго мању класу језика, благо контекстно осетљиве језике. Да ли ниску препознаје линеарна индексирана граматика се може утврдити у полиномијалном времену.[2]

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ а б Hopcroft, John; Ullman, Jeffrey (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. стр. 390-. ISBN 978-0-201-02988-8. 
  2. ^ Gazdar, Gerald (1988). „Applicability of Indexed Grammars to Natural Languages”. Ур.: U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. стр. 69-94. 

Литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]