edited by
18,665 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

Best answer
121 votes
121 votes

Convert the given transitions to a state diagram 

From the given diagram we can write 

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

Correct Option: C

edited by
74 votes
74 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.

edited by
53 votes
53 votes
option c is correct because look at the smallest string generated by the grammar is 11 which is not accepted by any option.
7 votes
7 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.

Answer:

Related questions

36 votes
36 votes
6 answers
1
go_editor asked Feb 13, 2015
15,509 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