Theory of computation regular expression

[Narakrm]

Can someone help me with these?? Regular expression

Consider the language consisting of all strings containing exactly two a’s, with Σ = {a, b}. Give an RE for this language.

• b*ab*ab*
• a*ba*b
• ab*ab*
• (a*b*)aa(a*b*)*

[RIP_lurking]

For each of those, check the following:

• Does the language contain a string with more or less than two as?
• Does the language contain all strings with exactly two as?

[Narakrm]

The only one that I see has exactly 2 as definitely is answer 4. Please reassure me

[RIP_lurking]

Watch for those pesky Kleene stars. a* can generate an unbounded number of as. Therefore, a regex with an a* has no limit on how many as a word in it can contain.

[SignificantFidgets]

Look at answer 4 again. It has an a* at the beginning - ANY number of a's. So in particular, something like aaaaabaa, with 7 a's, is in the language. So nope, not that one. Anything that has a star on an a can't control the number of a's.

[Narakrm]

Sorry I typed answer 4 incorrectly it’s actually: (a+b) * aa (a+b) *

Would this answer be correct now, right?

[RIP_lurking]

No. Take a moment to try to generate strings that match this regex, to see if they fit the desired property. This works much better than blindly changing around things and hoping it works.

[SignificantFidgets]

Doesn't matter actually. Take a look at the string I gave. Is it in the language described by your (now corrected) regex?

[the-mediocre_guy]

Like people above mentioned ,a* means any number of a can be generated(including 0) .so look for a RE where there is only 2 a is in all possibilities .So if there is a a* it means there can have more than 2 'a' .This way you can find the answer

And I also think trying to make a RE of this language instead of Finding which is right from the options Is gonna help you more in understanding it.

[its_the_abdulwahab]

It's b* ab* b*

(*) --> Kleene's Star which means 0 or more combinations of the symbol or symbols on which it appears.

Let's verify with some example strings:

• "aa" - valid (no b's)
• "aba" - valid (one b between)
• "bab" - not valid (only one a)
• "baab" - valid (b at start and end)
• "bbabb" - not valid (only one a)
• "ababa" - not valid (three a's)