NFA for strings with one "dab" and no "bad" substrings

  • Thread starter zeion
  • Start date
1 reply · 2K views · last reply
zeion
Messages
455
Reaction score
1

Homework Statement



Give an NFA and RE for each of the following languages.

L1 = {s \in {a, b, d}* : s contains exactly one occurrence of the substring "dab" and no occurrence of the substring "bad"}

Homework Equations


The Attempt at a Solution



I made two separate NFAs for each condition, then tried to combine them:Do they look right?
How can I simplify the combined one so that I can make a RE expression out of it?
I'm not sure how to make a "trap" state because the accepting states all have different paths to dead states?

Any help appreciated, thanks.
Thanks.
 
Attachments
  • NFA diagram with three states q0, q1 and q2, all drawn as accepting. q0 is the start state with a self-loop labelled a, d and a b transition to q1; q1 has a self-loop labelled b, d and an a transition to q2; q2 has a self-loop labelled a, b.
    e6-2aNFA_Bottom.jpg
    5.7 KB · Views: 549
  • State diagram of an NFA with states q0 to q5 over alphabet a, b, d; q0 start, q3 to q5 accepting, transitions d, a, b, d, a along the chain.
    e6-2aNFA_Top.jpg
    10.2 KB · Views: 512
  • State diagram of an NFA with states q0 to q52, self-loops labelled a, b, d on several states, and transitions labelled a, b and d between them, with q31 and q32 double-circled as accepting states.
    e6-2aNFA.jpg
    5.8 KB · Views: 545
Last edited:

Discussion

Similar threads

Designing an NFA that accepts binary strings divisible by 5 or 6
  • Lolligirl
  • · Replies 6 ·
  • AI and Computer Science
Replies
6
Finding K-Byte Substrings in Two Long Strings
  • Hurkyl
  • · Replies 7 ·
  • Computing and Technology
Replies
7