0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Right linear grammar: One nonterminal at the end of the right hand side $\endgroup$
    – vonbrand
    Commented Feb 25, 2013 at 4:35

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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