Results 1 to 4 of 4

Math Help - finite Automaton

  1. #1
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20

    finite Automaton

    draw a deterministic finite automaton that decides the language of all binary strings that donot contain 1010 as a substring
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    What have you tried? You won't get any full answers in here - this is not a do-your-homework site.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Also, a hint: Suppose an automaton A decides a language L. Then if you change all accepting states to non-accepting ones and vice versa in A, the resulting automaton decides the complement of L.

    This particular problem is useful because it is not only about finite automata. To develop the required automaton, you need to come up with an algorithm that searches for a substring in a string. This is a problem of fundamental importance and is arguably one of the most successful applications of theoretical computer science. The automaton can be straightforwardly translated into any conventional programming language.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    @ Defunkt

    You don't need to answer it and I don't understand why you r so angry
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Distinct Bases for Finite Vector Spaces over Finite Fields
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: May 29th 2011, 12:31 PM
  2. Replies: 1
    Last Post: May 21st 2011, 04:17 AM
  3. please help with this Q...... of Finite automaton
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 10:21 PM
  4. Discrete Finite Automaton and the pumping lemma
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 24th 2009, 04:39 AM
  5. finite automaton proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 20th 2008, 02:35 PM

Search Tags


/mathhelpforum @mathhelpforum