Finite Automaton Variants Finite Automaton Variants Mohamed M. El Wakil
[email protected]
1
Agenda • Finite State Automaton/Machine (FSA) Finite State Automaton/Machine (FSA) – State transition tables – Non‐deterministic Finite State Automaton(NFA) Non deterministic Finite State Automaton(NFA) – Two‐way Deterministic Finite Automaton (2FA)
• Finite State Transducer Fi it St t T d – Mealy machine – Moore machine
2
Finite State Automaton/Machine Finite State Automaton/Machine • It is a model of computation that consists of: – States • Start/Initial state • Acceptance states • Other states h
– Transitions • Moving from a state to another
– Input string Inp t string • Finite set of symbols
– Actions • • • •
Entry action Entry action Exit action Transition action Input action p 3
Recognition/Acceptance • A A FSA is said to recognize, or accept FSA is said to recognize or accept an input an input string, if it ends at an acceptance state, and the whole input string has been processed the whole input string has been processed.
4
Example • This machine has 7 states, 8 transitions, and 0 actions. • State “Start” is the start state. • If the input is the word If the input is the word “nice” nice , this machine this machine will end at the state “Success”, otherwise it will end at the “Error” will end at the Error state. state
5
Transitions • A A transition is a move from a state A to another state B transition is a move from a state A to another state B based on the current state (i.e. A), and the current symbol of the input string. • Transitions can be viewed as a function with two inputs (current state, and current input symbol), and one (current state, and current input symbol), and one output (next state). For example: – (S1, “n”) Æ S2 – (S1, (S1 “not not_n n”)) ÆS6 ÆS6
• When a symbol is input to a transition function, it is said to be consumed. • Symbols Symbols in the input string are consumed from left to in the input string are consumed from left to right. 6
State Transition Table State Transition Table • Transition Transition functions are expressed via state functions are expressed via state transition tables. • State transition tables can be either one State transition tables can be either one dimension or two dimensions. • This machine accepts – 1111000, 1010, and 000 1111000 1010 and 000
• but, does not accept – 1001, 111, or 001 1001 111 or 001 7
State Transition Tables • One dimension table: Input
Current State
Next State
0
P
Q
0
Q
R
0
R
S
1
P
P
1
Q
R
1
R
‐
• Two dimension tables: Next Current
P
Q
R
S
Input State
0
1
P
1
0
‐
‐
P
Q
P
Q
‐
‐
{0,1}
‐
Q
R
R
R
‐
‐
‐
0
R
S
‐
8
Mathematically speaking Mathematically speaking • A finite state machine is quintuple (Σ,S,s0,δ,F): A finite state machine is quintuple (Σ S s0 δ F): – Σ: Finite non‐empty set of symbols (Input). – S: Finite, non‐empty set of states (States). S: Finite non empty set of states (States) – S0: Initial state S0 belongs to S (Start state). – F: Set of final states, a subset of S. F S t f fi l t t b t fS – δ: Transition function (Transitions) • δ: S x Σ Æ δ S ΣÆS
9
Non‐deterministic Finite State Machine (NFA) h ( ) • The FSA is deterministic, If The FSA is deterministic If – for each pair of state and input symbol there is one and only one transition to a next state one and only one transition to a next state.
• The FSA is non‐deterministic, if The FSA is non deterministic if – it is allowed for a pair of state and input symbol to have more than one possible next state or a have more than one possible next state, or a transition can take place without consuming input symbol (ε y ( transitions)) 10
NFA Example 1 NFA Example 1 • This This machine is non machine is non‐deterministic deterministic as for the as for the pair (P,0), there is more than one possible next state (P and Q) state (P, and Q)
Input State
0
1
P
P,Q
P
Q
R
R
R
S
‐ 11
NFA Example 2 NFA Example 2 • This This machine is non machine is non‐deterministic deterministic it can move it can move from state Q to state R, without consuming any input any input.
Input State
0
1
ε
P
Q
P
‐
Q
‐
R
R
R
S
‐
‐
12
Deterministic Vs. Non‐deterministic Finite State Automaton/Machine / h • NFA – – – –
Easier to design Harder to implement Sl Slower Smaller
• DFA – – – –
Easier to implement Harder to design Faster Bigger 13
Two‐way Two way Finite Automaton Finite Automaton • In DFA, input can be read only once from left to right. , p y g • In 2DFA, input can be read back and forth with no limit on how many times an input symbol can be read. • A 2DFA is a generalization of the DFA. A 2DFA i li ti f th DFA • Transition Transition functions in 2DFA, outputs a new state, and functions in 2DFA outputs a new state and a direction (left, right, or stand still)
14
DFA Vs. 2DFA DFA Vs. 2DFA • 2DFA can solve any problem solvable by DFA. 2DFA can solve any problem solvable by DFA – Why?
• Also Also, problems solvable by a 2DFA, can be problems solvable by a 2DFA can be solved by a DFA1. • But, 2DFA is – much simpler, and – more realistic. 1M. O. Rabin and D. Scott, “Finite automata and their decision problems”, IBM Journal of
Research and Development, 3 (1959), 114–125.
15
Finite State Transducers (FST) Finite State Transducers (FST) • A A FSA can be viewed as a function that maps an FSA can be viewed as a function that maps an input string into the set {0,1}, {True, False}, {Accept Reject} {Accept, Reject}… • A A FST may generate a new string (output string) FST i ( i ) while consuming the input string. • A FST is a FSA with actions producing output! p g p 16
FST Example FST Example • This This machine outputs the one machine outputs the one’ss complement complement of its input, while it is recognizing this input. • For input 000, it outputs 111 • For input 1010, it outputs 0101
17
FST variants FST variants • A A FST, may be non FST may be non‐deterministic deterministic, if it can if it can produce more than one output string for a given input string given input string. • A A FST is either a Mealy machine, or a Moore FST is either a Mealy machine or a Moore machine.
18
Mealy Machines Mealy Machines • A A Mealy machine is finite state transducer that Mealy machine is finite state transducer that produces an output for each transition (i.e has input actions) input actions) • Example: E l
19
Moore Machines Moore Machines • A A Moore machine is finite state transducer Moore machine is finite state transducer that produces an output for each state it enters (i e has entry actions) enters (i.e. has entry actions) • Example: E l – We have to add a new state X
20
Mathematically speaking Mathematically speaking • A finite state transducer is a sextuple (Σ, A finite state transducer is a sextuple (Σ Γ,S,S0,δ, Γ S S0 δ ω): – – – – –
Σ: Finite non‐empty set of symbols (Input). Γ: Finite non‐empty Γ: Finite non empty set of symbols (Output). set of symbols (Output). S: Finite, non‐empty set of states (States). S0: Initial state S0 belongs to S S0: Initial state S0 belongs to S (Start state). (Start state). δ: Transition function (Transitions) • δ: S x Σ Æ S
– ω: Output function • ω: S x Σ Æ Γ (Mealy machine) • ω: S Æ Γ (Moore machine) 21
