Automata Theory
Finite Automata
Finite Automata
• Two types – both describe what are called regular languages
– Deterministic (DFA) – There is a fixed number of states and we can only be in one state at a time – Nondeterministic (NFA) –There is a fixed number of states but we can be in multiple states at one time
• While NFA’s are more expressive than DFA’s, we will see that adding nondeterminism does not let us define any language that cannot be defined by a DFA. • One way to think of this is we might write a program using a NFA, but then when it is “compiled” we turn the NFA into an equivalent DFA.
1
Informal Example
• Customer shopping at a store with an electronic transaction with the bank
– The customer may pay the e-money or cancel the emoney at any time. – The store may ship goods and redeem the electronic money with the bank. – The bank may transfer any redeemed money to a different party, say the store.
• Can model this problem with three automata
Bank Automata
Actions in bold are initiated by the entity. Otherwise, the actions are initiated by someone else and received by the specified automata
Start pay
a
b ship redeem ship redeem
d e 2
transfer
f ship Store
Cancel
c
transfer
g
Pay
Cancel
1
Redeem
3
Transfer
4
Start
Start
Customer
Bank
2
Ignoring Actions
• The automata only describes actions of interest
– To be more precise, with a DFA (deterministic finite automaton) we should specify arcs for all possible inputs. – E.g., what should the customer automaton do if it receives a “redeem”? – What should the bank do if it is in state 2 and receives a “redeem”?
• The typical behavior if we receive an unspecified action is for the automaton to die.
– The automaton enters no state at all, and further action by the automaton would be ignored. – The best method though is to specify a state for all behaviors, as indicated as follows for the bank automaton.
Complete Bank
Finite Automata
• Two types – both describe what are called regular languages
– Deterministic (DFA) – There is a fixed number of states and we can only be in one state at a time – Nondeterministic (NFA) –There is a fixed number of states but we can be in multiple states at one time
• While NFA’s are more expressive than DFA’s, we will see that adding nondeterminism does not let us define any language that cannot be defined by a DFA. • One way to think of this is we might write a program using a NFA, but then when it is “compiled” we turn the NFA into an equivalent DFA.
1
Informal Example
• Customer shopping at a store with an electronic transaction with the bank
– The customer may pay the e-money or cancel the emoney at any time. – The store may ship goods and redeem the electronic money with the bank. – The bank may transfer any redeemed money to a different party, say the store.
• Can model this problem with three automata
Bank Automata
Actions in bold are initiated by the entity. Otherwise, the actions are initiated by someone else and received by the specified automata
Start pay
a
b ship redeem ship redeem
d e 2
transfer
f ship Store
Cancel
c
transfer
g
Pay
Cancel
1
Redeem
3
Transfer
4
Start
Start
Customer
Bank
2
Ignoring Actions
• The automata only describes actions of interest
– To be more precise, with a DFA (deterministic finite automaton) we should specify arcs for all possible inputs. – E.g., what should the customer automaton do if it receives a “redeem”? – What should the bank do if it is in state 2 and receives a “redeem”?
• The typical behavior if we receive an unspecified action is for the automaton to die.
– The automaton enters no state at all, and further action by the automaton would be ignored. – The best method though is to specify a state for all behaviors, as indicated as follows for the bank automaton.
Complete Bank