edited by
18,692 views
54 votes
54 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$
edited by

13 Answers

1 votes
1 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).
0 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
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
Answer:

Related questions

36 votes
36 votes
6 answers
1
go_editor asked Feb 13, 2015
15,522 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
88 votes
88 votes
5 answers
3
38 votes
38 votes
5 answers
4