- Source: 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
→
b
a
{\displaystyle a\to ba}
(insertion rules) and
c
d
→
d
{\displaystyle cd\to d}
(deletion rules). Here,
a
,
b
,
c
{\displaystyle a,b,c}
and
d
{\displaystyle 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