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

:<math> L = \{a^n b^n c^n | n \geq 1 \} </math><ref name=Hopcroft_and_Ullman> {{Cite book |last=Hopcroft | first = John | last2 = Ullman | first2 = Jeffrey | title = Introduction to automata theory, languages, and computation |url=https://archive.org/details/introductiontoau00hopc_091 |year=1979| publisher = Addison-Wesley |isbn=978-0-201-02988-8|pages=[https://archive.org/details/introductiontoau00hopc_091/page/n397 390]-}}</ref>

Џералд Газдар је дефинисао другу класу, '''линеарно индексираних граматика''', захтевајући да највише један нетерминал у сваком кораку извођења буде одређен за примање стека; у класичној индексираној граматици сви незавршни симболи примају копије стека. Он је показао да ова нова класа граматика дефинише строго мању класу језика, [[благо контекстно осетљиви језик|благо контекстно осетљиве језике]]. Да ли ниску препознаје линеарна индексирана граматика се може утврдити у [[полиномијално време|полиномијалном времену]].<ref name="gazdar1998">{{Cite book | chapter=Applicability of Indexed Grammars to Natural Languages | year=1988 | last=Gazdar | first=Gerald | title=Natural Language Parsing and Linguistic Theories | url=https://archive.org/details/naturallanguagep00reyl | editor=U. Reyle and C. Rohrer | pages=[https://archive.org/details/naturallanguagep00reyl/page/69 69]-94}}</ref>

* {{Cite book | ref= harv|chapter=Applicability of Indexed Grammars to Natural Languages | year=1988 | last=Gazdar | first=Gerald | title=Natural Language Parsing and Linguistic Theories | url= https://archive.org/details/naturallanguagep00reyl| editor=U. Reyle and C. Rohrer | pages=[https://archive.org/details/naturallanguagep00reyl/page/69 69]-94}}