留学生考试辅导 COMP3630/6360: Theory of Computation Semester 1, 2022

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 ∈ Σ∗ ˆdef􏰋ind􏰋defˆ 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 ÝÝÝ
pk1 Ý Ý ::: Ý 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
pk1 ::: 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