Theory of computation rg


#1

which of the following regular expressions derive 0 or more instances of ‘a’ and ‘b’
1)a|b
2)(ab)*
3)(a|b)*


#2

The opt 2 and 3 both are correct since using kleen closure we can generate epsilon or more number of string since there is no mention about number of instances of ‘a’ or ‘b’ so I think both are appropriate.


#3

2 and 3.
(ab) * generates {€,ab, abab… }
(a|b)* generates {€,a, aa,…, b, bb,… }