Struktur Diskrit : Finite-State Machine dengan Output
Finite State Machines
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 represents the values of the transaction function f and the output function g for all pairs of states and input.
- State TABLE
- State DIAGRAM (a directed graph with labeled edge, state represented by a circle)
Finite State and State Diagram
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
Posting Komentar