what is regular expression not generated over {a,b}?

Question

Hello all,

I am really stuck with these 2 question for over 2 days now. trying to figure out what the question means.... my tutor is out of town too....

write a regular expression for the only strings that are not generated over {a,b} by the expression: (a+b)*a(a+b)*. explain your reasoning.

and i tried the second question, do you think is there any better answer than this one?

what is regular expression of set of string that contain an odd number of a's or exactly two b's................(a((a|b)(a|b))*|bb).... coz i know to represent any odd length of a's, the RE is a((a|b)(a|b))*

Answer 1

Here's a start for the first question. First consider the strings that this regular expression generates:

(a+b)*a(a+b)*

• It must begin with a AND
• Every b must have at least one an a immediately before it AND
• There must either be an aab or else the string must end in a.

The inverse of this is:

• It must not begin with a OR
• There is at least one b not after an a OR
• The string consists only of repetitions of ab.

For the second question you should check that you have understood the question correctly. Your interpretation seems to be:

What is the regular expression for the set of strings that contain either (an odd number of a's and any number of b's) or (exactly two b's and no a's).

But another interpretation is this:

What is the regular expression for the set of strings that contain either (an odd number of a's and any number of b's) or (exactly two b's and any number of a's).

Answer 2

To match two a's you would use something like aa right? Now we know that the + is a quantifier for 1 or more and the * is a quantifier for 0 or more. So if we want to repeat that entire pattern, we can put it in a group and repeat the entire pattern like so: (aa)+.

That would match:

• aa
• aaaa

But not:

• a (because aa requires at least 2 items)`
• aaa (because aa will match the first two, but you'll have an extra a)

And if we want to make that odd an even, we can simply add one extra a outside of the group like so: a(aa)+. However, since we wanted an odd amount without a specific minimum we shouldn't use + since that will require atleast 3 a's.

So the entire answer would be: (bb|a(aa)*)

Answer 3

It sounds like the first question is asking you to write a regular expression for the set of strings that do not match the provided regular expression.

For instance, suppose the question was asking for a regular expression for the set of strings not matched by aa+ over {a}. Well, here are a few strings that do match:

• 'aa'
• 'aaaa'
• 'aaaaa'

What are some strings that do not match? Here are the only two:

• ''
• 'a'

A regex for the latter set is a?.

Regarding the second question, I would suggest drumming up some positive and negative test cases. Run some strings like this through your regex and see what happens:

• 'a' (should pass)
• 'aaa' (should pass)
• 'bb' (should pass)
• '' (should fail)
• 'aa' (should fail)
• 'aba' (should fail)

Good luck!

Answer 4

The expression (a+b)*a(a+b)* just means: there has to be an a inside the string. The only strings that cant be generated by this expression are those: b*

Answer 5

This expression means that RE must contain Atleast 1 'A' in the expression.

this expression doest not accept

'b' 'b'* or Empty set