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.

Computational properties

The membership problem for leftist grammars is decidable.

See also

• Unrestricted grammar
• String rewriting