Lecture Notes - Week 3 PDF

Chapter 6 Non-regular Languages Limitations of finite automata. 1. Not all languages are regular. 2. Intuitively languages that “require” some sort of counting are generally not regular. 6.1 The Pumping Lemma Theorem 8 (Pumping Lemma). Let L be a regular language. There exists an integer...

Chapter 6 Non-regular Languages Limitations of finite automata. 1. Not all languages are regular. 2. Intuitively languages that “require” some sort of counting are generally not regular. 6.1 The Pumping Lemma Theorem 8 (Pumping Lemma). Let L be a regular language. There exists an integer p ≥ 0, such that for all w ∈ L of length at least p, there exists a partition of w = xyz such that |xy| ≤ p, |y| > 0, and for all i ≥ 0, xy i z ∈ L. Informally pumping lemma says that if L is a regular language then all strings in L having length greater than some quantity, has a non-null substring that can be repeated as many times as you want and the resultant string is still in the language. Note 4. Pumping lemma is a property of regular languages. In other words if a language is regular then it satisfies the above property. It may very well be true that certain non-regular languages also satisfy the above property. To prove that certain languages are not regular, we will use the pumping lemma in the contrapositive form. Theorem 9 (Contrapositive form of Pumping Lemma). Let L be a language. If - ∀p ≥ 0, (opponent’s move) - ∃w ∈ L with |w| ≥ p, such that, (your move) - ∀ possible partitions of w as w = xyz, satisfying (opponent’s move) - |xy| ≤ p, and - |y| > 0, - ∃i ≥ 0 such that xy i z ∈ / L, (your move) then L is not regular. 39 Think of it as a game between you and an all powerful opponent. Both you and your opponent have to follow the rules of the game (the conditions of the theorem). Your goal is to finally find an i such that xy i z is not in L and your opponents goal is to choose the partition of w in such a manner that no matter what i you choose, xy i z will be in L. Pumping lemma gives a sufficient condition for non-regular languages. It is not a necessary condition. In other words, there exists non-regular languages that do not satisfy the pumping lemma. Therefore, You WIN =⇒ L is not regular, but You LOSE 6 =⇒ L is regular 6.2 Examples of Non-regular Languages 1. L1 = {0n 1n | n ≥ 0} Given p ≥ 0, pick w = 0n 1n. Now for any partition of w = xyz such that |xy| ≤ p and |y| > 0, it must be the case that y = 0t for some t > 0. Therefore xy 0 z = 0p−t 1p ∈ / L1 since t > 0. Therefore L1 is not regular. 2. L2 = {al bm cn | l, m, n ≥ 0 and l + m = n} Given p ≥ 0, pick w = ap bp c2p. Now for any partition of w = xyz such that |xy| ≤ p and |y| > 0, it must be the case that y = at for some t > 0. Therefore xy 2 z = ap+t bp c2 p ∈ / L2 since t > 0. Therefore L2 is not regular. 3. L3 = {w ∈ {0, 1}∗ | #0 (w) = #1 (w)} Note that L3 ∩ L(0∗ 1∗ ) = L1. Since we have shown that L1 is not regular therefore it must be the case that L3 is also not regular. Remark. Intersection of a non-regular language with a regular/non-regular language can be both regular or non-regular. Same is true for union as well. Verify for yourself by constructing toy examples. 4. L4 = {0k | k is a prime} Given p ≥ 0, pick w = 0q , where q is the smallest prime greater than or equal to p. Now for any partition of w = xyz such that |xy| ≤ p and |y| > 0, let |y| = l. Then 0 < l ≤ p. Choose i = q + 1. Then, |xy i z| = q + l(i − 1) = q + lq = q(l + 1). Hence xy i z ∈ / L4. Therefore L4 is not regular. Exercise 9. Show that the following languages are not regular. 1. 2 {0n 1n | n ≥ 0} 2. {0n 1m | n > m}  3. {ww | w ∈ {0, 1}∗ } Proof of Theorem 8. Let D = (Q, Σ, δ, q0 , F ) be a DFA for L. Let p = |Q|. Let w be a string of length at least p in L and |w| = t. There is a sequence of states q0 , q1 ,... qt that the DFA traverses on the string w where qt ∈ F. By pigeon hole principle, there exists integers i, j such that 0 ≤ m < n ≤ qp and qm = qn. Now consider a partition w = xyz, such that - x is the smallest string having the property that δ(q0 , x) = qm , - y is the smallest non-empty string such that δ(qm , y) = qm , and - z is the remaining part of w. In other words, the DFA traverses from q0 to qm on x, traverses from qm to qn (qn is the same as qm ) on y and then proceeds to qt. Since m < n therefore |y| > 0. Now for all i ≥ 0, δ(q0 , xy i ) = qm , as the automaton loops on the state qm on the string y. Therefore δ(q0 , xy i z) = qt and hence xy i z ∈ L. Note 5. Observe that in the above proof we are “overloading” the definition of δ to accommodate strings as well instead of symbols only. We can formalize this by defining δ recursively as follows: δ : Q × Σ∗ −→ Q such that δ(q, ) = q, δ(q, xa) = δ(δ(q, x), a). Chapter 7 DFA Minimization Given a DFA D = (Q, Σ, δ, q0 , F ) we define a equivalence relation on the states of the DFA. For any two states p, q ∈ Q, we say that p ≈ p if for all string x ∈ Σ∗ , (δ(p, x) ∈ F ⇐⇒ δ(q, x) ∈ F ). Exercise 10. Verify that ≈ is an equivalence relation. Let [p] = {q | q ≈ p} be the equivalence class of all states equivalent to p. We define a quotient DFA D≈ based on the DFA D as D≈ = (Q0 , Σ, δ 0 , q00 , F 0 ), where, Q0 = {[p] | p ∈ Q} (i.e. the set of equivalence classes) 0 δ ([p], a) = [δ(p, a)] q00 = [q0 ] F 0 = {[f ] | f ∈ F } Exercise 11. Show that the definition of δ 0 is well defined. In other words, if [p] = [q], then [δ(p, a)] = [δ(q, a)] for all a ∈ Σ. We will now show that D≈ and D accept the same language. Lemma 10. For all x ∈ Σ∗ , δ 0 ([p], x) = [δ(p, x)]. Proof. We will use induction on |x|. Base Case If x = , then δ 0 ([p], ) = [p] = [δ(p, )]. Induction Step Let x = ya and assume that δ 0 ([p], y) = [δ(p, y)]. Now δ 0 ([p], ya) = δ 0 (δ 0 ([p], y), a) = δ 0 ([δ(p, y)], a) = [δ(δ(p, y), a)] = [δ(p, ya)]. 43 Theorem 11. L(D≈ ) = L(D). Proof. For all x ∈ Σ∗ , δ 0 (s0 , x) ∈ F 0 ⇐⇒ δ 0 ([s], x) ∈ F 0 ⇐⇒ [δ(s, x)] ∈ F 0 (by Lemma 10) ⇐⇒ δ(s, x) ∈ F. Exercise 12. Can you collapse the quotient DFA any further? What happens if you try to do so? 7.1 DFA Minimization Algorithm Remark. A state is said to be unreachable if on no input the DFA ever traverses that state. Let D = (Q, Σ, δ, q0 , F ) be a DFA that does not have any unreachable states. The algorithm to minimize the DFA is as follows: 1. Create a table of pairs {p, q}, where p, q ∈ Q. All entries of the table are initially unmarked. 2. Mark the pair {p, q} if p ∈ F and q ∈ / F , or vice versa. 3. Repeat the following until you make an entire pass of the table and no new pair gets marked: - If {p, q} is unmarked and there exists a symbol a ∈ Σ such that {δ(p, a), δ(q, a)} is marked, then mark pair {p, q}. 4. After completion, p ≈ q if and only if {p, q} is not marked. 7.1.1 An Example Consider the following DFA a 2 4 a a, b b start 1 6 a, b b a, b b a 3 5 We want to minimize the above DFA. We first create a table of pairs. 1 × 2 × 3 After Step 2 × × 4 × × 5 × × × 6 1 × 2 × 3 After 1st iteration of Step 3 × × 4 × × 5 × × × × × 6 1 × 2 × 3 After 2nd iteration of Step 3 × × × 4 × × × 5 × × × × × 6 No more pairs can get marked any further. Hence the algorithm terminates. From the final table we have that 2 ≈ 3 and 4 ≈ 5. Hence the minimized DFA will have the following form. a, b a, b a, b start a, b Exercise 13. Minimize the following DFA. b a 6 3 b a a b start 1 b 2 a 5 b b a a a b b 4 8 7 a