draw a deterministic finite automaton that decides the language of all binary strings that donot contain 1010 as a substring

Printable View

- Oct 3rd 2010, 08:31 PMgirgishffinite Automaton
draw a deterministic finite automaton that decides the language of all binary strings that donot contain 1010 as a substring

- Oct 4th 2010, 02:29 AMDefunkt
What have you tried? You won't get any full answers in here - this is not a do-your-homework site.

- Oct 4th 2010, 07:15 AMemakarov
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. - Oct 11th 2010, 09:25 PMgirgishf
@ Defunkt

You don't need to answer it and I don't understand why you r so angry :)