[go: up one dir, main page]
Scribd
Upload
86 views7 pages

Formal Methods: Finite State Machine-Moore Machine

This document discusses Moore machines, a type of finite state machine (FSM). A Moore machine's outputs depend only on its present state, not the inputs. It is described by 6 tuples: states, initial state, input symbols, output symbols, transition function, and output function. An example Moore machine is provided that accepts strings of a's and b's ending in a, with its transition and output tables defined. Homework is assigned to design a DFA that accepts all strings ending with 0.

Uploaded by

Status Life
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
86 views7 pages

Formal Methods: Finite State Machine-Moore Machine

This document discusses Moore machines, a type of finite state machine (FSM). A Moore machine's outputs depend only on its present state, not the inputs. It is described by 6 tuples: states, initial state, input symbols, output symbols, transition function, and output function. An example Moore machine is provided that accepts strings of a's and b's ending in a, with its transition and output tables defined. Homework is assigned to design a DFA that accepts all strings ending with 0.

Uploaded by

Status Life
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

FORMAL

METHODS
Lecture 7: Finite state machine- Moore Machine

LECTURER: QURATULAIN
DEPARTMENT OF INFORMATION TECHNOLOGY
GOVERNMENT COLLEGE UNIVERSITY FAISALABAD
MOORE MACHINE

Moore machine is an FSM whose


outputs depend on only the present
state.
MOORE MACHINE
Moore machine can be described by 6 tuples (Q, q0, ∑, O,
δ, λ) where,
Capital Q- Q: finite set of states
Q0- q0: initial state of machine
Sigma- ∑: finite set of input symbols
O: output alphabet
Delta - δ: transition function where Q × ∑ → Q
Lambda- λ: output function where Q → O
Example : Transition Table
Q = {q0, q1, q2}
Next state for Next State of
∑ = {0, 1} Present State OUTPUT
Input 0 Input 1
q0 = {q0}
→q0 q0 q1 a
O: {a,b}
q1 q2 q0 b
q0 0
00110, n → n+1
q0 1 F q2 q0 q1 b
5→6
q1 0
q1 1 00110, aaabaa
q2 0 0
0
q2 1
--------- 1 0

q0 a
Start qo/a q1/b q2/b
q1 b
q1 b
1 1
That accepts strings of a’s and b’s, ending
with A. baa, n → n+1
Q = {q0, q1} 3→4
b a
∑ = {a, b} a
baa, 0011 Start qo/0 q1/1
q0 = {q0}
F = {q1} {q0}
O: {0,1} {q1} b
{q1}

q0 a baba, n → n+1
4→5
q0 b
Transition Table
q1 a baba, 00101
q1 b Present Next state for Next State of
{q0} Output
State Input a Input b
{q1}
q0 0 {q0} →q0 q1 q0 0
{q1}
q1 1
L= { aa, ab, ba, baa, baba, aba, aba,…} q1 q1 q0 1
DFA: ACCEPTS ALL ENDING WITH 0. HOME TASK
110, n → n+1
Q = {q0, q1} 3 → __
∑ = {__, __}
Transition Table
110, ____
q0 = {q0} Presen Next state for Next State of
Output
t State Input 0 Input 1
F = {q1} {q__}
O: {__,__} {q__} →q0 q1 q0 ____
{q__}

q0 01010, n → n+1 q1 q1 q0 ____


5 → __
q0 1
0110, ____ 0
q1
q1 0
{q__} Start
{q __}
q0 {q__} qo/a q1/b
{q__}
q1
L= { 0, 10, 010, 110, 01010, 0110, 1110..} 1
Next Lecture TYPES OF FINITE STATE
MACHINE

Mealy State Machine

You might also like