The Gateway to Computer Science Excellence
+31 votes
4.5k views

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 Veteran (105k points)
edited by | 4.5k views
+3
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??

8 Answers

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

by Boss (16.4k points)
selected by
+2
Thanks Umang for simple explanation.
+2

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

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

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

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

+1
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}$.
+50 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.

by Veteran (56.8k points)
edited by
0
Can you please post any reference of this version of Arden's theorem?
0

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?

0
we have to find X0?
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
+1

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

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

0

@Praveen Saini

R = Q + RP is also I can write.

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

0

@MRINMOY_HALDER you are right. What is the doubt? 

0
If I calculate according to R = Q + RP, then I'll get different answer.
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
+1
"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
+41 votes
option c is correct because look at the smallest string generated by the grammar is 11 which is not accepted by any option.
by Active (5k points)
+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.

by (241 points)
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!
by Active (3.7k points)
0
how did you check ?
+1

@

X0=1X1

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

by Active (3.5k points)
edited by
0

final state which is X2 because it accepts epislon symbol.

how presence of epsilon is making x2 as final state?  

+1

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 

0
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).
by (405 points)
0 votes

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

by (321 points)

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
50,647 questions
56,492 answers
195,473 comments
100,774 users