Theory of computation rg


which of the following regular expressions derive 0 or more instances of ‘a’ and ‘b’


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.


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