# Construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa"

I want to construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa". I tried to follow the same procedure as in all the words that don't have both substring bba and abb, where the goal was to find a regular expression that matches all words that do not contain both "bba" and "abb" as substrings. However, I got stuck at some point and could not get the correct answer. Here are the steps I followed:

Here is how I tried to solve it

1. I constructed an NFA that accepts all words that contain contiguous substring "baa"
2. I constructed the complement of NFA by turning middle states into final states and final states into middle ones. Here it is.
3. I simplified the NFA by adding a new final state and eliminates some states.
4. I tried to write a regular expression for the simplified NFA, but I realized that it still accepts words that contain contiguous "baa" as a substring

Can someone tell me where I went wrong and how to fix it? Is there a better way to approach this problem? Thanks in advance.

• I think the problem is that at step 2 you accept baabaa on the node number 1 alone. At step 1, you could perhaps remove the transition (1, b)->1 and add the transitions (2, b)-> 2 and (2, c)->1 and also (3, b)->2 and (3, c)-> 1 etc, (4,a)->1, (5,b)->2, (6,b)->2 Commented Mar 9 at 10:14

## 1 Answer

I find it easier to build a DFA directly in this case.

• Thanks! I should construct DFA not NFA Commented Mar 13 at 11:57