I have some old exercises of regular expressions without solutions and i would like to check if i understand the theory correctly. In the methodology section i show my answers/steps so far.
After the arrow ( -> ) is my answer to every problem.
1.Give the smallest possible string that languages i) and ii) don't accept
i)b*(ab)*a* -> aab
ii)b*(a+ba)*b* -> abba
2.Given the regular expressions r=a*+b* and s=ab* + ba* + b*a + (a*b)* . Find the smallest possible string that can be expressed in:
i)r but not in s -> {empty-ε}
ii)s but not in r -> aba
iii)both r and s -> {x} there is no answer
iv)cannot be expressed in any of them -> aaba
3.Give the expression that accepts strings that:
i)have 3*x a's character -> b*(b*ab*ab*a)*b*
ii)start or end with ab/ba -> (ab+ba)(a+b)* +(b+a)*(ab+ba)
iii)dont have aaa in them -> (b+ab+aab)*(a+aa+ε)
iv)every b is followed by aaa -> a*(baaa)*a*
METHODOLOGY
i) After two a the regex can't go back and accept a b.
ii) After abb cannot accept anything other than b
2)
i)The empty string because s accepts at least the characters aba
ii)aba cannot be accepted by r since it can't have a after b*
iii) No answer since the smallest possible strings aren't the same.
iv) aaba in r you can't have aab_ with _ = other than b and s can't accept aaba.
3)
i)There are always 3*x a's in the string with any number of b's.
ii)Any string between start/end is arbitary.
iii)Every possible string that does not have aaa (so states end with b).
iv)No criterion for a's but every b should be followed by aaa.
Best Answer
There are a few errors.
2(i) isn’t right: the $(a^*b)^*$ term in $s$ accepts the empty string. However, $s$ does not accept $aa$, which is accepted by $r$.
2(iii) isn’t right: the empty string can be expressed in both.
Another possibility for 2(iv) is $bbaa$.
3(i) is correct but can be simplified to $(b^*ab^*ab^*a)^*b^*$, and $(b^*ab^*ab^*ab^*)^*$ also works.
3(iv) isn’t right: it doesn’t recognize $baaaabaaa$, for instance. $a^*(baaaa^*)^*$ will work.