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
5/27/2019 EECS2001, Summer 2019 1
Non-regular Languages §1.4
Which languages cannot be recognized by finite automata?
Example: L={ 0n1n | nN }
• ‘Playing around’ with FA convinces you that the
‘finiteness’ of FA is problematic for “all nN”
• The problem occurs between the 0n and the 1n
• Informal: the memory of a FA is limited by the the number of states |Q|
5/27/2019 EECS2001, Summer 2019 2
Proving non-regularity
• Prove a general statement — NO DFA exists for a given problem.
• Cannot assume an automaton structure or a specific strategy
• Need an argument that holds for ALL DFA’s
5/27/2019 EECS2001, Summer 2019 3
Repeating DFA Paths
Consider an accepting DFA M with size |Q|
On a string of length p, p+1 states get visited For p|Q|, there must be a j such that the computational path looks like: q1,…,qj,…,qj,…,qk
qj q1
qk
5/27/2019
EECS2001, Summer 2019 4
Repeating DFA Paths
The action of the DFA in qj is always the same. If we repeat (or ignore) the qj,…,qj part, the new path will again be an accepting path
qj q1
qk
5/27/2019
EECS2001, Summer 2019 5
Line of Reasoning
Proof by contradiction:
• Assume that L is regular
• Hence, there is a DFA M that recognizes L • For strings of length |Q| the DFA M has
to ‘repeat itself’
• Show that M will accept strings outside L • Conclude that the assumption was wrong
Note that we use the simple DFA, not the more elaborate (but equivalent) NFA or GNFA
5/27/2019 EECS2001, Summer 2019 6
Pumping Lemma (Thm 1.37)
For every regular language L, there is a pumping length p, such that for any string sL and |s|p, we can write s=xyz with
1) x yi z L for every i{0,1,2,…} 2) |y| 1
3) |xy| p
Note that 1) implies that xz L
2) says that y cannot be the empty string Condition 3) is not always used
5/27/2019 EECS2001, Summer 2019 7
Formal Proof of Pumping Lemma
Let M = (Q,,,q1,F) with Q = {q1,…,qp} Let s = s1…snL(M) with |s| = n p Computational path of M on s is the sequence r1,…,rn+1 Qn+1 with
r1 = q1, rn+1F and rt+1= (rt,st) for 1tn Because n+1 p+1, there are two states
such that rj = rk (with j