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 [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]

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.

Leftist Grammar

Computational properties

See also

References