Finite State Machines
1 INTRODUCTION
This chapter discusses two types of “machines.” The ?rst is a ?nite state machine (FSM) which is similar to a ?nite state automaton (FSA) except that the ?nite state machine “prints” an output using an output alphabet which may be distinct from the input alphabet. The second is the celebrated Turing machine which may be used to de?ne computable functions.
2 FINITE STATE MACHINES
A ?nite state machine (or complete sequential machine) M consists of six parts: (1) A ?nite set A of input symbols. (4) An initial state s0 in S.
(2) A ?nite set S of “internal” states. (5) A next-state function f from S × A into S.
(3) A ?nite set Z of output symbols. (6) An output function g from S × A into Z.
Such a machine M is denoted by M = M(A, S, Z, s0 , f, g) when we want to indicate its six parts.
EXAMPLE 1 The following de?nes a ?nite state machine M with two input symbols, three internal states, and three output symbols:
(1) A = {a, b}, (2) S = {s0 , s1 , s2 }, (3) Z = {x, y, z}, (4) Initial state s0 ,
(5) Next-state function f : S × A ? S de?ned by:
f (s0 , a) = s1 , f (s1 , a) = s2 , f (s2 , a) = s0
f (s0 , b) = s2 , f (s1 , b) = s1 , f (s2 , b) = s1
(6) Output function g : S × A ? Z de?ned by:
g(s0 , a) = x, g(s1 , a) = x, g(s2 , a) = z g(s0 , b) = y, g(s1 , b) = z, g(s2 , b) = y
State Table and State Diagram of a Finite State Machine
There are two ways of representing a ?nite state machine M in compact form. One way is by a table called the state table of the machine M , and the other way is by a labeled directed graph called the state diagram of the machine M .
The state table combines the next-state function f and the output function g into a single table which represent the function F : S × A ? S × Z de?ned as follows:
F (si , aj ) = [f (si , aj ), g(si , aj )]
For instance, the state table of the machine M in Example 1 is pictured in Fig. 1(a). The states are listed on the left of the table with the initial state ?rst, and the input symbols are listed on the top of the table. The entry
in the table is a pair (sk , zr ) where sk = f (si , aj ) is the next state and zr = g(si , aj ) is the output symbol. One
assumes that there are no output symbols other than those appearing in the table.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .