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 \to b a$ (insertion rules) and $c d \to 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]

References

↑ ^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

[accessibility=-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.

[1]

Leftist grammar

Computational properties

See also

References