If you want to make money online : Register now

Identity productions in regular grammar

, , No Comments
Problem Detail: 

If a grammar is of the following form (i.e. all its productions are), is its language regular?

  1. $B → a$ - where $B$ is a non-terminal in $N$ and a is a terminal in $Σ$
  2. $B → aC$ - where $B$ and $C$ are in $N$ and $a$ is in $Σ$
  3. $B → ε$ - where $B$ is in $N$ and $ε$ denotes the empty string, i.e. the string of length 0.
  4. $B → A$ - where $A$ and $B$ are non-terminals in $N$

(1. - 3. quoted from wikipedia)

I only added the 4th rule and I assume that the language is regular. However, I cannot find any reference that supports this intuition.

Asked By : choeger
Answered By : Hendrik Jan

Yes the language is regular.

Productions 2 and 3 are like transitions in a finite state automaton: $B \to aC$ is like moving from state $B$ to state $C$ while reading $a$; $B\to \varepsilon$ indicates that $B$ is like a final state where we can stop the computation (i.e., end the dirivation in grammar terminology).

The production $A\to B$ is like an $\varepsilon$-transition in finite state automata. This may be practical, but does not change the language generating capabilities of the grammars.

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback