finite-automata

How can I construct finite automata


I have to create a deterministic finite automata accepting the set of strings with an even number of 1 and ends with 0.Should I include 0 as a string from this set? and how can I do this?


Solution

  • Should I include 0 as a string from this set?

    Yes

    And how do I do this?

    To construct a finite automaton, you need to identify the states and transitions. The Myhill-Nerode theorem allows you to find the necessary (and sufficient!) states of for a finite automaton if you are able to identify the equivalence classes of "indistinguishable" strings.

    Two strings x and y are indistinguishable, in this sense, if for any other string z, either both xz and yz are in the language, or neither is.

    In your case, let's try to identify equivalence classes. The empty string is in some equivalence class. The string 0 is in a different equivalent class, since you can add the empty string to 0 and get a string in the language (whereas you can't add the empty string to the empty string to get a string in the language). We have found two distinct equivalence classes so far - one for the empty string, one for 0. Both of these will need different states in our FA.

    What about the string 1? It's distinguishable from both 0 and the empty string, since you can add 10 to 1 to get 110, a string in the language, but you can't add it to 0 or the empty string to get a string in the language. So we have yet another state.

    What about the string 00? This string is not in the language, and no other string can be added to this string to get a string in the language. This is another equivalence class. It turns out that the next strings, 01 and 10, are also in this class.

    The string 11 ends up being in the same class as the empty string: you can add any string in the language to 11 and get another string in the language. If you try all strings of length 3, you will find that all of those already fall into one of the above classes, and you can stop checking at that point.

    So we have four states - let's call them [-], [0], [1], and [00]. Now we figure out transitions.

    If you get a 0 in [-], you need to go to [0]... and if you get a 1, you need to go to [1]. For the rest, just figure out what string you'd get by adding to the canonical one, and which class the resulting string would be in... and go to that state.