Discrete Mathematics for Computer Science

592 APPENDIX B Finite Automata

8(010, q2) = 3(10, B(0, q2)) = 6(10, qo)

8(10, q2) = 8(0, 8(1, qo)) = 8(0, qj)

8(0, ql) = q2

Since 10010 leads to an accepting state, this word is in the language. U

Definition 2. The language accepted by a finite automaton or automata is the set of

strings in E * accepted by the finite automaton.

Example 2. The finite automaton shown in Figure B.1 accepts the language of binary

words that represent positive odd integers. States with double-circle boundaries are accept

states. The symbol on a directed edge indicates what the next state is for that symbol. The

figure is called a state diagram for the finite automaton.

(^1 0)
Figure B.1 Automaton to accept odd integers.
Example 3. The finite automaton shown in Figure B.2 accepts the language of binary
words that represent even positive integers.
(^1 0)
Figure B.2 Automaton to accept even integers.
rn Exercises

1. Let E = {0, 11 and Q = {qo, ql, q2}. qo is the start state, and {qlI is the set of accept-

ing states. The function 8 is defined as

8 qo qj q2

0 ql ql q2

1 q2 ql qo