1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why are you convinced of this? Note that grammar hierarchies are different from language hierarchies. Different sources define the types of grammars differently -- but with equivalent "power". If you puzzle together different sources, you don't necessarily get a grammar hierarchy, but that's okay. $\endgroup$ – Raphael Jan 30 '15 at 16:25
  • $\begingroup$ So... in a nutshell, Regular Grammars as defined by the Chomsky Hierarchy (which disallows certain null productions) and the definition of Regular Grammars as defined on Wikipedia (which doesn't) actually refer to two entirely different grammars with the same "power"? Is there no "standard" definition of a Regular Grammar? $\endgroup$ – peteykun Jan 30 '15 at 16:33
  • $\begingroup$ 1) I have not checked for different, but hopefully equal power, yes. 2) Probably not. -- If you want more specific answers, you have to ask a more specific questions. Cite the different definitions and asks for differences. (The definitions of context-sensitive grammars are far more fun.) Having no "standard" definition is not uncommen; everybody picks the formalism/characterisation (of anything they use, really) which makes their application and/or proof the most convenient to express resp. write down. $\endgroup$ – Raphael Jan 30 '15 at 17:19
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.