COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Finite Automata
Copyright By PowCoder代写 加微信 powcoder
COMP3630/6363: Theoory of Computation
Prerequisites. Assessment. Content. Lecturer.
Introduction to Automata Theory, Languages and Computation John E. Hopcroft, , and . Ullman [HMU].
Chapter 1 of HMU (sets, functions, relations, induction) 3 Assignments @ 10% each, Final Exam @ 70%. Languages / Automata / Computability / Complexity. ,
CECS Class Representatives
Roles and Responsibilities
Be creative and proactive in gathering feedback from your class mates about the course.
Act as the official liaison between your classmates and your lecturers in communicating feedback about the course and providing course-related updates to your classmates. You’ll also provide regular reports to the Associate Director (Education) on the feedback you’ve been gathering.
Benefits of Being a Class Rep
The opportunity to develop skills sought by employers – particularly interpersonal, dispute resolution, leadership and communication skills.
Empowerment: Play a more active role in determining the direction of your education. Become more aware of issues influencing your University and current issues in higher education.
Nominations
Please contact CECS Student Services with your name, Student ID and the course number (e.g. ENGN1211) you are interested in becoming a Class Representative for.
This Lecture Covers Chapter 2 of HMU: Finite Automata
Deterministic Finite Automata
Nondeterministic Finite Automata
NFA with ε-transitions
An Equivalence among the above three.
Additional Reading: Chapter 2 of HMU.
Preliminary Concepts
ó Alphabet Σ: A finite set of symbols, e.g., ó Σ = {0, 1} (binary alphabet)
ó Σ = {a,b,…,z} (Roman alphabet)
ó String (or word) is a finite sequence of symbols.
Strings are usually represented without commas, e.g., 0011 instead of (0, 0, 1, 1)
ó Concatenation x · y of strings x and y is the string xy .
ó ε is the identity element for concatenation, i.e., ε · x = x · ε = x.
ó Concatenationofsetsofstrings: A·B={a·b:a∈A,b∈B}
ó Concatenation of the same set: A2 = AA; A3 = (AA)A, etc (We often elide the concatenation operator and write AB for A · B)
ó Kleene-∗orclosureoperator: A∗ ={ε}∪A∪A2 ∪A3···=n≥0An
(Viewing Σ as a set of length-1 strings, Σ∗ is the set of all strings over Σ.)
ó A (formal) language is a subset of Σ∗.
The Deterministic Finite Automaton
Deterministic Finite Automaton (DFA)
Informally:
: : : [Input tape] [Movable Reading Head]
Finite Control
ó The device consisting of: (a) input tape; (b) reading head; and (c) finite control (Finite-state machine)
ó The input is read from left to right
ó Each read operation changes the internal state of the finite-state machine (FSM)
ó Input is accepted/rejected based on the final state after reading all symbols
The Deterministic Finite Automaton
Deterministic Finite Automaton (DFA)
Definition: DFA
ó ADFAA=(Q,Σ,δ,q0,F)
ó Q: A finite set (of internal states)
ó Σ: The alphabet corresponding to the input
ó δ : Q ×Σ → Q , (Transition Function)
(If present state is q ∈ Q, and a ∈ Σ is read, the DFA moves to δ(q, a).)
ó q0: The (unique) starting state of the DFA (prior to any reading). (q0 ∈ Q)
ó F ⊆ Q is the set of final (or accepting) states
Transition Table:
Transition Diagram:
⇤q1q1q1 01
Ü(q0à0) = q2 Ü(q0à1) = q0
Languages accepted by DFAs
Language accepted by a DFA
ó The language L(A) accepted by a DFA A = (Q,Σ,δ,q0,F) is:
ó The set of all input strings that move the state of the DFA from q0 to a state in F
ó This is formalized via the extended transition function δˆ : Q × Σ∗ → Q: ó Basis:
δˆ(q, ε) = q (no state change)
ó Induction:
ó L(A) := all strings that take q0 to some final state = {w ∈ Σ∗ : δˆ(q0,w) ∈ F}.
In other words:
ó ε∈L(A)⇔q0 ∈F ó For k > 0,
s1 s2 s3 sk
w = s 1 s 2 · · · s k ∈ L ( A ) ⇔ q 0 −→ P 1 −→ P 2 −→ · · · −→ P k ∈ F
δˆ(q, ws) = δ(δˆ(q, w), s) (process w, then s)
Languages accepted by DFAs
An Example
ó Is 00 accepted by A? 00
ó q 0 − → q 2 − → q 2 ∈/ F
ó Thus, 00 ∈/ L(A)
ó Is 001 accepted by A?
ó q0 −→ q2 −→ q2 −→ q1 ∈ F
ó Thus, 001 ∈ L(A)
ó The only way one can reach q1 from q0 is if the string contains 01.
ó L(A) is the set of strings containing 01.
ó Remark 1: In general, each string corresponds to a unique path of states.
ó Remark 2: Multiple strings can have the same path of states. For example, 0010 and 0011 have the same sequence of states.
Languages accepted by DFAs
Limitations of DFAs
ó Can all languages be accepted by DFAs?
ó DFAs have a finite number of states (and hence finite memory).
ó Given a DFA, there is always a long pattern it cannot ’remember’ or ’track’ ó e.g., L = {0n1n : n ∈ N} cannot be accepted by any DFA.
ó Can generalize DFAs in one of many ways:
ó Allow transitions to multiple states for each symbol read.
ó Allow transitions without reading any symbol
ó Allow the device to have an additional tape to store symbols ó Allow the device to edit the input tape
ó Allow bidirectional head movement
Non-deterministic Finite Automaton (NFA)
Non-deterministic Finite Automaton (NFA)
ó Allow transitions to multiple states at each symbol reading.
ó Multiple transitions allows the device to:
ó clone itself, traverse through and consider all possible parallel outcomes.
ó hypothesize/guess multiple eventualities concerning its input.
ó Non-determinism seems bizarre, but aids in the simplification of describing an
automaton.
Definition: NFA
ó NFA A = (Q,Σ,δ,q0,F) is defined similar to a DFA with the exception of the transition function, which takes the following form.
ó δ : Q × Σ → 2Q (Transition Function)
ó Remark 1: δ(q,s) can be a set with two or more states, or even be empty!
ó Remark 2: If δ(·, ·) is a singleton for all argument pairs, then NFA is a DFA. (So every DFA is trivally an NFA).
Languages Accepted by NFAs
Language Accepted by an NFA
ó The language accepted by an NFA is formally defined via the extended transition
functionδˆ:Q×Σ∗ →2Q: ó Basis:
܈(qàw) w
܈ ( q à w s ) s
δˆ(q, ε) = {q} ó Induction:
(no state change)
δˆ(q,ws)= δ(p,s),s∈Σ,w∈Σ∗. p ∈ δˆ ( q , w )
ó L(A):={w ∈Σ∗ :δˆ(q0,w)∩F ̸=∅}. In other words:
ó ε∈L(A)⇔q0 ∈F ó For k > 0,
s1 s2 s3 sk
w = s1s2 ···sk ∈ L(A) ⇔ ∃ a path q0 −→ P1 −→ P2 −→ ··· −→ Pk ∈ F
Languages Accepted by NFAs
An Example
ó L(A) = {w : penultimate symbol in w is a 1}.
q0 q0àq1 q2 q2 ;;
ó δ(q0,00) = {q0} q0 −→ q0 −→ q0
ó δ(q0,01)={q0,q1} q0 −→q0 −→q1 q0 −→q0 −→q0
ó δ(q0,10)={q0,q2} q0 −→q0 −→q0 q0 −→q1 −→q2
ó δ(q0,100)={q0} q0 −→q1 −→q0 −→q0
ó Aninputcanmovethestatefromq0 toq2 onlyifitendsin10or11.
ó Each time the NFA reads a 1 (in state q0) it considers two parallel possibilities:
ó the 1 is the penultimate symbol. (These paths die if the 1 is not actually the
penultimate symbol)
ó the 1 is not the penultimate symbol.
Languages Accepted by NFAs
Is Non-determinism Better?
ó Non-determinism was introduced to increase the computational power.
ó So is there a language L that is accepted by an NDA, but not by any DFA?
Theorem 2.4.1
Every Language L that is accepted by an NFA is also accepted by some DFA.
Languages Accepted by NFAs
Is Non-determinism Better?
Proof of Theorem 2.4.1
ó Let N = (QN,Σ,δN,q0,FN) generate the given language L
ó Idea: Devise a DFA D such that at any time instant the state of the DFA is the set
of all states that NFA N can be in.
ó Define DFA D = (QD,Σ,δD,qD,0,FD) from N using the following subset
construction:
QD =2QN qD,0 ={q0} FD ={S⊆QN :S∩FN ̸=∅}
0à1 q0 q1àq2
1 0à1 ; q2 q0àq1 q0àq1àq2 q0 q1 q2
ó Hence,ε∈L(N) ⇔ q0 ∈F ⇔ {q0}∈FD ⇔ ε∈L(D)
Languages Accepted by NFAs
Is Non-determinism Better?
Proof of Theorem 2.4.1
ó To define δD(P,s) for each P ⊆ Q and s ∈ Σ:
ó Assume NFA N is simultaneously in all states of P
ó Let P′ be the states to which N can transition from states in P upon reading s ó Set δD(P,s) := P′ = p∈P δN(p,s).
ó By Induction: δˆN(q0,w) = δˆD({q0},w) for all w ∈ Σ∗
ó Basis: Lets∈Σ
ˆ def def ˆ δN(q0,ε) = {q0} = δD({q0})
ó Induction: assume δˆN(q0,w) = δˆD({q0},w) for w ∈ Σ∗ ˆdefinddefˆ defˆ
ó Thus, δˆN (q0, ·) = δˆD ({q0}, ·), and hence the languages have to be identical.
δN(q0,ws) = δN(p,s) = δN(p,s) = δD(δD({q0},w),s) = δD({q0},ws) p∈δˆN (q0 ,w ) p∈δˆD ({q0 },w )
Languages Accepted by NFAs
Comments about the Subset Construction Method
ó Generally, the DFA constructed using subset construction has 2n states (n = number of states in the NFA).
ó Not all states are reachable! (see example below)
ó The state corresponding to the empty set is never a final state.
1 q0àq1 1 q0àq1àq2
Transtions without Symbol Reading
ε-Transitions
ó State transitions occur without reading any symbols. Definition: ε-transitions
An ε-Nondeterministic Finite Automaton is a 5-tuple (Q,Σ,δ,q0,F) defined similar to a DFA with the exception of the transition function, which is defined to be:
ó An Example:
δ : Q × (Σ ∪ {ε}) → 2Q Ý Ý
q0 q1àq4 ; ; q1 q2 ; ; q2 q3 ; ;
⇤q3 ; ; ; q4 ; q5 ; q5 q6 ; q3
ó Without reading any input symbols, the state of the ε-NFA can transition: Fromq0 toq1,q4,q2,orq3. Fromq1 toq2,orq3.
From q2 to q3. From q5 to q6.
Transtions without Symbol Reading
Language Accepted by an ε-NFA
ó ε-closure of a state
ó ECLOSE(q) = all states that are reachable from q by ε-transitions alone.
ECLOSE(q0) = {q0, q1, q4, q2, q3} ECLOSE(q1) = {q1, q2, q3} ECLOSE(q2) = {q2,q3} ECLOSE(q3) = {q3}
ECLOSE(q4) = {q4} ECLOSE(q5) = {q5,q6} ECLOSE(q6) = {q6}
q4 q5 q6 aÝ
Transtions without Symbol Reading
Language Accepted by an ε-NFA
Givenε-NFAN=(Q,Σ,δ,q0,F)defineextendedtransitionfunctionδˆ:Q×Σ∗ →2Q by induction:
δˆ(q,s)= p∈ECLOSE(q)
δˆ(q, ε) = ECLOSE(q)
ECLOSE(p′)
[s= ε···ε s ε···ε ]
q q1 ::: q Ý=Ý =Ý =ààà
qÝqÝ:::Ýq0 sp0 ÝpÝ:::Ýp 11
ó Induction:
δˆ(q,ws)= ECLOSE(p′)
p ∈ δˆ ( q , w ) p ′ ∈ δ ( p , s )
ó w ∈ L(N) if and only if δˆ(q0, w) ∩ F ̸= ∅
܈ ( q à w )
finitely many
finitely many
܈ ( q à w s )
Transtions without Symbol Reading
Language Accepted by an ε-NFA
ó w ∈ L(N) if and only if δˆ(q0, w) ∩ F ̸= ∅ ó In other words:
ó ε∈L(N)⇔ECLOSE(q0)∩F ̸=∅
q0 Ý p1 Ý ::: Ý pr2F
ó For k > 0,
w=s1s2àààsk2L(A) ,
9 a path such as the following
Ý Ý Ý s1
p1 :::s2p2 ÝÝÝ
pk 1 Ý Ý ::: Ý sk pk Ý
pk Ý Ý ::: Ý qF2F
Transtions without Symbol Reading
Do ε-NFAs Accept More Languages?
Theorem 2.5.1
Every Language L that is accepted by an ε-NFA is also accepted by some DFA. Proof of Theorem 2.5.1
ó Given L that is accepted by some ε-NFA, we must find an NFA that accepts L. ([NFA to DFA conversion can then be done as in Theorem 2.4.1].
ó Let ε-NFA N = (QN,Σ,δN,q0,FN) accept L.
ó Let us devise NFA N′ = (QN′,Σ,δN′,q0′,FN′) as follows:
QN′ =QN q0′ =q0 FN′ ={q∈QN :ECLOSE(q)∩FN ̸=∅} δN′ :QN′ ×Σ→2QN′ definedby: δN′(q,s)= δ(p,s)
p∈ECLOSE(q)
N: q Ý Ý ::: Ý p s p0
N : q can transition to p0 after a few Ý-transitions, and a single read of s 2 ⌃.
N0: q s p0
N0: q can transition to p0 after reading s.
Transtions without Symbol Reading
Do ε-NFAs Accept More Languages?
Proof of Theorem 2.5.1 (Cont’d)
[Argument is handwavy, but can be formalized!]
s1 :::sk is accepted by Ý-NFA N s1 :::sk is accepted by NFA N0 mm
Ý Ý Ý s1
p1 :::s2p2 ÝÝÝ
Ý Ý Ý sk
pk 1 ::: pk
Ý ::: Ý qF2F
ECLOSE(pk)\FN 6=;
Transtions without Symbol Reading
To Summarize…
Languages accepted = Languages accepted = Languages accepted by DFAs by NFAs by ε-NFAs
ó Allowing non-determinism and/or ε-transitions does not improve the language acceptance power of (finite) automata.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com