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 with DFA/NFA

  1. Jan 25, 2009 #1
    Hi there, I've been working on DFA's and NFA's in class, and for the most part I get it, but I want to make sure im doing a couple of these right, and maybe you guys can give some insight on how to complete the ones that make no sense to me. With that, on to the first one!

    1. The problem statement, all variables and given/known data

    For this problem, we'll work over the alphabet [tex]\Sigma[/tex]= {a, b, c}. Design a DFA to recognize the language: L[tex]_{}1[/tex] = {w| if there is a b in w, then there is a c in w}

    3. The attempt at a solution
    I couldn't think of any other way of posting this, so im just attaching an image (a pretty bad one at that, sorry!):


    Anyways, does that seem right? I didnt know what to do if b didnt exist since if b->c and b=false, we dont know what c could be right? Any help is greatly appreciated!

    Im also having trouble with:
    Using the same alphabet, design NFAs for each of the following languages:
    L[tex]_{}4[/tex]= {w| w ends with bac}
    L[tex]_{}5[/tex]= {w||w| mod 2 = 1 or w ends with a}

    for the first one I got:

    But the second I have no idea.

    Finally could someone tell me where to even start with:
    Recall that we can interpret a string over {0,1} as the binary representation of an
    integer starting with the least signi cant bit, so that for example 011 = 6.Using the alphabet {0,1}, prove that the language {x | x mod 3 = 0} is regular.

    Any help is greatly appreciated!
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted