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

- $10(0^*+(10)^*)1$
- $10(0^*+(10)^*)^*1$
- $1(0+10)^*1$
- $10(0+10)^*1 +110(0+10)^*1$

+89 votes

Best answer

+1

@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?

+2

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

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

0

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

0

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.

0

@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?

+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:

$R=PR+Q$

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

0

I tried the substitution in another way,

X_{1}= 0X_{1} + 1 X_{2} (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?

0

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?

+3

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

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

0

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

0

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

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

+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

WE CAN WRITE THE EQUATION LIKE:

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

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!

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.

0

final state which is X2 because it accepts epislon symbol.

how presence of epsilon is making x2 as final state?

52,345 questions

60,503 answers

201,899 comments

95,335 users