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

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

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

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

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

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

 L = \{a^n b^n c^n | n \geq 1 \} [1]

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

S\to aAfc

A\to aAgc ~|~ B

Bf\to b

Bg\to bB

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

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

Линеарне индексиране граматике[уреди]

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

Види још[уреди]

Референце[уреди]

  1. ^ а б Hopcroft, John; Jeffrey Ullman (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“. In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. стр. 69-94. 

Литература[уреди]

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

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

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.