Discrete Mathematics for Computer Science

Finite Automata

A fundamental problem in computer science is to decide whether a word is in a language.
For the case of regular sets or regular languages, the problem is solved using a very special
sort of computer, called a finite automaton.

Definition 1. A finite automaton consists of five elements:

(a) An alphabet E. Our input strings will be elements in E
(b) A finite set Q, the elements of which are called states.
(c) A designated start state in Q called qo.
(d) Some subset of Q is designated as the set of accepting states.
(e) A transition function 8, which indicates what state should be entered as a result of
processing the next letter in the input word. By convention 6(xw, q) = 8(w, 8(x, q))
for any word t and any element x E E. A word a) E E* is accepted or is in the
language if (wo, q0) is in the set of accepting states.

Example 1. Let E = {0, 1} and Q = {q0, ql, q21. q0 is the start state, and {q2} is the set
of accepting states. The function 8 is defined as

8(0, qo) = q2 8(0, ql) = q2 8(0, q2) = qo

3(1, qo) = ql 8(1, ql) = ql 8(1, q2) = ql

The word (^11001) is not in the language. The word 10010 is in the language.
Solution. We must compute 8(11001, qo):
8(11001, qo) = 8(1001, 8(1, qo)) = 8(1001, ql)
8(1001, ql) = 3(001, 3(1, ql)) = 3(001, ql)
8 (001, qa) = 8(0, (0, q1)) = 8(01, q2)
8(01, q2) = 8(1, 8 (0, q2)) = 8 (1, qo)
8(1, qo) = qj
Since 11001 does not lead to an accepting state, this word is not in the language.
We must now compute 8(10010, qo):
6(10010, qo) = 8(0010, 8(1, qo)) = 6(0010, qj)
3(0010, qj) = 8(010, 6(0, ql)) = 3(010, q2)
591