-
Which of the following are regular sets?
1. { an b2m | n ≥ 0, m ≥ 0 }
2. { an bm | n = 2m }
3. { an bm | n ≠ m }
4. { xcy | x, y, ∈ {a,b}* }
-
- 1 and 4
- 1 and 3
- 1 only
- 4 only
- 1 and 4
Correct Option: A
Lets gather some knowledge for the regular expressions before going to True or False. The regular sets are defined in such a way that they have to follow some conventions. Conventions on regular expressions
1. Bold face is not used for regular expressions when the expression is not confusing. So, for example, (r + s) is used instead (r + s).
2. The operation * has precedence over concatenation, which further has precedence over union (+). Thus, the regular expression (a + b(c*))) is written as a + bc*.
3. The concatenation of k r's, where r is regular expression, is written as rk . Thus, for example rr = r2 . The language corresponding to rk is Lkr , where Lr is language corresponding to the regular expression r. For a recursive definition of Lkr .
4. The (r+) is used as a regular expression to represent L+r .
Based on the concept, only 1 and 4 are found to be regular since in 1, L can be written as a* (bb)* and 4, (a + b) * c(a + b)* can be written for the 4.
