-1
$\begingroup$

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"enter image description here
  2. I constructed the complement of NFA by turning middle states into final states and final states into middle ones. Here it is. enter image description here
  3. I simplified the NFA by adding a new final state and eliminates some states. enter image description here
  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 enter image description here

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Commented Mar 9 at 10:14

1 Answer 1

-1
$\begingroup$

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

enter image description here

$\endgroup$
1
  • $\begingroup$ Thanks! I should construct DFA not NFA $\endgroup$
    – Nolen
    Commented Mar 13 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.