[SOLVED] 代写 R C algorithm graph theory EECS2001:

EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
[email protected]
Office: Lassonde 2015 Course page: Moodle
Notes based on work by Professor Suprakash Datta
7/17/2019 EECS2001, Summer 2019 1

Chapter 4: Decidability
We are now ready to tackle the question:
What can computers do and what not?
We do this by considering the question:
Which languages are TM-decidable, Turing- recognizable, or neither?
Assuming the Church-Turing thesis, these are
fundamental properties of the languages.
7/17/2019 EECS2001, Summer 2019 2

Describing TM Programs
Three Levels of Describing algorithms:
• formal (state diagrams, CFGs, et cetera) • implementation (pseudo-Pascal)
• high-level (coherent and clear English)
Describing input/output format:
TMs allow only strings * as input/output.
If our X and Y are of another form (graph, Turing machine, polynomial), then we use X,Y to denote ‘some kind of encoding *’.
7/17/2019 EECS2001, Summer 2019 3

Deciding Regular Languages
The acceptance problem for deterministic finite automata is defined by:
ADFA = { B,w | B is a DFA that accepts w } Note that this language deals with all possible
DFAs and inputs w, not a specific instance. Of course, ADFA is a TM-decidable language.
7/17/2019 EECS2001, Summer 2019 4

ADFA is Decidable (Thm. 4.1)
Proof: Let the input B,w be a DFA with B=(Q, , , qstart, F) and w*.
The TM performs the following steps:
1) Check if B and w are ‘proper’, if not: “reject” 2) Simulate B on w with the help of two pointers:
Pq  Q for the internal state of the DFA, and Pw  {0,1,…,|w|} for the position on the string. While we increase Pw from 0 to |w|, we change Pq according to the input letter wPw and the transition function value (Pq,wPw).
3) If M accepts w: “accept”; otherwise “reject”
7/17/2019 EECS2001, Summer 2019 5

Deciding NFA
The acceptance problem for nondeterministic FA ANFA = { B,w | B is an NFA that accepts w }
is a TM decidable language.
Proof: Let the input B,w be an NFA with
B=(Q, , , qstart, F) and w*.
Use our earlier results on finite automata
to transform the NFA B into an equivalent DFA C. (See Theorem 1.19 how to do this automatically.) Use the TM of the previous result on C,w.
This can all be done with one big, combined TM.
7/17/2019 EECS2001, Summer 2019 6

Regular Expressions
The acceptance problem
AREX = { R,w | R is a regular expression
that can generate w } is a Turing-decidable language.
Proof Theorem 4.3. On input R,w:
1. Check if R is a proper regular expression
and w a proper string
2. Convert R into a DFA B
3. Run earlier TM for ADFA on B,w
7/17/2019 EECS2001, Summer 2019 7

Emptiness Testing (Thm. 4.4)
Another problem relating to DFAs is the emptiness problem:
EDFA = {A | A is a DFA with L(A) =  }
How can we decide this language? This language concerns the behavior of the DFA A on all possible strings.
Less obvious than the previous examples. Idea: check if an accept state of A is reachable from the start state of A.
7/17/2019 EECS2001, Summer 2019 8

Proof for DFA-Emptiness
Algorithm for EDFA on input A=(Q,,,qstart,F): 1) If A is not proper DFA: “reject”
2) Mark the start state of A qstart
3) Repeat until no new states are marked:
a) Mark any states that can be -reached from any marked state that is already marked
4) If no accept state is marked, “accept”; else “reject”
7/17/2019 EECS2001, Summer 2019 9

DFA-Equivalence (Thm. 4.5)
A problem that deals with two DFAs: EQDFA = {A,B | L(A) = L(B) }
Theorem 4.5: EQDFA is TM-decidable.
Proof: Look at the symmetric difference between
the two languages:
Note: “L(A)=L(B)” is equivalent with an empty symmetric difference between L(A) and L(B). This difference is expressed by standard DFA transformations: union, intersection, complement.
(L(A)  L(B))  (L(A)  L(B))
7/17/2019 EECS2001, Summer 2019 10

Proof of Theorem 4.5 (cont.)
Algorithm on given A,B:
1) If A or B are not proper DFA: “reject”
2) Construct a third DFA C that accepts the
language
(with standard ‘Chapter 1’ transformations).
(L(A)  L(B))  (L(A)  L(B))
3) Decide with the TM of the previous theorem
whether or not CEDFA
4) If CEDFA then “accept”;
If CEDFA then “reject”
7/17/2019 EECS2001, Summer 2019 11

Context-Free language problems
Similar languages for context-free grammars: ACFG = { G,w | G is a CFG that generates w }
ECFG = { G | G is a CFG with L(G)= } EQCFG = { G,H | G and H are CFGs with
L(G)=L(H) }
The problem with CFGs and PDAs is that they are inherently non-deterministic.
7/17/2019 EECS2001, Summer 2019 12

Recall “Chomsky NF”
A context-free grammar G = (V,,R,S) is in Chomsky normal form if every rule is of the form
A → BC or A → x
with variables AV and B,CV {S}, and x For the start variable S we also allow “S → ”
Chomsky NF grammars are easier to analyze. The derivation S * w requires 2|w|–1 steps
(apart from S  ).
7/17/2019 EECS2001, Summer 2019 13

Deciding CFGs (1)
Theorem 4.6: The language
ACFG = { G,w | G is a CFG that generates w }
is TM-decidable.
Proof: Perform the following algorithm:
1) Check if G and w are proper, if not “reject”
2) Rewrite G to G’ in Chomsky normal form
3) Take care of w= case via S→ check for G’
4) List all G’ derivations of length 2|w|–1
5) Check if w occurs in this list;
if so “accept”; if not “reject”
7/17/2019 EECS2001, Summer 2019 14

Deciding CFGs (2)
Theorem 4.7: The language
ECFG = { G | G is a CFG with L(G)= }
is TM-decidable.
Proof: Perform the following algorithm: 1) Check if G is proper, if not “reject” 2) Let G=(V,,R,S), define set T=
3) Repeat |V| times:
• Check all rules B→X1…Xk in R
• If BT and X1…XkTk then add B to T 4) If ST then “reject”, otherwise “accept”
7/17/2019 EECS2001, Summer 2019 15

Equality of CFGs
What about the equality language
EQCFG = { G,H | G and H are CFGs with L(G)=L(H) }?
For DFAs we could use the emptiness decision procedure to solve the equality problem.
For CFGs this is not possible… (why?) … because CFGs are not closed under complementation or intersection.
Later we will see that EQCFG is not TM-decidable.
7/17/2019 EECS2001, Summer 2019 16

Deciding Languages
We now know that the languages:
ADFA = { B,w | B is a DFA that accepts w }
ACFG = { G,w | G is a CFG that generates w } are TM decidable.
What about the obvious next candidate
A = {M,w | M is a TM that accepts w }? TM
Is one TM capable of simulating all other TMs?
7/17/2019 EECS2001, Summer 2019 17

Does there exist a Universal TM?
Given a description M,w of a TM M and input w, can we simulate M on w?
We can do so via a universal TM U (2-tape): 1) Check if M is a proper TM
Let M = (Q,,,,q0,qaccept,qreject)
2) Write down the starting configuration
 q0w  on the second tape
3) Repeat until halting configuration is reached:
• Replace configuration on tape 2 by next configuration according to 
4) “Accept” if qaccept is reached; “reject” if qreject
7/17/2019 EECS2001, Summer 2019 18

Next
Towards undecidability:
• The Halting Problem
• Countable and uncountable infinities • Diagonalization arguments
7/17/2019 EECS2001, Summer 2019 19