Consider the alphabet β = {0, 1}, the null/empty string π and the sets ofβ¦
2015
Consider the alphabet β = {0, 1}, the null/empty string π and the sets of strings X0, X1, and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1, and X2 are related as follows.
X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {π}
Which one of the following choices precisely represents the strings in X0?
- A.
10(0* + (10)*)1
- B.
10(0* + (10)*)*1
- C.
1(0 + 10)*1
- D.
10(0 + 10)*1 + 110(0 + 10)*1
Attempted by 83 students.
Show answer & explanation
Correct answer: C
Key steps: solve the grammar equations to a regular expression.
From X1 = 0 X1 + 1 X2 we get X1 = 0* 1 X2 (zero or more 0s, then a 1, then whatever X2 generates).
From X2 = 0 X1 + {Ξ»} substitute X1 = 0*1 X2 to obtain X2 = Ξ» + (0 0* 1) X2, so X2 = (0 0* 1)*. Each factor 0 0* 1 is "one or more 0s followed by 1".
Therefore X0 = 1 X1 = 1 0* 1 (0 0* 1)*.
Interpretation and simplification: strings in X0 must start and end with 1. Between these boundary 1s, every internal 1 is followed by at least one 0 (because of the block "one-or-more-0s then 1"). Thus the middle part can be seen as a sequence of tokens that are either a single 0 or the pair 10, i.e. (0 + 10)*.
So X0 = 1(0 + 10)*1, which matches the given correct expression.
A video solution is available for this question β log in and enroll to watch it.