GATE CS 2015 Set 2 Q35 — Regular Expressions and Finite Automata

To find the regular expression representing the set of strings $X_0$, we can solve the given system of linear equations using Arden's Theorem.

The given equations are:

1. $X_0 = 1 X_1$
2. $X_1 = 0 X_1 + 1 X_2$
3. $X_2 = 0 X_1 + \lambda$

Step 1: Substitute $X_2$ into the equation for $X_1$

$$\begin{aligned} X_1 &= 0 X_1 + 1 (0 X_1 + \lambda) \\ &= 0 X_1 + 10 X_1 + 1 \\ &= (0 + 10) X_1 + 1 \end{aligned}$$

Step 2: Apply Arden's Theorem

Arden's Theorem states that if we have an equation of the form $R = P R + Q$ (where $\lambda \notin P$), then it has a unique solution given by $R = P^* Q$.

Comparing $X_1 = (0 + 10) X_1 + 1$ with $R = P R + Q$:

• $P = (0 + 10)$
• $Q = 1$

Applying the theorem, we get:

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

Step 3: Substitute $X_1$ into the equation for $X_0$

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

This matches the expression given in Option C.