Week 6 Flashcards
What does it mean to say an FSA is non-deterministic?
It means the computer makes a choice between several possible next moves.
What is the set Q?
The set of all possible moves.
What is the set Σ?
The set of all possible inputs.
What is q0?
The starting state
What is F?
The set of final states.
What is δ?
A mapping of moves, of the form δ(current state, input) = new state
Give the formal definition of a deterministic FSA.
A deterministic finite state automaton is a quintuple
FSA = <Q, Σ, δ, q0, F>
where
Q: a finite, nonempty set of states;
For all Σ: a finite input alphabet;
For all δ: a mapping from Q x Σ into Q;
q0 ∈ Q : the initial state;
F ⊆ Q : the set of final states.
Give the formal definition of a non-deterministic FSA.
A non-deterministic finite state automaton is a quintuple
FSA = <Q, Σ, δ, q0, F>
where
Q: a finite, nonempty set of states;
For all Σ: a finite input alphabet;
For all δ: a mapping from Q x Σ into P(Q) where P is powerset;
q0 ∈ Q : the initial state;
F ⊆ Q : the set of final states.
Give the formal definition of a deterministic FST.
A deterministic finite state transducer is a sextuple
DFST = <Q, Σ, Delta, δ, q0, F>
where
* Q: a finite, nonempty set of states
* Σ: a finite input alphabet
* Delta: a finite output alphabet
* δ: a mapping from Q x E into Q x Delta*
* q0 ∈ Q: the initial state
* F ⊆ Q: the set of final states
Give the formal definition of a non-deterministic FST.
A deterministic finite state transducer is a sextuple
DFST = <Q, Σ, Delta, δ, q0, F>
where
* Q: a finite, nonempty set of states
* Σ: a finite input alphabet
* Delta: a finite output alphabet
* δ: a mapping from Q x E into finite subsets of Q x Delta*
* q0 ∈ Q: the initial state
* F ⊆ Q: the set of final states
What does a+ mean?
Any number of a’s but at least one.
What does a* mean?
Any number of a’s including 0.
What is a epsilon (e) transition?
An empty transition, the automaton can simply decide to change state without any input of symbol.
