Results 1 to 6 of 6

Math Help - Languages and FSM.

  1. #1
    Newbie
    Joined
    Feb 2011
    Posts
    8

    Languages and FSM.

    I seem to be stuck in the last section of my maths work,just cannot seem to grasp the logic behind it.....somebody please help??
    here the last 2 questions.

    a) Design and draw the state transition network for a deterministic nite state
    machine acceptor for input alphabet {0; 1} which would accept strings which
    start with 01 or 1, followed by any number of 0's, and and ending in the sequence
    101 and no other strings.

    b) Write out the State Transition Table that describes your machine.


    thanks in advance
    Last edited by mr fantastic; April 3rd 2011 at 06:41 PM. Reason: Title.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Actually, this automaton is incorrect because it does not accept 101. OP, do you have ideas about how to correct it? I can return to it later if needed.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2011
    Posts
    8
    Geez that was fast in regards to your question, it is the first time I have had to tackle this kind of mathmatics, regardless of how much I read through the books the penny has not dropped yet. so i guess the answer is ...No.


    Thnaks again
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2011
    Posts
    8
    I have tried with it but still no luck fathoming this out...emakarov if you can help i would greatly appreciate .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    a deterministic finite state machine acceptor for input alphabet {0; 1} which would accept strings which start with 01 or 1, followed by any number of 0's, and and ending in the sequence 101 and no other strings
    The more I read this formulation, the more it seems somewhat ambiguous to me. It may mean, "followed by any number of 0's and then by 101" or "followed by any number of 0's. It also must end in 101." In the latter case, 101 is accepted because it starts with 1 followed by one 0; it also ends with 101, but in the former case, it is not accepted. The automaton I draw corresponds to the former case; the latter one is more complicated.

    I am also not sure what exactly you don't understand. If you need more intuition about how FSM work, write several strings consisting of 0's and 1's and see whether the automaton above accepts them by following from one state to the next along the arrows. The arrow's label (0 or 1) must correspond to the next unread character in the string. If you end up in the state with the double border when the string is exhausted, the string is accepted; otherwise it is not accepted.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automata Languages and DFA etc.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 20th 2011, 08:32 AM
  2. How many different languages?
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 22nd 2011, 05:56 AM
  3. context free languages
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2010, 06:11 PM
  4. countability of languages
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 21st 2010, 11:18 AM
  5. countable languages..please help!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 17th 2010, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum