, q0,
F, T) where:
A finite-state automaton is comprised of a set of five objects (Q,
, q0,
F, T) where:
| 1. | Q : a finite set of states the automaton can be in. |
| 2. | : a finite
set of input symbols, called alphabet. |
| 3. | q0 : the start state
of the automaton, q0  Q.
|
| 4. | F : a set of accept (final) states, F Q.
|
| 5. | T : a transition function Q x I  Q.
The transition function defines the movement of an automaton from one state
to another by treating the current state and current input symbol as an
ordered pair. For each pair of "current state" and "current
input symbol" (the function input), the transition function produces
as output the next state in the automaton. |
The operation of a finite-state automaton is always illustrated in a state diagram. For instance, a finite automaton M is shown in the state diagram below.
In this case, Q = {q0, q1, q2}, I (alphabet)= {0, 1}, F(set of accept states)= {q1} and q0 is the start state.
The transition function T can be described by a transition function table, as follows:
| State/Input Symbol | 0 | 1 |
|
q0 |
q1 |
q0 |
|
q1 |
q2 |
q1 |
|
q2 |
q1 |
q1 |
The transition function can be represented as T(current
state, current input symbol)next
state. For instance if q0 is
the current state and 0 is the current input symbol, then the transition
function is T(q0,
0)q1.
You can check this by comparing the transition table with the above state
diagram.
Languages Accepted by An Automaton
Consider the automaton (machine) M shown below. When the input string 10011 is fed to machine M, the processing proceeds as follows:
M
| 1. start in state q0; | Transition Function |
| 2. read 1, follow transition from q0 to q0; | T(q0,
1)q0 |
| 3. read 0, follow transition from q0 to q1; | T(q0,
0)q1 |
| 4. read 0, follow transition from q1 to q2; | T(q1,
0)q2 |
| 5. read 1, follow transition from q2 to q1; | T(q2,
1)q1 |
| 6. read 1, follow transition from q1 to q1; | T(q1,
1)q1 |
| 7. accept because M is in accept state q1 at the end of the input. |
On any input string w, if the transition doesn't reach
an accept state at the end of the input, it means that the machine rejects
the input. Suppose that instead of the above example, we had fed in the
string 10010. The transitions would be the same up to step 6, where
the transition function would be replaced with T(q1,
0)q2.
In this case, the final state of M would be q2,
which is not an accept state. This means that M rejects
that particular input.
If A is the set of strings that a machine N accepts, we say that A is the language of machine N and write L(N) = A. When a machine accepts a language, that language is the collection of all strings which the machine will accept. A machine may accept several strings, but it always accepts only one language.
Designing A Finite-State Automata
Now consider the problem of starting with a description of a language and designing an automaton to accept exactly that language.
Consider the following example:
| Example: | Design a finite-state automaton that accepts the set of all strings of 0's and 1's containing exactly three 1's. |
| Solution: | The automaton M must have at least four distinct states:
q0: the start state; q1: the state to which M goes when the first 1 is read from the string; q2: the state to which M goes when the second 1 is read from the string; q3: the state to which M goes when the third 1 is read from the string; If M is in state q0 and a 0 is input, M stays in state q0, but as soon as a 1 is input , M moves to state q1. At state q1, if a 0 is input, M stays in state q1, but as soon as a 1 is input, M moves to state q2. As above, M stays in state q2, until a 1 is input, then M moves to q3. At state q3, if a 0 is input, the input string still has three 1s. so M stays in state q3. But if a 1 is input (i.e., the fourth 1 in the string), then the input string contains more then three 1's, so M must leave q3 (as no string with more than three 1s is to be accepted by M). M cannot go back to any of the previous states q0, q1, or q2 because those states can go to q3 again. So M must go to a fifth state, q4, from which there is no return to q3. The complete state diagram for M is shown below.
|
Go
to next section review. Go
to Class Agenda. 
