Leftist grammar
From HandWiki
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 [math]\displaystyle{ a \to ba }[/math] (insertion rules) and [math]\displaystyle{ cd \to d }[/math] (deletion rules). Here, [math]\displaystyle{ a,b,c }[/math] and [math]\displaystyle{ d }[/math] 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
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.
 |  |
