0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ... and $B\to a$ is like going to a final state (without outgoing transition) while reading $a$. $\endgroup$ – babou May 17 '15 at 14:41

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.