Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
Right linear grammar: One nonterminal at the end of the right hand side – vonbrand Feb 25 '13 at 4:35
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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