1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help me make a combined NFA for this languag

  1. Apr 3, 2012 #1
    1. The problem statement, all variables and given/known data

    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"}

    2. Relevant equations

    3. 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.

    Attached Files:

    Last edited: Apr 3, 2012
  2. jcsd
  3. Apr 4, 2012 #2
    No one knows how to make DFA's?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook