Transcript Q - IDA

CS Master – Introduction to the Theory of Computation
Lecture 2
Finite Automata
Jan Maluszynski, IDA, 2007
http://www.ida.liu.se/~janma
janma @ ida.liu.se
Jan Maluszynski - HT 2007
2.1
CS Master – Introduction to the Theory of Computation
Deterministic Finite Automata
DFA A is defined as (Q, , , q0, F)
• Q States
•  Alphabet
• Transition function  : Q    Q
• Initial state q0  Q
• Final (accept) states: F  Q
A moves from state to state on input strings: next state
unique for given symbol and state
A accepts s iff s brings A from q0 to some final state.
The language L(A) is the set of accepted strings
Jan Maluszynski - HT 2007
2.2
CS Master – Introduction to the Theory of Computation
Nondeterministic Finite Automata
NFA M is defined as (Q, , , q0, F)
• Q States
•  Alphabet
• Transition function  : Q   {}  P(Q)
In q M can move on input c to any of the states in (q,c)
• Initial state q0  Q
• Final (accept) states: F  Q
M accepts s iff s can bring M from q0 to some final state.
Jan Maluszynski - HT 2007
2.3
CS Master – Introduction to the Theory of Computation
DFA vs. NFA
Finite automata M and N are equivalent iff
L(M)=L(N)
For every NFA there exists an equivalent DFA. (see
the construction pp. 54-58).
For every FA there exists a unique DFA (up to
renaming of states) with a minimal number of
states (the construction not discussed in the
book)
Jan Maluszynski - HT 2007
2.4
CS Master – Introduction to the Theory of Computation
Regular languages
Definition: A language is regular iff it is accepted by
a Finite Automaton
Regular languages are closed under
• Union
• Kleene Star
• Concatenation
• Intersection
Jan Maluszynski - HT 2007
2.5
CS Master – Introduction to the Theory of Computation
Proving closure properties
• Construct NFA’s for basic automata
• Construct combinations of NFA’s for
• Concatenation
• Union
• Kleene star
pp.59-63
• Construct product of DFA’s for proving
closure under intersection. p.45
Jan Maluszynski - HT 2007
2.6