GATE CS 1998 Q1.9 — Regular Expressions and Finite Automata

To determine the relationship between the regular sets $A = (01 + 1)^*$ and $B = ((01)^*1^*)^*$, we can show containment in both directions.

Step 1: Show $A \subseteq B$

Let us look at the generators of $A$, which are $01$ and $1$:

• For the subexpression $(01)^*1^*$ inside $B$, choosing the first term once and the second term zero times gives $01$. Thus, $01 \in (01)^*1^*$.
• Choosing the first term zero times and the second term once gives $1$. Thus, $1 \in (01)^*1^*$.

Since both generators of $A$ belong to the set $(01)^*1^*$, any string formed by concatenating these generators (which constitutes the set $A$) must also belong to $((01)^*1^*)^*$. Therefore, $A \subseteq B$.

Step 2: Show $B \subseteq A$

Since $A = (01 + 1)^*$, we know that $A$ is closed under concatenation and Kleene star.

• Clearly, $01 \in A$ and $1 \in A$.
• Since $A$ is closed under Kleene star, $(01)^* \subseteq A$ and $1^* \subseteq A$.
• Since $A$ is closed under concatenation, $(01)^*1^* \subseteq A$.
• Applying the Kleene star again, we get $((01)^*1^*)^* \subseteq A^*$. Since $A^* = A$, this simplifies to $B \subseteq A$.

Conclusion

Since $A \subseteq B$ and $B \subseteq A$, we have $A = B$.