One-sided forbidding grammars and selective substitution grammars

Abstract

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a non-terminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form, while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars. As its main result, this paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, this paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.

Keywords:

• formal language theory
• regulated rewriting
• one-sided forbidding grammars
• selective substitution grammars
• generative power

2010 AMS Subject Classifications :

• 68Q42
• 68Q45

Acknowledgements

This work was supported by the following grants: BUT FIT FIT-S-11-2, MŠMT MEB041003, EU CZ 1.05/1.1.00/02.0070, and CEZ MŠMT MSM0021630528.