World's most popular travel blog for travel bloggers.

[Solved]: Relaxation of the null production restriction in Regular and Context Free Grammars

, , No Comments
Problem Detail: 

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of some production.

However, in most definitions of regular and context-free grammars (such as those on Wikipedia), this restriction is nowhere to be seen (as an exception, the restriction is mentioned in the article on the Chomsky hierarchy for Type-3 languages).

  1. Is this relaxation intentional in that both variants (with and without the restriction) have the same expressive power, or is this just a "sloppy" definition?

  2. Even if they do have the same expressive power, wouldn't that ensure that Context Free Grammars are not a subset of Context Sensitive Grammars, thus violating Chomsky's Hierarchy?

Asked By : peteykun

Answered By : Hendrik Jan

True.

For CFG we can remove in fact all epsilon rules and obtain the same family of languages, except for the empty word. That can be added by adding the $S\to\varepsilon$ production. It is a so-called normal form.

Like Raphael says: it all depends on what you want to express in the formalism, and what makes proofs convenient.

The definition on type-3 grammars is a matter of taste. I would prefer $A\to\varepsilon$, $A\to aB$ as these two types of productions correspond to final states and transitions in finite state automata.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37771

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback