Regular Expressions for Strings with Specific Character Patterns

kliker
Messages
102
Reaction score
0

Homework Statement


Σ = {a,b}
find regular expression for

1)all strings that haven't got more than 3 a's
2)all strings that have a number of a's that is divisible by 3
3)all strings that have the substring aaa only one time

The Attempt at a Solution


1) b*Ub*ab*Ub*ab*ab*Ub*ab*ab*ab*

2) (b*Ub*ab*ab*ab*)*

3) b*(aUaaUe)b*aaab*(aUaaUe)b*

can you please tell me if I am correct? this is not homework actually but i didnt know where to post it, I am just preparing myself for the upcoming exams and need to know if i have these correct

thanks in advance
 
Physics news on Phys.org
i have one more

Σ = {a,b,c}

i want a regular expression for all strings that contain at least 1 a, 1 b and 1 c

ok my solution is this

(a(bUc)*Ub(aUc)*Uc(aUb)*)*

but the book has this solution

(aUbUc)*c(aUbUc)*b(aUbUc)*a(aUbUc)*

which is right but is my solution wrong?
 
There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...
Back
Top