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 ba$ (insertion rules) and $cd\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

^ ^a ^b Motwani, Rajeev; Panigrahy, Rina; Saraswat, Vijay; Ventkatasubramanian, Suresh (2000). "On the decidability of accessibility problems (extended abstract)". 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.

[accessibility=-1] Motwani, Rajeev; Panigrahy, Rina; Saraswat, Vijay; Ventkatasubramanian, Suresh (2000). "On the decidability of accessibility problems (extended abstract)". 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]

Computational properties

See also

References