Jump to content

Talk:Indexed language

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Complexity characterization?

[edit]

Is there one? Seems like more than PTIME. JMP EAX (talk) 10:32, 17 August 2014 (UTC)[reply]

Example for context-sensitive, but not indexed language

[edit]

Could somebody please provide an example for a language that is context-sensitive, but not indexed? The article says that { (abn)n | n≥0 } isn't indexed; I guess that it is context-sensitive, but I'm unable to establish it (writing context-sensitive grammars is an error-prone task, cf. Talk:Context-sensitive grammar). - Jochen Burghardt (talk) 13:49, 25 February 2015 (UTC)[reply]