The given regular expression is $(ab \cup ba)(aa \cup bb)^*ab$.

Let's break down the structure of any word, let's call it $w$, generated by this expression:

1. Prefix: The word must start with either ab or ba. This part has a fixed length of 2.
2. Middle: This part is described by $(aa \cup bb)^*$. The Kleene star ($*$) means "zero or more repetitions". This means the middle can be the empty string ($\epsilon$), or aa, or bb, or aaaa, or aabb, etc. Crucially, any string in this middle part will have an even length (0, 2, 4, 6, ...).
3. Suffix: The word must end with ab. This part has a fixed length of 2.

The total length of any word is $2$ (prefix) $+ \text{length of middle part} + 2$ (suffix). So, the total length will be $4 + (\text{an even number})$. This means the possible lengths of the words are 4, 6, 8, 10, and so on.

We are asked for all words of length less than or equal to 8. So we only need to consider words of length 4, 6, and 8.

---

1. Words of Length 4: For the total length to be 4, the middle part must have a length of 0. This means we use zero repetitions from $(aa \cup bb)^*$, which gives us the empty string, $\epsilon$.

• Prefix ab + Middle ε + Suffix ab $\rightarrow$ abab
• Prefix ba + Middle ε + Suffix ab $\rightarrow$ baab

2. Words of Length 6: For the total length to be 6, the middle part must have a length of 2. This means we use one repetition from $(aa \cup bb)^*$. The middle part can be aa or bb.

• Prefix ab + Middle aa + Suffix ab $\rightarrow$ abaaab
• Prefix ab + Middle bb + Suffix ab $\rightarrow$ abbbab
• Prefix ba + Middle aa + Suffix ab $\rightarrow$ baaaab
• Prefix ba + Middle bb + Suffix ab $\rightarrow$ babbab

3. Words of Length 8: For the total length to be 8, the middle part must have a length of 4. This means we use two repetitions from $(aa \cup bb)^*$. The possible middle parts are:

• aa followed by aa $\rightarrow$ aaaa
• aa followed by bb $\rightarrow$ aabb
• bb followed by aa $\rightarrow$ bbaa
• bb followed by bb $\rightarrow$ bbbb

Now we combine these with the prefixes and suffix:

• Prefix ab + Middle aaaa + Suffix ab $\rightarrow$ abaaaaab
• Prefix ab + Middle aabb + Suffix ab $\rightarrow$ abaabbab
• Prefix ab + Middle bbaa + Suffix ab $\rightarrow$ abbbaaab
• Prefix ab + Middle bbbb + Suffix ab $\rightarrow$ abbbbbab
• Prefix ba + Middle aaaa + Suffix ab $\rightarrow$ baaaaaab
• Prefix ba + Middle aabb + Suffix ab $\rightarrow$ baaab bab
• Prefix ba + Middle bbaa + Suffix ab $\rightarrow$ babbaaab
• Prefix ba + Middle bbbb + Suffix ab $\rightarrow$ babbbbab

---

Summary of All Words

The words of length less than or equal to 8 are:

• Length 4: abab, baab
• Length 6: abaaab, abbbab, baaaab, babbab
• Length 8: abaaaaab, abaabbab, abbbaaab, abbbbbab, baaaaaab, baaab bab, babbaaab, babbbbab

---

Skills to Solve Similar Questions

Here is a systematic approach you can use for any similar problem:

1. Deconstruct the Regular Expression First, break the expression down into its main components. Understand what each symbol means:

• Concatenation: Characters next to each other mean "followed by". For example, ab means a followed by b.
• Union (∪ or |): This means "OR". For example, (a ∪ b) means you can choose a or b.
• Kleene Star (*): This means "zero or more repetitions" of the preceding element. For example, a* can be $\epsilon$ (the empty string), a, aa, aaa, etc.
• Positive Closure (+): This means "one or more repetitions". It's like the Kleene star, but you can't have zero repetitions. a+ can be a, aa, aaa, etc.

2. Analyze the Word Structure and Length

• Identify the fixed parts of the expression (those without a * or +). In your problem, (ab ∪ ba) and ab are fixed blocks.
• Identify the variable parts (those with a * or +). In your problem, (aa ∪ bb)* is the variable part.
• Calculate the minimum possible length of a word. This occurs when the Kleene star (*) part is repeated zero times (i.e., it's the empty string).
• Determine how the length changes. Notice that the variable part in your expression, (aa ∪ bb), always adds 2 to the length. This allows you to find a pattern for possible word lengths (e.g., 4, 6, 8, ...).

3. Apply the Constraints Systematically

• The problem will almost always give you a constraint, like "length less than or equal to 8".
• Use the length analysis from the previous step to figure out which cases you need to examine. For your problem, you realized you only need to check lengths 4, 6, and 8.
• Work through each case one by one. For example:
  • "To get length 4, what must the variable part be?"
  • "To get length 6, what must the variable part be?"
  • And so on.

4. Generate All Combinations Methodically

• For each case (e.g., for each length), list out all possible choices for each part of the expression.
• Combine them piece by piece. If there's a prefix (a ∪ b) and a suffix (c ∪ d), make sure you test all four combinations: ac, ad, bc, bd.
• Being organized is key to not missing any words or writing down duplicates. Listing them in alphabetical or structural order helps.

Changelog

8/18/25, 1:13 PM

View All Changelog

• 0f9da-feat: add notes for writing diff combinationson 8/18/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)