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 (insertion rules) and (deletion rules). Here, and are terminal symbols. This type of grammar was motivated by accessibility problems in the field computer security.[1]

Computational properties

edit

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

See also

edit

References

edit
  1. ^ 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.