“My Lafter Machin (MLM)” recognizes the following strings : (i) a (ii) aba…
2010
“My Lafter Machin (MLM)” recognizes the following strings :
(i) a
(ii) aba
(iii) abaabaaba
(iv) abaabaabaabaabaabaabaabaaba
Using this as an information, how would you compare the following regular expressions ?
(i) (aba)3ˣ
(ii) a·(baa)3ˣ − 1·ba
(iii) ab·(aab)3ˣ − 1·a
Answer: D. (i), (ii) and (iii) are same. — ConceptTwo regular expressions are equivalent when they denote exactly the same set of strings; looking different is not the same as being different.…
- A.
(ii) and (iii) are same; (i) is different.
- B.
(ii) and (iii) are not same.
- C.
(i), (ii) and (iii) are different.
- D.
(i), (ii) and (iii) are same.
Attempted by 10 students.
Show answer & explanation
Correct answer: D
Concept
Two regular expressions are equivalent when they denote exactly the same set of strings; looking different is not the same as being different. Equivalence is therefore settled by generating the strings, and one standard rotation identity does most of that work.
Rotation identity: for any strings u and v and any n ≥ 1, (uv)n = u·(vu)n − 1·v. Moving the anchor point of a repeated block changes how an expression is written without changing the strings it produces.
Application
Write n = 3x. The three expressions then read (aba)n, a·(baa)n − 1·ba and ab·(aab)n − 1·a, so they can be compared term by term in the single quantity n.
Take u = a and v = ba in the rotation identity: (a·ba)n = a·(ba·a)n − 1·ba, that is (aba)n = a·(baa)n − 1·ba. The second written form is the first one re-anchored after a leading a.
Take u = ab and v = a in the same identity: (ab·a)n = ab·(a·ab)n − 1·a, that is (aba)n = ab·(aab)n − 1·a. The third written form is the first one re-anchored after a leading ab.
Both rewritings are identities that hold for every n ≥ 1, and 3x ≥ 1 for every x ≥ 0. So all three expressions generate one and the same language: the block aba repeated 3x times.
Cross-check
Expand every expression at the first values of x and compare the results symbol by symbol (n = 3x).
x | (i) (aba)n | (ii) a(baa)n − 1ba | (iii) ab(aab)n − 1a |
|---|---|---|---|
0 | aba | a·ba = aba | ab·a = aba |
1 | abaabaaba | a·(baa)2·ba = abaabaaba | ab·(aab)2·a = abaabaaba |
2 | abaabaabaabaabaabaabaabaaba | a·(baa)8·ba = abaabaabaabaabaabaabaabaaba | ab·(aab)8·a = abaabaabaabaabaabaabaabaaba |
The generated strings of length 3, 9 and 27 are exactly the machine strings (ii), (iii) and (iv) listed in the stem, so those samples cannot separate one expression from another.
The length-1 string a listed in the stem is produced by none of the three expressions, because every string they generate has length 3·3x. It therefore plays no part in this comparison.
Result: the three regular expressions denote one and the same language, so the comparison that treats (i), (ii) and (iii) as the same is the one that holds.