Properties of Regular Languages
Alexander Meduna · Auerbach Publications eBooks · 2014
Given a language and a language family, perhaps the most fundamental problem consists in determining whether or not the language belongs to the family� This chapter discusses this problem in terms of the family of regular languages, regΦ (see Definition 3�23)� That is, it establishes several properties of regular languages that are helpful to prove or disprove that a language is in regΦ� First, Section 5�1 establishes a lemma, customarily referred to as the pumping lemma for regular languages, which represents a crucially important tool for demonstrating that certain languages are out of regΦ� Then, Section 5�2 establishes basic closure properties concerning regΦ� Roughly speaking, it demonstrates that regΦ is closed under most common language operations, including the operations defined in Section 2�1� It shows how to combine closure properties together with the pumping lemma to disprove that some languages are regular� On the other hand, it also demonstrates how to use closure properties to prove that some languages are regular� 5.1 Pumping Lemma for Regular Languages To give an insight into this important lemma, consider any L ∈ regΦ and any deterministic finite automaton (DFA), M = (Σ, R ), satisfying L(M) = L� Set k = card(Q)� Suppose that z ∈ L(M) with |z| ≥ k� As M reads a symbol during every move, M accepts z by making a sequence of |z| moves; therefore, there necessarily exists at least one state that M visits two or more times when accepting z� Take the first two visits of the same state, q, in this sequence of moves and decompose z according to them as follows� Set z = uvw so that u, v, and w satisfy the following properties: 1� u takes M from the start state to the first visit of q� 2� v takes M from the first visit of q to the second visit of q� 3� Apart from the two visits of q in properties 1 and 2, M never visits any state twice on uv� 4� w takes M from the second visit of q to a final state f� 74 As M is deterministic and, therefore, makes no ε-moves, 0 < |v|� By properties 1 through 3, |uv| ≤ k� Most importantly, M can obviously iterate the sequence of moves between the two visits of q described in properties 1 and 2 m times, for any m ≥ 0, and during each of these iteration, M reads v� Consequently, M accepts every string of the form uvmw� Next, we state and prove this lemma rigorously� Lemma 5.1 Pumping lemma for regular languages� Let L ∈ regΦ� Then, there exists a positive integer k ∈ ℕ such that every string z ∈ L satisfying |z| ≥ k can be expressed as z = uvw, where 0 < |v| ≤ |uv| ≤ k, and uvmw ∈ L, for all m ≥ 0� Proof� Let L ∈ regΦ� Let L be finite� Set k to any positive integer satisfying |z| < k, for all z ∈ L, so the lemma trivially holds simply because L contains no string whose length is greater than or equal to k� Therefore, suppose that L is infinite� Let M = (Σ, R) be a DFA such that L(M) = L� Set k = card(Q)� Consider any string z ∈ L with |z| ≥ k� As z ∈ L, sz ⇒* f [ρ], where s is the start state of M, f ∈ F, and ρ ∈ R * is a sequence of rules from R� Because M makes no ε-moves and, thus, reads a symbol on every step, |ρ| = |z|� As |z| ≥ k and k = card(Q), |ρ| ≥ card(Q)� Therefore, during sz ⇒* f [ρ], M enters some states more than once� Consider the shortest initial part of this sequence of moves during which M visits the same state, q ∈ Q� More formally, express sz ⇒* f [ρ] as suvw ⇒* qvw [σ] ⇒+ qw [τ] ⇒* f [υ] where ρ = στυ, q ∈ Q, |τ| ≥ 1, and during suvw ⇒* qw, M visits q precisely twice and any other state no more than once� Claims A and B verify that uvw satisfies the conditions stated in the lemma� Claim A� 0 < |v| and |uv| ≤ k� Proof of Claim A� As |v| = |τ| and |τ| ≥ 1, 0 < |v|� Because during suvw ⇒* qw [στ], M visits q twice and any other state no more than once, |στ| ≤ card(Q)� As |uv| = |στ| and card(Q) = k, |uv| ≤ k� Thus, |uv| ≤ k� Claim B� For all m ≥ 0, uvmw ∈ L� Proof of Claim B� Let m ≥ 0� M accepts uvmw by repeating the sequence of moves according to τ m times; formally, suvmw ⇒* qvmw [σ] ⇒* qw [τm] ⇒* f [υ] Thus, for all m ≥ 0, uvmw ∈ L; notice that for m = 0, M actually accepts uw so it completely omits the sequence of moves made according to τ and, therefore, computes suw ⇒* qw [σ] ⇒* f [υ] ◾ Example 5.1 To illustrate the technique used in the previous proof, take this regular language L = {a}{bc}*{b} Consider the DFA M defined by the following three rules: 1: sa → p, 2: pb → f, 3: fc → p where s is the start state of M and f ∈ F� As obvious, L(M) = L� Since M has three states, set k = 3� Consider z = abcb ∈ L� As |z| = 4 and k = 3, z satisfies |z| ≥ k� M accepts z as sabcb ⇒* f [1232], which can be expressed in a move-by-move way as follows: sabcb ⇒ pbcb [1] ⇒ fcb [2] ⇒ pb [3] ⇒ f [2] The shortest initial part of this computation that contains two occurrences of the same state is sabcb ⇒ pbcb [1] ⇒ fcb [2] ⇒ pb [3] where p is the state M visits twice� Following the above proof, we express sabcb ⇒* f [1232] as suvw ⇒* qvw [1] ⇒* qw [23] ⇒* f [2] with u = a, v = bc, and w = b� Observe that 0 < |v| = 2 and |uv| = 3 ≤ k = 3� As a(bc)mb = u(v)m w ∈ L, for all m ≥ 0, all the conditions stated in Lemma 5�1 hold� Specifically, take m = 2 to obtain a(bc)mb = a(bc)2b = abcbcb� M accepts abcbcb by iterating the partial computation according to 23 twice as follows: sabcbcb ⇒* pbcbcb [1] ⇒* pbcb [23] ⇒* pb [23] ⇒* f [2] 5.1.1 Applications of the Pumping Lemma for Regular Languages As already pointed out, we primarily apply Lemma 5�1 to prove that a given language L is out of regΦ� Of course, a proof like this is made by contradiction, and its typical structure follows: 1� Assume that L ∈ regΦ� Consider the constant k from the pumping lemma, and select a string z ∈ L whose length depends on k so |z| ≥ k is surely true� 2� Consider all possible decompositions of z into uvw satisfying |uv| ≤ k and v ≠ ε, and for each of these decompositions, demonstrate that there exists m ≥ 0 such that uvmw ∉ L, which contradicts the third condition in Lemma 5�1� 3� The contradiction obtained in (2) implies that the assumption in (1) was incorrect, so L ∉ regΦ� 76 Example 5.2 Let L = {x| x ∈ {0, 1}*, occur(x, 0) = occur(x, 1)}� In other words, L is the language consisting of strings containing the same number of 0s and 1s� Following the proof scheme earlier almost literally, we easily demonstrate that L ∉ regΦ� 1� Assume that L ∈ regΦ� 2� As L ∈ regΦ, there exists a natural number k satisfying Lemma 5�1� Set z = 0k1k� Notice that z ∈ L� Notice that |z| ≥ k because |z| = 2k ≥ k� 3� By Lemma 5�1, z can be expressed as z = uvw so the conditions of the pumping lemma hold� As 0 < |v| and |uv| ≤ k, v ∈ {0}+� Consider uv0w = uw� Then, uw = 0 j1k with j = k − |v|; therefore, uw ∉ L� However, by the pumping lemma, uvmw ∈ L, for all m ≥ 0, including the case when m = 0, so uw ∈ L-a contradiction� 4� By the contradiction in (3), L ∉ regΦ� Example 5�2 followed the recommended four-step proof idea, consisting of (1) through (4), almost literally� Example 5�3 makes use of the pumping lemma in a more original and ingenious way� Example 5.3 Clearly, {a}+ ∈ regΦ� Consider its sublanguage P ⊆ {a}+ defined as P = {an| n is prime} (a positive integer n is prime if its only positive divisors are 1 and n)� As demonstrated next, P ∉ regΦ� Thus, from a more general viewpoint, we see that a sublanguage of a regular language may be nonregular� Assume that P is regular� Then, there exists a positive integer k satisfying the pumping lemma� As P is infinite, there surely exists a string z ∈ P such that |z| ≥ k� By Lemma 5�1, z can be written as z = uvw, so the conditions of the pumping lemma hold� Consider uvmw with m = |uw| + 2|v| + 2� As |uvmw| = |uw| + m|v| = |uw| + (|uw| + 2|v| + 2)|v| = (|uw| + 2|v|) + (|uw| + 2|v|)|v| = (|uw| + 2|v|)(1 + |v|), |uvmw| is no prime and, thus, uvmw ∉ P� By the pumping lemma, however, uvmw ∈ P-a contradiction� Thus, P ∉ regΦ� Observe that this result has its significant practical consequences� Indeed, as P is nonregular, no FA accepts P (see Theorem 3�38)� Consequently, informally speaking, the FAs are not strong enough to handle the primes� Lemma 5�1 is a powerful tool to disprove that certain languages are in regΦ, but it cannot be applied in the positive sense� That is, it cannot be used to prove that certain languages are regular because some nonregular languages satisfy the pumping-lemma conditions as Example 5�4 illustrates� Consequently, proving that a language satisfies these conditions does not necessarily imply that the language is regular� Example 5.4 Take L = {aobncn| o ≥ 1 and n ≥ 0} ∪ {bocn| o, n ≥ 0} Observe that L satisfies the conditions of the pumping lemma for regular languages although L ∉ regΦ� To see that L satisfies the pumping lemma conditions, set k = 1� Consider any string z ∈ L and |z| = k� As z ∈ L, either z ∈ {aobncn| o ≥ 1 and n ≥ 0} or z ∈ {bocn| o, n ≥ 0}� 1� Let z = aobncn, for some o ≥ 1 and n ≥ 0� Express z as z = uvw with u = ε, v = a, and w = ao−1bncn� Clearly, v ≠ ε and |uv| = k = 1� Furthermore, notice that ambncn ∈ L, for all m ≥ 1, so uvmw ∈ L, for all m ≥ 0� Thus, the pumping lemma conditions are satisfied in this case� 2� Let z = bocn, for some o, n ≥ 0� Express z as z = uvw with u = ε, v is the leftmost symbol of bocn, and w is the remaining suffix of z� For o = 0, v = c and w = cn−1, and all the three conditions hold� For o ≥ 1, v = b and w = bo−1cn, and all the three conditions hold in this case as well� ◾ Thus, L satisfies the conditions of the pumping lemma for regular languages� Finally, prove that L ∉ regΦ by contradiction� That is, assume that L ∈ regΦ� Let M = (Σ, R) be a DFA such that L(M) = L� As an exercise, show how to transform M to an FA N such that L(N ) = {abncn| n ≥ 0}, and by analogy with Example 5�2, prove that {abncn| n ≥ 0} ∉ regΦ� From this contradiction, it follows that L ∉ regΦ� 5.2 Closure Properties Based on the general concept of closure properties sketched in Section 2�2�2, we see that regΦ is closed under a language operation o if regΦ contains every language that results from o applied to any regular languages; equivalently, we say that o preserves regΦ� Closure results concerning regΦ are obviously useful to prove that some languages are regular� Indeed, to prove that a relatively complicated language K belongs to regΦ, we construct K from simpler regular languages by operations that preserve regΦ, so K has to be in regΦ� However, combined with the pumping lemma, the closure properties of regular languages are often very helpful in proofs that a language L is nonregular� Indeed, assuming that L is regular, we first transform this language to a simpler language K by using some operations under which regΦ is closed� Then, by using the pumping lemma, we prove that K is nonregular, so we conclude L is not regular either� In this section, we prove that regΦ is closed under most common theoretical language operations, such as union, concatenation, closure, complement, intersection, regular substitution, finite substitution, and homomorphism� In fact, we demonstrate most of these closure properties effectively in terms of FAs� In other words, when proving that a given operation o preserves the family of regular languages, we actually present an algorithm that converts any FAs to another FA that accepts the language resulting from o applied to the languages accepted by the input automata� Union, concatenation, and closure� We have already demonstrated that the family of regular languages is closed under union, concatenation, and closure (see Algorithms 2�19, 2�21, and 2�23, and Theorem 5�2)� Theorem 5.2 regΦ is closed under union, concatenation, and closure� Complement and Intersection� To prove that regΦ is closed under complement, we explain how to turn any csDFA I to a csDFA O such that L(O) = ~L(I )� Theorem 5.3 Let I be a csDFA� Then, there exists a csDFA O such that L(O) = ~L(I)� Consequently, regΦ is closed under complement� Proof� Let L ∈ regΦ� Without any loss of generality, suppose that L = L(I), where I is a completely specified DFA (csDFA) (see Definition 3�17 and Theorem 3�18)� From I, construct a csDFA O by making every nonfinal state final and vice versa� As I is completely specified, so is O� Thus, O completely reads every input string over Δ� Consequently, O accepts a string iff I rejects it, so L(O) = Δ* − L(I)� As ~L = ~L(I) = Δ* − L(I), L(O) = ~L� Hence, regΦ is closed under complement� 78 Theorem 5.4 regΦ is closed under intersection� Proof� Let K, L ∈ regΦ� By (see Section ∪ = K L, so Theorem 5�4 follows from 5�2 and Regular As a case of (see Section we the regular and prove that regΦ is closed under This important closure represents a powerful theoretical tool for proving several other closure properties as demonstrated in this proving this important closure that in an a state is a state from which there exists no (see Definition Consequently, no FA can any of its Lemma that any loss of generality, we can assume that an FA has precisely one final state, which is also a Notice that the proof of Lemma no Consequently, and any loss of generality, we can assume that any regular language is accepted by an FA with a final state, which is also a We use of this result in the proof that regΦ is closed under regular Definition Let and be two and be a from * to * such that for all a ∈ ∈ regΦ� Then, is a regular We to prove that regΦ is closed under regular (see Theorem in the following way� First, we consider any regular and any K ∈ regΦ� Without any loss of generality, we assume that K is accepted by an FA I such that = f where I f is a To demonstrate that regΦ is closed under the regular substitution, we explain how to and I to an FA O such that L(O) = = ), which establishes the closure that this we its basic Let K, and I have the above More be a regular such that for every a ∈ = where is an We construct an FA O satisfying ∈ iff ∈ L(O) for every ∈ so L(O) = = )� In a greater I has a final state, I f, which is also a O as follows� First, O O enters a final state of and, accepts O to and so all n through in this O has with ∈ As ∈ L(I), takes O to its only final state, so at this O accepts that the following algorithm that the state of I, are This is obviously any loss of if two some states in we states in either of them to obtain two FA for Regular I = such that = f and I f is a state, and a set of FAs = is an a ∈ such that I and all the in have of FA O such that ∈ L(O) iff ∈ ), where ∈ ), ∈ ∈ ∈ ), 1 ≤ ≤ for some n ∈ = 0 = = ◾ set = ∪ q ∈ o ∈ with ∈ a ∈ set = set = f set = a ∈ with ∈ set = → q ∈ ∈ for some a ∈ ∪ → q ∈ pb → o ∈ with b ∈ ∪ ∈ for some a ∈ ∪ → q, p ∈ → p ∈ with a ∈ f ∈ with ∈ Lemma is Proof� Let I and have the same as in We to demonstrate that an FA O such that ∈ L(O) iff ∈ where ∈ L(I), ∈ ∈ ∈ 1 ≤ ≤ where n ∈ We with the following important Let q ∈ ∈ ∈ 1 ≤ ≤ where n ∈ Then, ⇒* q in I iff ⇒* q in O with ∈ where ∈ By on n ≥ 0, we prove that for every q ∈ ∈ ∈ 1 ≤ ≤ ⇒* q in I implies ⇒* q in O with ∈ where ∈ Assume that the part of the holds for all strings of length k, 1 ≤ k ≤ for some n ∈ Let q ∈ ∈ ∈ 1 ≤ ≤ n + 1, and ⇒* q in As I is express ⇒* q as ⇒* ⇒ q → in I, where → q ∈ with p ∈ Thus, ⇒* p in By the ⇒* p in O with ∈ ∈ 1 ≤ ≤ For every ∈ ⇒* in where is the start state of and is a final state in this p → and → q to Furthermore, the algorithm the rules of into as so ⇒* in O� Thus, ⇒ → ⇒* ⇒ q → in O� Consequently, ⇒* ⇒* ⇒ q in O with ∈ 1 ≤ ≤ n + 1, so the is Thus, the part of the proof A proof of this part of the is as an the above for q = I f, we see that for every ∈ ∈ 1 ≤ ≤ where n ∈ f in I iff f in O with ∈ where ∈ that = f Therefore, ∈ iff ∈ so the lemma Theorem regΦ is closed under regular Proof� Let K ∈ regΦ� Then, there exists an FA I such that K = with = ) (see Theorem 3�38)� Without any loss of generality, assume that I satisfies the properties stated in is, I = represents an such that = f and I f is a Let be a regular from to That is, for every a ∈ ), is regular, so there exists an FA such that = Set = is an a ∈ By and Lemma there exists an FA O satisfying ∈ L(O) iff ∈ where ∈ L(I), ∈ ∈ ∈ 1 ≤ ≤ where n ∈ already n = 0 = = Thus, L(O) = = )� Because O is an ) ∈ regΦ (see Theorem 3�38)� Theorem is a powerful result significant as Definition Let and be two and be a from * and * such that for all a ∈ is a finite Then, is a finite Notice that every finite and every (see Section are of regular Thus, Theorem implies the regΦ is closed under finite and homomorphism� Applications of Closure Properties As already pointed out, together with the pumping lemma for regular languages, the closure properties are used to prove that a language L is not regular� a proof of this is made by contradiction in the following way� 1� Assume that L ∈ regΦ� 2� By using operations regΦ, construct a language K from L, so K ∈ this so that the following proof in is as as 3� By the pumping lemma, prove that K ∉ regΦ, which contradicts K ∈ regΦ as stated in 4� The contradiction obtained in implies L ∉ regΦ� ◾ Example Let L = {x| x ∈ {0, 1}*, occur(x, 0) ≠ occur(x, 1)}� Next, we prove that this language is nonregular� 1� Assume that L ∈ regΦ� 2� Consider which is obviously in regΦ� Consider K = ~L = n ≥ 0}� By 5�3 and K ∈ regΦ� 3� By analogy with Example prove that K ∉ regΦ, which contradicts K ∈ regΦ� 4� obtained the contradiction in (3), we conclude that L ∉ regΦ� the pumping lemma is of no use in proving that a language is in regΦ (see Example closure properties are useful in this positive sense� Indeed, suppose a proof that a language L is regular a of an complicated followed by a proof that this automaton accepts L� we can this proof so we L by several regular languages combined by operations under which the family of regular languages is closed and, therefore, conclude that L is in regΦ� Example Consider L = k ≥ 0 and ≥ To verify that L ∈ regΦ, express this language as L = where is a regular defined as = and = As and are obviously regular, L = is also regular by 5�2 and 1 Example 5�3 demonstrates that {an| n is a prime} is not regular� an proof of this result by using the pumping lemma for regular languages (see Lemma 2� Consider each of the following languages� By the pumping lemma for regular languages, demonstrate that the language is not regular� ≥ b� 1 ≤ ≤ k ≥ 0 and = k + j ≥ 0 and ≤ j ≤ f� k ≥ 0, ≠ k ≠ and j ≠ j ≥ 0 and j ≤ ≥ 0} 3� the following of the pumping lemma for regular languages� Lemma Let L be a regular Then, there is a natural k, such that if ∈ L and |z| = k, z can be written as z = uvw, where |v| ≥ 1 and ∈ L, for all m ≥ 0� this lemma to prove that j ≥ is not regular� 4� Consider the following languages� the closure properties of the regular languages and the regular pumping lemma to demonstrate that these languages are not regular� w ∈ and = b� ≥ w ∈ and v = a set of languages from regΦ such that each of them contains that are not in regΦ� For each L, in this a nonregular K, such that K ⊆ L and prove that K is not regular by the pumping lemma For take L defined as L = and consider K = n ≥ 0}� Clearly, K ⊆ L and L ∈ regΦ� By Lemma 5�1, it is to prove that K ∉ regΦ� the pumping lemma for regular languages in terms of than FAs� Example a proof of Lemma that a L, over an is regular iff there exists a natural k, satisfying this if z ∈ and |z| ≥ k, (1) z = uvw with v ≠ ε and (2) ∈ L if and only if ∈ L, for all m ≥ 0 and x ∈ how to use this lemma to prove that a language is regular� Then, explain how to use this lemma to prove that a language is not regular� Assume that L is a regular language over an it necessarily that ~L is also regular under this and this in terms of and L Theorem 5�2 in terms of regular Let L be a regular language over an the language For each of these operations, prove or disprove that the family of regular languages is closed under the = w ∈ L and − L = b� = w ∈ L and L = = {x| ∈ L for some ∈ and = = {x| ∈ L for some ∈ and = = ∈ L for some v, w ∈ f� = ∈ L for some v ∈ and = = ∈ L for some z ∈ z = For a language L over an and a symbol a ∈ the language obtained by all occurrences of a from the strings of L� this regΦ closed under