Showing only posts tagged formal grammar. Show all posts.

Automata theory: formal languages and formal grammars

Chomsky hierarchy Grammars Languages Abstract machines
Type-0 Unrestricted Recursively enumerable Turing machine
(no common name) Decidable Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
Positive range concatenation Positive range concatenation* PTIME Turing Machine
Indexed Indexed* Nested stack
Thread automaton
Linear context-free rewriting systems Linear context-free rewriting language restricted Tree stack automaton
Tree-adjoining Tree-adjoining …