Question

Automata Theory - Finding a regular expression for each of the following languages over {a,b} or {0,1}:

I've written the solution . Please show steps on how to approach the problems that I mentioned in parentheses. The ones where I put my own regular expression check and see if it's still right. Thanks

Strings with ....

odd # of a's ---> (b*ab*ab*)b*ab*

even # of 1's ---> 0*(10*10*)* ---> my answer was 0*10*10* (is this still right?)

start & end with same letter --> a(a+b)*a + b(a+b)*b + a + b ----> my answer was a(a+b)*a = b(a+b)*b (is this still right?)

no occurrence of 00 ----> 1*(011*)*(0+1)* --->(show steps to how to approach this)

exactly 1 occurrence of 00 ---> 1*(011*)*00(11*0)*1* ---> show steps to how to approach this

Answer 1

1)

odd # of a's ---> (b*ab*ab*)b*ab*

even # of 1's ---> 0*(10*10*)* [0*10*10* regex represents the strings containing only 2 1's. It does not accept strings contanining 4, 6 or 8 1's and hence, it is not correct.]

start & end with same letter --> a(a+b)*a + b(a+b)*b + a + b (= is not a valid character and does not work with regex, and moreover your regex does not accept strings "a" or "b", and hence wrong).

no occurrence of 00 ----> ((0?(1+0?)+)|0)

Explained:

Regular expressions such as 0?(1+0)* will match against any part of the string so it will match the middle part of a string such as 000011000000, it will match the 0110. To check that the whole string matches need to add the start and end of string anchors, giving ^0?(1+0)*$. This will also match an empty string. To match against a non-empty string we could use ^0?(1+0)+$ but this will not match a string with a single 0. So we need to add an alternative (using |) to match the 0, leading to the total expression ((0?(1+0?)+)|0)

exactly 1 occurrence of 00 ---> 1*(011*)*00(11*0)*1*

Explained:

1*(011*)* represents all string which does not contain any consecutive 0. Then, followed by a single occurrence of 00 and again the regex (11*0)* represents the strings not containing consecutive 0s. And, finally the string can end with any number of 1s, done using 1*.