Working on my homework for a class and I came to this question: For each of the

Question

Working on my homework for a class and I came to this question:

For each of the following regular expressions, give minimal length strings that are not in the language defined by the expression.

A) (bb)*(aa)b
b) a*(bab)*?b?ab

For the first one, the empty string is included and has a length of zero, however the string a cannot be in the language since it would result in an odd amount of a's.

I'm confused about the second part though. Obviously the first part means that the string must have some number of a's followed by bab, but i dont really understand what the union operation means. Any help would be greatly appreciated.

Explanation / Answer

The first regular expression is matching any word that starts with an even number of 'b's (zero included) followed by an even number of 'a's (zero is ok), then followed by some 'b's.

This means that the empty string is in the language, as well as the string "b". However, the string "a" is not in the language.

Thus all the minimal length string that are not in the language is "a".

The second regex matches on "", "a" and "aa" (by a*(bab)*) and also on "b" and "ab". However it doesn't match on "ba" and "bb".

Thus the minimal strings are of length 2: "bb" and "ba".

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.