The Gateway to Computer Science Excellence
+36 votes

Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows.

  • $X_0 = 1 X_1$
  • $X_1 = 0 X_1 + 1 X_2$
  • $X_2 = 0 X_1 + \{ \lambda \}$

Which one of the following choices precisely represents the strings in $X_0$?

  1. $10(0^*+(10)^*)1$
  2. $10(0^*+(10)^*)^*1$
  3. $1(0+10)^*1$
  4. $10(0+10)^*1 +110(0+10)^*1$
in Theory of Computation by
edited by | 5.6k views
answer bellow given by @anoop +umang shows that X0 is start state(in dfa) or start symbol (in grammar ) how i know that X0 is start state is quetion gives such informations??
See the selected answer FA. A,B,D don't accept 11 accepted by the FA.

9 Answers

+89 votes
Best answer


Convert the given transitions to a state diagram 

From the given diagram we can write 

$X_0 = 1(0+10)^*1$ option C

selected by
Thanks Umang for simple explanation.

 Brij Mohan Gupta   will u pls explain how 1 comes at last position with this diagram?

Can u tell me how to find which is the final state?
How do we decide which non terminal is the starting state?
but how you  did it?

what is language at X1  and at X2?
This should be selected as best answer.
it should accept έ null string also it is given in the question

@Arjun sir, What are these equations actually?

$X_0 = 1 X_1$

$X_1 = 0 X_1 + 1 X_2$

$X_2 = 0 X_1 + \{ \lambda \}$

Can we treat them as RIGHT LINEAR GRAMMAR? If yes, then this is the FA for it.Now the question asks for the language of $X_0$ which is NULL.


The correct language of $X_0$ can be obtained by REVERSAL of this FA. i.e. by reversing arrows and swapping initial and final states.

I know that when a LEFT LINEAR GRAMMAR is changed to RIGHT LINEAR then language is reversed. But why here?

Here we are asked to find the set of strings generated by the non terminal X$_{0}$.

We can compare the given equations to a right linear grammar (as the relationship of equations are similar to the form of a RLG) with X$_{0}$ as the initial state because we are asked to find the strings generated by X$_{0}$, and X$_{2}$ as final state, because X$_{2}$ is the only state with ∈ production.


PS : The set of Strings generated by a grammar means that, starting symbol of that grammar can generate that set of strings. Like wise here we start derivation from X$_{0}$  inorder to find the set of strings generated by X$_{0}$.

So we draw the corresponding NFA (for convenience ) with start state X$_{0}$ and final state X$_{2}$ to find the representation (regular expression).


Also please note that, if we are asked to find precise representation of the strings in X$_{1}$, we will set initial state as X$_{1}$.

@Amal @Praveen Saini sir, When I treat three equations given in question according to Arden's theorem , I get X2 as initial state (due to presence of λ in its equation). Can you please explain why we are not drawing DFA according to Arden's Theorem here. 


@Gaganjot _Kaur

are you clear with my last explanation?

There is no actual need to find any DFA here. Here we are asked to find the set of strings generated by the non terminal X0. And drawing DFA is a technique for finding it.


@Amal , Actually I drew DFA according to Arden's equation and got X0 as final state. Are we considering X0 to be the start state only because we need to find "strings generated by X0" , or is there any other explanation?


yeah..we considering X0 to be the start state only because we need to find "strings generated by X0". Look at the answer, he just converted the relations into state diagram with initial state X0.(that is the technique he used here)

+56 votes

Here we have little different version of Arden's Theorem.

If we have $R= PR + Q$   then it has a solution  $R = P^*Q$

Proof :

$R= PR+ Q$

$\quad= P(PR+Q)+Q$    (by putting $R= PR+Q$)

$\quad= PPR+PQ+Q$

$\quad=PP(PR+Q)+PQ+Q$   (by putting $R= PR+Q$)

$\quad= PPPR+PPQ+PQ+Q$

and so on, we get $R = \{\ldots+PPPPQ+PPPQ+PPQ+PQ+Q\}$

$\qquad\qquad\qquad= \{\ldots+PPPP+PPP+PP+P+ \lambda \}Q  = P^*Q$

or another way:


$\quad= P(P^*Q) + Q$      (by putting $R = P^*Q$)

$\quad=(PP^* + \lambda )Q = P^*Q$

So, equation is proved.

Now for the Above Question:

$X_1= 0X_1 + 1 \ X_2$   (Equation 2)

$\quad= 0X_1 +1(0X_1 + \lambda)$     ( Put the value of $X_2$ from Equation 3 )

$\quad=0X_1 +10 \ X_1+ 1 =  (0+10)X_1 +1$

$X_1= (0+10)^*1$   (Apply if $R = PR + Q$ then $R = P^*Q$)

$X_0 = 1 \ X_1$     (Equation 1)

$X_0 = 1(0+10)^*1$   (Put the value of $X_1$ we calculated).

So, $1(0+10)^*1$.

Option C is correct.

edited by
Can you please post any reference of this version of Arden's theorem?

I tried the substitution in another way,

X1= 0X1 + 1 X2   (Equation 2)

consider 0 = A, 1X2 = B,

so, by the theorem,

X1 = 0*1X2 --- (4)

Now , substitute Eq(4) in Eq 3,

X2 = 0 0*1X2 + lambda

by considering 00*1 as A and lambda as B, we get,

X2 = (00*1)*lambda ~= (00*1)*

Even though I get your derivation, I want to know why this way of substituion failed?

we have to find X0?
we can substitute X2's value in eq 4 to get X1 after this we can substitute X1 in X0's equation. But by doing this way, I did not arrive at that correct answer even though I think that, method I followed is correct. Have I done any mistake in substitution?
X2= (00*1)*

X1 = 0*1(00*1)*

X0 = 1X1 = 10*1(00*1)* = 1(0*10)*0*1  or 10*(100*)1 is equivalent to 1(0+10)*1

or 10*(100*)1 is equivalent to 1(0+10)*1

It should be $10^*(100^*)^*1$


@Praveen Saini

R = Q + RP is also I can write.

then solution is R = QP* != P*Q


@MRINMOY_HALDER you are right. What is the doubt? 

If I calculate according to R = Q + RP, then I'll get different answer.

@MRINMOY_HALDER are you converting the question to some other equivalent form where R = Q + RP can be applied on it. 

please check my understanding,

arden's lema can be of two form - R = Q + RP or PR, right??
here according to qsn, PR will be applicable???

R = Q+RP, then QP*
R=Q+PR, then P*Q
"R = Q+RP, then QP*"

This is Arden's Theorem , but not applicable here.

"R=Q+PR, then P*Q"

This is a variation of above, works well for this problem
This variant of Arden's theorem is taught by Kamala ma'am in her TOC NPTEL lectures.
Can you tell me in which lecture she teaches Arden method or share the link for the same?

Couldn't find ardens theorem in the reference book I use.

Would be of great help.

+47 votes
option c is correct because look at the smallest string generated by the grammar is 11 which is not accepted by any option.
+3 votes


X0 = 1X1

X1 = 0X1 / 1X2

X2 = 0X1 / λ


Now we can convert it into the following production :

X0 = 1X1

X1 = 0X1 / 10X1 / 1

So from the above production we can write like : 1 ( 0 + 10)* 1. 

So option (C) is the correct ans.

+3 votes

firstly i converted regular grammar(right linear grammar) to finite automata and then finite automata to regular expression.

0 votes
If we observe a liitle bit then we can easily see that minimum string is 11, which is generated by only option C!
how did you check ?



now substitute 1X2 in place of X1

now substitute empty string in place of X2 ( which is generated by X2,see in the production of X2)

minimum string is 11 ,which is generated by only option C!

0 votes

Till now no question has been asked directly on Arden's theorem. 

This question can be solved using both Arden's theorem OR by making DFA using relation given among Xo, X1, X2. Actually, a DFA can also be represented in terms of outgoing arrow(right linear grammar) or incoming arrow(Left linear grammar). so first convert outgoing arrow representation into DFA, which will look like this....

The question is asking about "by which set of strings(Regular expression) given in options we can accept it through Xo".

It means consider Xo initial state and try to reach the final state which is X2 because it accepts epislon symbol.

Now try to generate regular expression by state elimination method and you get the option C.

same can be done for X1 and X2 also. I have tried these using Arden's method and state elimination both. and both give the same answer.

edited by

final state which is X2 because it accepts epislon symbol.

how presence of epsilon is making x2 as final state?  


When we write a regular grammar for a finite automaton, we denote final state as an epsilon production for Right linear Grammar.   I couldn't find any valid reference but this might help 

Thanks bro, that helped.
0 votes
The smallest possible string by given grammar is "11".
X0 = 1X1
   = 11X2  [Replacing X1 with 1X2]
   = 11    [Replacing X2 with λ]

The string "11" is only possible with option (C).

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,503 answers
95,335 users