|
In order to know what is computable (and what is not computable) we need to have a clear model of computation. It seems reasonable to start with a very simple model.
The model discussed here is very weak. We ask, what can be computed if you have a fixed, finite amount of memory, but must nonetheless be able to solve problems whose inputs are arbitrarily large?
Chapter 2 of Sipser describes finite state machines, which he calls DFAs. (DFA stands for deterministic finite automaton.) I will try to match Sipser's terminology, so I will also call them DFAs. The discussion of DFAs here is intended only to be a sketch. Sipser provides far more detail.
A DFA solves a language problem. Its input is a string and it answers yes or no to the question, is the input in this language?
Suppose that we want to make a DFA to solve a particular problem. That problem should have an alpabet in which inputs can be written, which is also the alpabet of the DFA.
A DFA has a finite set of states. One of those states is designated as a start state. Every state is designated either as an accepting state or as a rejecting state.
For each state q and symbol c in the alphabet, there is another state q' = δ(q, c). We say that there is a transition from q to q' on symbol c.
It is easiest to understand a finite state machine in a diagramatic form. Here is an example with alphabet {a, b}. (I apologize for the ASCII art, but I do not have time to produce better graphics.)
Let's call this example M1.
| v _____ b _____ ___| |------>| |___ a | | 0 | | 1 | | b `-->| (y) |<------| (n) |<--' |_____| a |_____|
State 0 is an accepting state (marked (y) for yes) and state 1 is a rejecting state (marked (n) for no). (Sipser uses a single circle around a state for a rejecting state and a double circle for an accepting state.)
The start state is state 0 (indicated by the arrow pointing to state 0.) The transitions are:
δ(0, a) = 0
δ(0, b) = 1
δ(1, a) = 0
δ(1, b) = 1
The idea is to read an input and follow a transition for each symbol. Suppose that the input is abba. M1 starts in state 0. When the first a is read, it goes stays in state 0. It goes through the following chain of states.
a b b a 0 ---> 0 ---> 1 ---> 1 ---> 0
Since it ends in state 0 and state 0 is an accepting state, we say that M1 accepts string abba. On input bab, M1 goes through state sequence
b a b 0 ---> 1 ---> 0 ---> 1
Since the last state is a rejecting state, we say that M1 rejects string bab.
It should be clear that M1 accepts all strings that end on a and rejects all that end on b. So the language accepted by M1 (written L(M1)) is
L(M1) = {x | x ∈ {a,b}*, x ends on a}
A finite state machine M consists of 5 things: An alphabet A, a set of states Q, a start state q0 ∈ Q, a subset F of Q whose members are the accepting states, and a function δ: Q×A → Q.
We define another function δ*: Q×A* → Q so that δ*(q,s) is the state on which M stops when it reads string s, starting in state q. The definition of δ* is as follows.
δ*(q, ε) = q
δ*(q, sc) = δ(δ*(q, s), c)
where both equations hold for every state q and the second equation holds for all strings s ∈ A* and symbols c ∈ A.
The language that M accepts is L(M) defined by
L(M) = {s | s ∈ A*, δ*(q0, s) ∈ F}.
That is, M accepts all strings take M to an accepting state when M starts in state q0.
Here is another example of a DFA, M2. This one has alphabet {0,1} and states {0,1,2}.
| v ___ 1 ___ 0 ___ ___| |------>| |------>| |___ 0 | | 0 | | 1 | | 2 | | 1 `-->| y |<------| n |<------| n |<--' |___| 1 |___| 0 |___|
DFA M2 has only 3 states. That means it can only remember one of 3 possible pieces of information about the input that it has read at any point.
Think of the input s of M2 as a binary number, and let Ns be the number that s stands for. For example,
N110 = 6since 110 is a binary representation of 6. (An empty string stands for 0.)
Claim. If δ*(0, s) = i thenNs mod 3 = i,for i = 1, 2, 3.
That is, what M2 remembers is the input mod 3. Since state 0 is the only accepting state,
L(M2) = {s | s is a binary number that is divisible by 3}.
The claim is based on the following facts.
If x is a binary number, then
x0 represents 2x,For example, 110 represents 6. 1100 represents 12 = 2(6) and 1101 reprents 13 = 2(6) + 1.
x1 represents 2x + 1.
For any integer x, if x mod 3 = y then
(2x) mod 3 = (2y) mod 3,
(2x+1) mod 3 = (2y+1) mod 3.
2(0) mod 3 = 0
2(1) mod 3 = 2
2(2) mod 3 = 1
(2(0) + 1) mod 3 = 1
(2(1) + 1) mod 3 = 0
(2(2) + 1) mod 3 = 2
When M2 moves from state a to state b on a 0, it is always true that b = (2a) mod 3.
When M2 moves from state a to state b on a 1, it is always the case that b = (2a+1) mod 3.
The machine starts in state 0 = 0 mod 3.
So, after reading the bits of binary number x, M2 is in state x mod 3. ◊
|