Turing's Vision: The Birth of Computer Science by Chris Bernhardt

Author:Chris Bernhardt [Bernhardt, Chris]
Language: eng
Format: epub
Tags: Computers, Computer Science, History
ISBN: 9780262034548
Google: Bf0NDAAAQBAJ
Publisher: MIT Press
Published: 2016-05-13T00:35:28.700013+00:00

Figure 1

M2: Strings that end with 01.

We return to the example. We now need to give information about what happens when we are in a state and either 0 or 1 is input. We go through each state in turn. For each state we first say which state is entered when a 0 is input and then which state is entered when a 1 is input — using a single 1 to separate these pieces of information.

In state 1, if 0 is entered we move to state 2, if 1 is entered we move to state 1. This is encoded as 0010. In state 2, if 0 is entered we move to state 2, if 1 is entered we move to state 3. This is encoded as 001000. In state 3, if 0 is entered we move to state 2, if 1 is entered we move to state 1. This is encoded as 0010. Each of these three pieces of information are separated by two 1s. This gives 001011001000110010. This is now added to the encoding we have so far, to obtain 1111000111000111001011001000110010. Finally, we add four 1s to indicate that we have finished the description. The final encoding is 11110001110001110010110010001100101111.

The standard notation for the encoding of a machine M is 〈M〉, so

〈M2〉 = 11110001110001110010110010001100101111.

It is important that we can not only encode a finite automaton and obtain a string of 0s and 1s, but that we can also decode the string. We should not only be able to go from M to 〈M〉, but should also be able to convert 〈M〉 back to M. It is possible to do this with our method of encoding. To illustrate, consider the string 1111001110011100101101001111. We will go through the decoding of this example in a step by step way.

The first four 1s just say that we are beginning a description of a machine, and the last four 1s say that we are ending the description. We now read off the first substring of 0s.

1111001110011100101101001111

There are two 0s telling us that the machine has two states. The next substring of 0s

1111001110011100101101001111

tells us that state 2 is the accept state. The next bolded substring

1111001110011100101101001111

tells us that in state 1 if we receive a 0 we move to state 2 and if we receive a 1 we move to state 1. Finally the bolded substring

1111001110011100101101001111

tells us that in state 2 if we receive a 0 we move to state 1 and if we receive a 1 we move to state 2. This is a complete description of the finite automaton. It is drawn in figure 2. This machine, M9, is one that recognizes strings with an odd number of 0s.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.