How to get words that belong to the language of this regular expression and four which do not, ((a|baa) ∗ (b|ab))∗ .

Question

In the alphabet {a, b} for both automata and regular expressions, what would be four words that belong to the language of this regular expression and four which do not, regular expression = ((a|baa)∗(b|ab))∗

Im not too sure on this, but would 'aaa' be one that does belong and 'bb' be one that doesn't belong. And what are some other ones

Answer 1

Trying to rephrase the expression... the expression (a|baa)*(b|ab) can be described as the following: (Step 1) Append any number (including zero) of either a or baa to the string. (Step 2) Append a b or an ab to the current word (not optional). Now, taking that expression, wrapping it in parentheses, and following it by a star means that we perform that whole process any number of times, possibly including zero. So, 'aaa' would not have been possible since thanks to the Step2 as written above, there obviously must have been a b included somehow.

I leave finding more examples to you.

"Okay, would these be correct: Belong to the language: aba baab baaabab ababab Do not belong to the language: aaa bbb abaaa bbaaba?"

Do step 1 zero times, then do step 2 by putting a b. Repeat this again, doing step 1 zero times again and doing step 2 by putting a b, and then once more. This gives the string bbb in our language

$~$

Since every time we do (or don't do) step 1 we must follow it by doing step 2... and since every option for step 2 puts a b at the end, and step 2 will always be the last thing done if anything was done at all (recall we could just do the whole process zero times and have the empty-string)... it follows that every word will end with a b and so aba does not belong to our language.

As an extra problem, try to prove to yourself whether your language is actually equivalent to (((a|b)*b)|ϵ), i.e. the empty string or any string made of a's and/or b's so long as it ends with a b.