Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Struktur Diskrit : Finite-State Machine dengan Output

Finite State Machines

A Finite State Machine are used to model many kinds of machine (computer components, vending machine) as the basis for programs for spell checking, grammar checking, indexing or searching large bodies of text, recognizing speech, transforming text and network protocol.

A Finite State Machine include a finite set of states, with a designated starting state, an input alphabet and a transition function that assigns a next state to every state and input pair.

A Finite State Machine can produce output or no output.

Example: vending machine

A vending machine accepts nickels (5 cents), dimes (10 cents), and quarters (25 cents).

When a total of 30 cents or more has been deposited, the machine immediately returns the amount in excess of 30 cents. When 30 cents has been deposited and any excess refunded, the customer can push an orange button and receive an orange juice or push a red button and receive an apple juice.

The machine can be in any of seven different states 𝑠𝑖, 𝑖 = 0,1,2,…,6 where 𝑠𝑖 is the state where the machine has collected 5𝑖 cents. The machine starts in state 𝑠0, with 0 cents received. The possible inputs are 5 cents, 10 cents, 25 cents, the orange button (O), and the red button (𝑅). The possible outputs are nothing (𝑛), 5 cents, 10 cents, 15 cents, 20 cents, 25 cents, an orange juice and an apple juice.

We can use a state table to represent the values of the transition function f and the output function for all pairs of states and input.

We can use a directed graph (state transition diagram or state diagram or transition diagram) to represent the values of the transition function f and the output function for all pairs of states and input.

Finite State Machines with Output

A Finite State Machine, M = (S, I, O, f, g, s0) consists of:

• A finite set S of states
• A finite input alphabet I
• A finite output alphabet O
• A transition function f that assigns to each state and input pair a new state
• An output functions g that assigns to each state and input pair an output
• An initial state s0 

A Finite State Machine can be represented by

• State TABLE
• State DIAGRAM (a directed graph with labeled edge, state represented by a circle)

Finite State and State Diagram

State TABLE represents the values of the transaction function f and the output function g for all pairs of states and input. 

State DIAGRAM is a directed graph with labeled edge. Each state represented by a circle. Arrows labeled with the input and output pair are shown for each transition.

Exercises

Draw the state diagrams for the finite state machines with the following tables.

Construct the state tables for the finite state machines with the following state diagrams. 

Input and Output String

Given the following finite state machine. 

• If the input string is 0111 then the output string is 1100.
• If the input string is 11011011 then the output string is 00110110.

Sumber

Slide Strukdis : FSM with output