EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
amahmoodi@cse.yorku.ca
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 CEDFA
4) If CEDFA then “accept”;
If CEDFA 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 AV and B,CV \{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 BT and X1…XkTk then add B to T 4) If ST 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