Leftist grammar

In formal language theory, a leftist grammar is a formal grammar on which certain restrictions are made on the left and right sides of the grammar's productions. Only two types of productions are allowed, namely those of the form a->ba (insertion rules) and cd->d (deletion rules). Here, a,b,c and d are terminal symbols. This type of grammar was motivated by accessibility problems in the field computer security.[1]

## Computational properties

The membership problem for leftist grammars is decidable.[1]

## See also

* Unrestricted grammar
* String rewriting

* v
* t
* e

Automata theory: formal languages and formal grammars

| Chomsky hierarchy| Grammars| Languages| Abstract machines

|
|
|

* Type-0
* —
* Type-1
* —
* —
* —
* —
* —
* Type-2
* —
* —
* Type-3
* —
* —

* Unrestricted
* (no common name)
* Context-sensitive
* Positive range concatenation
* Indexed
* —
* Linear context-free rewriting systems
* Tree-adjoining
* Context-free
* Deterministic context-free
* Visibly pushdown
* Regular
* —
* Non-recursive

* Recursively enumerable
* Decidable
* Context-sensitive
* Positive range concatenation*
* Indexed*
* —
* Linear context-free rewriting language
* Tree-adjoining
* Context-free
* Deterministic context-free
* Visibly pushdown
* Regular
* Star-free
* Finite

* Turing machine
* Decider
* Linear-bounded
* PTIME Turing Machine
* Nested stack
* Thread automaton
* restricted Tree stack automaton
* Embedded pushdown
* Nondeterministic pushdown
* Deterministic pushdown
* Visibly pushdown
* Finite
* Counter-free (with aperiodic finite monoid)
* Acyclic finite

Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

## References

1. ↑ 1.0 1.1 Motwani, Rajeev; Panigrahy, Rina; Saraswat, Vijay; Ventkatasubramanian, Suresh (2000). "Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00". Proceedings of the thirty-second annual ACM symposium on Theory of computing (STOC '00). pp. 306–315. doi:10.1145/335305.335341. ISBN 1581131844.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Leftist grammar. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Leftist_grammar&oldid=308680"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template