[Solved]: Constructing right-linear grammar

Problem Detail: 

Is the grammar

$\qquad S \to 1A0A \mid 0A \mid \varepsilon$

a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals.

I know $0A$ is right-linear but what about $1A0A$?

Trying to construct a right-linear grammar for language $10(0+1)^*10$.

Asked By : Iancovici

Answered By : Luke Mathieson

I'll give some hints as plain text, do try to have a go at solving the questions with this help before revealing the spoilers.

The first part you should be able to answer very easily - check the definition of a linear grammar, how many non-terminals can be on the right-hand side of the production?

At most one, so this isn't a linear grammar, let alone right-linear.

For the second part, perhaps one way to approach it is to first build an NFA that recognises the same language that the grammar generates, then you can use the transitions of the NFA to generate the transitions of the grammar.

$S\rightarrow 1A$
$A\rightarrow 0B$
$B\rightarrow 1B \;|\; 0B \;|\; C$
$C \rightarrow 1D$
$D\rightarrow 0$
This grammar is certainly not the only one, but should look something like an NFA for the same language - the non-terminals are states, and $D$ is the accept state.

Best Answer from StackOverflow

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