Consider the alphabet ∑ = {0, 1}, the null/empty string

Home » Theory of Computation » Theory of computation miscellaneous » Question

Consider the alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X₀, X₁, and X₂ generated by the corresponding non-terminals of a regular grammar X₀, X₁, and X₂ are related as follows. X₀ = 1 X₁
X₁ = 0 X₁ + 1 X₂
X₂ = 0 X₁ + {λ}
Which one of the following choices precisely represents the strings in X₀ ?

1. 10(0*+(10)*)1
2. 10(0*+(10*)*1
3. 1(0+10)*1
4. 10(0+10)*1+110(0+10)*1

Correct Option: C

NA