Ch.5: Pumping Lemma

Week 5 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 5.1. Intuitive Idea Behind the Lemma 5.2. The Pumping Lemma 5.3. Applications

49 flashcards · Computer Science · by lakesare

Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses

  1. [Intuitive Idea Behind the Lemma] Which three objects can show that a language is regular?

    DFA A deterministic finite automaton that recognizes the language. NFA A nondeterministic finite automaton that recognizes the language. Regular expression A regular expression that describes the language. Example: 0∗1∗0^*1^*0∗1∗ describes {0n1m∣n,m≥0}\{0^n1^m \mid n, m \ge 0\}{0n1m∣n,m≥0} . If none of the three can exist, the language is not regular. The pumping lemma is a systematic way to show this.

  2. [Intuitive Idea Behind the Lemma] Why, intuitively, is A={0n1n∣n≥0}A = \{0^n1^n \mid n \ge 0\}A={0n1n∣n≥0} not regular?

    Recognizing AAA requires remembering the number of 000 's, which needs infinitely many states, but a finite automaton has finitely many states. Likewise, the star operation ( )∗(\ )^*( )∗ in a regular expression cannot keep track of numbers.Example: B={w∣wB = \{w \mid wB={w∣w has an equal number of 000 's and 111 's }\}} is non-regular for the same reason.

  3. [Intuitive Idea Behind the Lemma] An NFA has nnn states. What is the greatest length of an accepted string whose computation visits no state twice?

    n−1\boldsymbol{n - 1}n−1 Reading mmm symbols visits m+1m + 1m+1 states (the start state included), so with m≥nm \ge nm≥n some state repeats.Example: an NFA with 5 states can accept abcaabcaabca along 5 different states:

  4. [Intuitive Idea Behind the Lemma] What is the basic idea behind the pumping lemma?

    If an NFA accepts a long string, the computation must contain a loop. "Long" means ∣w∣≥n|w| \ge n∣w∣≥n , where nnn is the number of states: the computation visits ∣w∣+1>n|w| + 1 > n∣w∣+1>n states, so some state appears twice.

  5. [Intuitive Idea Behind the Lemma] An accepting computation of an NFA goes around a loop once. What can be said about strings that go around the same loop a different number of times?

    They are accepted too, for any number of turns, including zero (if the rest of the string is the same). Example: if abacaabacaabaca is accepted with the second aaa read on a loop at one state, then abancaaba^ncaabanca is accepted for all n≥0n \ge 0n≥0 .

  6. [Intuitive Idea Behind the Lemma] An NFA accepts abacaabacaabaca along this path (the NFA may have more transitions): Which strings must the NFA then also accept?

    abanca\boldsymbol{aba^nca}abanca for every n≥0\boldsymbol{n \ge 0}n≥0 The loop at q2q_2q2​ reads aaa and can be taken nnn times. n=0n = 0n=0 gives abcaabcaabca .

  7. [Intuitive Idea Behind the Lemma] An NFA accepts abcccaabcccaabccca along this path (the NFA may have more transitions): Which strings must the NFA then also accept?

    abc(cc)na\boldsymbol{abc(cc)^na}abc(cc)na for every n≥0\boldsymbol{n \ge 0}n≥0 The loop q2→q3→q2q_2 \to q_3 \to q_2q2​→q3​→q2​ reads cccccc and can be taken nnn times. n=0n = 0n=0 gives abcaabcaabca .

  8. [Intuitive Idea Behind the Lemma] Copying a part of a string and pasting it nnn times is called pumping.

    Example: pumping the middle aaa of abacaabacaabaca gives abancaaba^ncaabanca , e.g. abcaabcaabca , abacaabacaabaca , abaacaabaacaabaaca .

  9. [Intuitive Idea Behind the Lemma] What does the pumping lemma say, in one sentence?

    Every sufficiently long string of a regular language can be pumped.

  10. [The Pumping Lemma] State the pumping lemma for a regular language LLL .

    There is an integer ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 . Example: L=a∗bL = a^*bL=a∗b and p=2p = 2p=2 . For s=aabs = aabs=aab : x=εx = \varepsilonx=ε , y=ay = ay=a , z=abz = abz=ab , and xykz=ak+1b∈Lxy^kz = a^{k+1}b \in Lxykz=ak+1b∈L .

  11. [The Pumping Lemma] In the pumping lemma, the integer ppp is called the pumping length.

    Every string s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be pumped.

  12. [The Pumping Lemma] In the pumping lemma, what is yky^kyk , and what is y0y^0y0 ?

    yky^kyk = kkk copies of yyy concatenated; y0=ε\ y^0 = \boldsymbol{\varepsilon} y0=ε Example: y=aby = aby=ab gives y3=abababy^3 = abababy3=ababab , and xy0z=xzxy^0z = xzxy0z=xz .

  13. [The Pumping Lemma] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 .In the proof, what is ppp ?

    The number of states of an NFA that recognizes LLL .

  14. [The Pumping Lemma] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 . ppp is the number of states of an NFA recognizing LLL , and s=s1s2⋯sn∈Ls = s_1s_2 \cdots s_n \in Ls=s1​s2​⋯sn​∈L with n≥pn \ge pn≥p . Why does some state repeat while the NFA reads sss ?

    Pigeonhole principle: an accepting computation passes through p+1p + 1p+1 states (start included) while reading s1⋯sps_1 \cdots s_ps1​⋯sp​ , but the NFA has only ppp states. So the NFA is in the same state after two inputs sis_isi​ and sjs_jsj​ with i<j≤pi < j \le pi<j≤p (where i=0i = 0i=0 means the start).

  15. [The Pumping Lemma] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 .In the proof, the NFA is in the same state qqq after reading sis_isi​ and after reading sjs_jsj​ ( i<ji < ji<j ) of s=s1⋯sns = s_1 \cdots s_ns=s1​⋯sn​ . How are xxx , yyy , zzz chosen?

    x=s1⋯si, y=si+1⋯sj, z=sj+1⋯sn\boldsymbol{x = s_1 \cdots s_i, \ \ y = s_{i+1} \cdots s_j, \ \ z = s_{j+1} \cdots s_n}x=s1​⋯si​, y=si+1​⋯sj​, z=sj+1​⋯sn​ yyy takes the NFA from qqq back to qqq .

  16. [The Pumping Lemma] Pumping lemma proof: p=6p = 6p=6 states, ∣s∣=9|s| = 9∣s∣=9 , and the NFA is in the same state q3q_3q3​ after reading s4s_4s4​ and after reading s7s_7s7​ .What are xxx , yyy and zzz ?

    x=s1s2s3s4, y=s5s6s7, z=s8s9\boldsymbol{x = s_1s_2s_3s_4, \ \ y = s_5s_6s_7, \ \ z = s_8s_9}x=s1​s2​s3​s4​, y=s5​s6​s7​, z=s8​s9​ yyy is read on a loop from q3q_3q3​ back to q3q_3q3​ .

  17. [The Pumping Lemma] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 .In the proof, yyy takes the NFA from a state qqq back to qqq . Why is xykz∈Lxy^kz \in Lxykz∈L for every k≥0k \ge 0k≥0 ?

    Reading yyy any number of times (also zero) ends in the same state qqq , so the computation on xykzxy^kzxykz ends exactly like the one on xyzxyzxyz : in an accept state.

  18. [The Pumping Lemma] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 .In the proof, the same state repeats after inputs sis_isi​ and sjs_jsj​ with i<j≤pi < j \le pi<j≤p , and y=si+1⋯sjy = s_{i+1} \cdots s_jy=si+1​⋯sj​ . Why do ∣y∣≥1|y| \ge 1∣y∣≥1 and ∣xy∣≤p|xy| \le p…

    ∣y∣=j−i≥1|y| = j - i \ge 1∣y∣=j−i≥1 because i≠ji \ne ji=j ; ∣xy∣=j≤p\ |xy| = j \le p ∣xy∣=j≤p because the repetition is found among the first ppp symbols.

  19. [Applications] The pumping lemma says: LLL regular ⇒\Rightarrow⇒ every string in LLL of length at least ppp can be pumped. Which equivalent form proves that a language is not regular?

    If some string in LLL of length at least ppp cannot be pumped, then LLL is not regular. The contrapositive. One single string that cannot be pumped is enough.

  20. [Applications] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 .What exactly does " sss cannot be pumped" mean?

    For every division s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p and ∣y∣≥1|y| \ge 1∣y∣≥1 , some k≥0k \ge 0k≥0 gives xykz∉Lxy^kz \notin Lxykz∈/L . So the proof has to cover all possible yyy , not one chosen yyy .

  21. [Applications] What are the steps of a proof that LLL is not regular with the pumping lemma?

    Assume LLL is regular, with pumping length ppp . Example: L={0n1n∣n≥0}L = \{0^n1^n \mid n \ge 0\}L={0n1n∣n≥0} . Choose a test string s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p , written in terms of ppp . Example: s=0p1ps = 0^p1^ps=0p1p . Consider every division s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 . Example: ∣xy∣≤p|xy| \le p∣xy∣≤p forces y=0iy = 0^iy=0i with i≥1i \ge 1i≥1 . Pump Find k≥0k \ge 0k≥0 with xykz∉Lxy^kz \notin Lxykz∈/L . Example: xy2z=0p+i1p∉Lxy^2z = 0^{p+i…

  22. [Applications] Show that L={0n1n∣n≥0}L = \{0^n1^n \mid n \ge 0\}L={0n1n∣n≥0} is not regular (pumping length ppp ): which test string, and why can it not be pumped?

    s=0p1p\boldsymbol{s = 0^p1^p}s=0p1p ; xy2z∉Lxy^2z \notin Lxy2z∈/L for every possible yyy . If yyy has one kind of symbol, xy2zxy^2zxy2z has unequal numbers of 000 's and 111 's. If yyy contains both, xy2zxy^2zxy2z has symbols out of order (a 111 before a 000 ).

  23. [Applications] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 .For the test string s=0p1ps = 0^p1^ps=0p1p , why does the condition ∣xy∣≤p|xy| \le p∣xy∣≤p simplify the proof?

    xyxyxy lies within the first ppp symbols, which are all 000 's, so y=0iy = 0^iy=0i with 1≤i≤p1 \le i \le p1≤i≤p . Then only one case is left: xy2z=0p+i1pxy^2z = 0^{p+i}1^pxy2z=0p+i1p .

  24. [Applications] Show that L={0n12n0n∣n≥0}L = \{0^n1^{2n}0^n \mid n \ge 0\}L={0n12n0n∣n≥0} is not regular (pumping length ppp ): which test string, and which pumped string is not in LLL ?

    s=0p12p0p\boldsymbol{s = 0^p1^{2p}0^p}s=0p12p0p ; with y=0iy = 0^iy=0i : xy2z=0p+i12p0p∉Lxy^2z = 0^{p+i}1^{2p}0^p \notin Lxy2z=0p+i12p0p∈/L ∣xy∣≤p|xy| \le p∣xy∣≤p forces yyy into the first block of 000 's. (A yyy of 111 's only, or of both symbols, also fails.)

  25. [Applications] Show that L={an−2bn+2∣n≥2}L = \{a^{n-2}b^{n+2} \mid n \ge 2\}L={an−2bn+2∣n≥2} is not regular (pumping length ppp ): which test string, and why can it not be pumped?

    s=apbp+4\boldsymbol{s = a^pb^{p+4}}s=apbp+4 ; y=aiy = a^iy=ai , and xyyz=ap+ibp+4∉Lxyyz = a^{p+i}b^{p+4} \notin Lxyyz=ap+ibp+4∈/L L={ajbj+4∣j≥0}L = \{a^jb^{j+4} \mid j \ge 0\}L={ajbj+4∣j≥0} : every string has exactly 4 more bbb 's than aaa 's. Pumping aaa 's breaks this.Example: y=a2y = a^2y=a2 gives ap+2bp+4a^{p+2}b^{p+4}ap+2bp+4 , only 2 more bbb 's.

  26. [Applications] Over Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} , which of these languages is regular? Give a regular expression for that language. A={anbmcnm∣n,m≥0}A = \{a^nb^mc^{nm} \mid n, m \ge 0\}A={anbmcnm∣n,m≥0} B={a2nbmck+1a2∣n,m,k≥0}B = \{a^{2n}b^mc^{k+1}a^2 \mid n, m, k \ge 0\}B={a2nbmck+1a2∣n,m,k≥0}

    B\boldsymbol{B}B , with regular expression (aa)∗b∗c+aa\boldsymbol{(aa)^*b^*c^+aa}(aa)∗b∗c+aa AAA is not regular: the number of ccc 's depends on the product nmnmnm .

  27. [Applications] Show that A={anbmcnm∣n,m≥0}A = \{a^nb^mc^{nm} \mid n, m \ge 0\}A={anbmcnm∣n,m≥0} is not regular (pumping length ppp ): which test string, and which pumped string is not in AAA ?

    s=apbpcp2\boldsymbol{s = a^pb^pc^{p^2}}s=apbpcp2 ; with y=aiy = a^iy=ai : xyyz=ap+ibpcp2∉Axyyz = a^{p+i}b^pc^{p^2} \notin Axyyz=ap+ibpcp2∈/A ∣xy∣≤p|xy| \le p∣xy∣≤p forces y=aiy = a^iy=ai , i≥1i \ge 1i≥1 , and (p+i)⋅p≠p2(p + i) \cdot p \ne p^2(p+i)⋅p=p2 .

  28. [Applications] Show that L={1n2∣n≥0}L = \{1^{n^2} \mid n \ge 0\}L={1n2∣n≥0} is not regular (pumping length ppp ): which test string, and why is xy2z∉Lxy^2z \notin Lxy2z∈/L ?

    s=1p2\boldsymbol{s = 1^{p^2}}s=1p2 ; xy2z=1p2+kxy^2z = 1^{p^2+k}xy2z=1p2+k with 1≤k≤p1 \le k \le p1≤k≤p , and p2+kp^2 + kp2+k is not a perfect square. p2<p2+k<p2+2p+1=(p+1)2p^2 < p^2 + k < p^2 + 2p + 1 = (p + 1)^2p2<p2+k<p2+2p+1=(p+1)2 , so p2+kp^2 + kp2+k lies strictly between two consecutive squares.

  29. [Applications] Show that L={1n!∣n≥0}L = \{1^{n!} \mid n \ge 0\}L={1n!∣n≥0} is not regular (pumping length ppp ): which test string, and why is xy2z∉Lxy^2z \notin Lxy2z∈/L ?

    s=1p!\boldsymbol{s = 1^{p!}}s=1p! ; xy2z=1p!+kxy^2z = 1^{p!+k}xy2z=1p!+k with 1≤k≤p1 \le k \le p1≤k≤p , and p!+kp! + kp!+k is not a factorial. (p+1)!−p!=p⋅p!>p≥k(p + 1)! - p! = p \cdot p! > p \ge k(p+1)!−p!=p⋅p!>p≥k , so p!<p!+k<(p+1)!p! < p! + k < (p + 1)!p!<p!+k<(p+1)! . This needs p≥2p \ge 2p≥2 , which is no restriction: a larger pumping length also works.

  30. [Applications] What is wRw^RwR for a string www , and which strings satisfy w=wRw = w^Rw=wR ?

    wRw^RwR = www reversed; w=wRw = w^Rw=wR holds for the palindromes. Example: 11101R=1011111101^R = 1011111101R=10111 , so 111011110111101 is not a palindrome; 1100011R=11000111100011^R = 11000111100011R=1100011 .

  31. [Applications] Show that the language of palindromes L={w∣w=wR}L = \{w \mid w = w^R\}L={w∣w=wR} over {0,1}\{0, 1\}{0,1} is not regular (pumping length ppp ): which test string, and which pumped string is not in LLL ?

    s=0p10p\boldsymbol{s = 0^p10^p}s=0p10p ; with y=0ky = 0^ky=0k : xyyz=0p+k10p∉Lxyyz = 0^{p+k}10^p \notin Lxyyz=0p+k10p∈/L ∣xy∣≤p|xy| \le p∣xy∣≤p forces yyy into the first block of 000 's, and 0p+k10p0^{p+k}10^p0p+k10p reversed is 0p10p+k0^p10^{p+k}0p10p+k .

  32. [Applications] Show that L={anbm∣n>m≥0}L = \{a^nb^m \mid n > m \ge 0\}L={anbm∣n>m≥0} is not regular (pumping length ppp ): which test string, and which kkk gives xykz∉Lxy^kz \notin Lxykz∈/L ?

    s=ap+1bp\boldsymbol{s = a^{p+1}b^p}s=ap+1bp , and k=0\boldsymbol{k = 0}k=0 : xz=ap+1−ibp∉Lxz = a^{p+1-i}b^p \notin Lxz=ap+1−ibp∈/L y=aiy = a^iy=ai with i≥1i \ge 1i≥1 . Pumping up ( k≥2k \ge 2k≥2 ) only adds aaa 's, and the strings stay in LLL . Pumping down leaves at most as many aaa 's as bbb 's.

  33. [Applications] Using k=0k = 0k=0 in the pumping lemma, i.e. deleting yyy , is called pumping down.

    Example: for L={anbm∣n>m}L = \{a^nb^m \mid n > m\}L={anbm∣n>m} and s=ap+1bps = a^{p+1}b^ps=ap+1bp , only pumping down leaves LLL .

  34. [Applications] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 .To show that A={0n1m∣n,m≥0, n≠m}A = \{0^n1^m \mid n, m \ge 0, \ n \ne m\}A={0n1m∣n,m≥0, n=m} is not regular, why does the test string s=0p1p+p!s = 0^p1^{p+p!}s=0p1p+p! work?

    y=0iy = 0^iy=0i with 1≤i≤p1 \le i \le p1≤i≤p , so iii divides p!p!p! , and k=1+p!ik = 1 + \frac{p!}{i}k=1+ip!​ gives xykz=0p+p!1p+p!∉Axy^kz = 0^{p+p!}1^{p+p!} \notin Axykz=0p+p!1p+p!∈/A . Example: p=3p = 3p=3 , s=0319s = 0^31^9s=0319 . For y=02y = 0^2y=02 : k=4k = 4k=4 gives 09190^91^90919 .A test string like 02130^21^30213 fails for p=3p = 3p=3 : with y=02y = 0^2y=02 the number of 000 's stays even, never 3.

  35. [Applications] Prove without pumping that A={0n1m∣n,m≥0, n≠m}A = \{0^n1^m \mid n, m \ge 0, \ n \ne m\}A={0n1m∣n,m≥0, n=m} is not regular.

    If AAA were regular, so would be A‾∩0∗1∗={0n1n∣n≥0}\overline{A} \cap 0^*1^* = \{0^n1^n \mid n \ge 0\}A∩0∗1∗={0n1n∣n≥0} , which is not regular. Regular languages are closed under complement and intersection, and 0∗1∗0^*1^*0∗1∗ is regular.

  36. [Exercises] Is L={a2nbcn∣n≥0}L = \{a^{2n}bc^n \mid n \ge 0\}L={a2nbcn∣n≥0} regular? If not, which test string proves this with the pumping lemma (pumping length ppp )?

    Not regular; test string s=a2pbcp\boldsymbol{s = a^{2p}bc^p}s=a2pbcp y=aiy = a^iy=ai , and xyyz=a2p+ibcp∉Lxyyz = a^{2p+i}bc^p \notin Lxyyz=a2p+ibcp∈/L because the number of aaa 's is no longer twice the number of ccc 's.

  37. [Exercises] Is L={a3n+2bm+1ck∣n,m≥0, k=3 or k=5}L = \{a^{3n+2}b^{m+1}c^k \mid n, m \ge 0, \ k = 3 \text{ or } k = 5\}L={a3n+2bm+1ck∣n,m≥0, k=3 or k=5} regular? If yes, give a regular expression.

    Regular: aa(aaa)∗bb∗(ccc∪ccccc)\boldsymbol{aa(aaa)^*bb^*(ccc \cup ccccc)}aa(aaa)∗bb∗(ccc∪ccccc)

  38. [Exercises] Is L={ww∣w∈{a,b,c}∗}L = \{ww \mid w \in \{a, b, c\}^*\}L={ww∣w∈{a,b,c}∗} regular? If not, which test string proves this with the pumping lemma (pumping length ppp )?

    Not regular; test string s=apbapb\boldsymbol{s = a^pba^pb}s=apbapb y=aiy = a^iy=ai , and xyyz=ap+ibapbxyyz = a^{p+i}ba^pbxyyz=ap+ibapb is not of the form wwwwww : for odd iii the length is odd, and for even i≥2i \ge 2i≥2 the first half contains no bbb .

  39. [Exercises] Is L={anbmck∣m+n+k=100}L = \{a^nb^mc^k \mid m + n + k = 100\}L={anbmck∣m+n+k=100} regular?

    Regular, because LLL is finite. Every finite language is regular (the union of its strings is a regular expression), here just a long one.

  40. [Exercises] Is L={anbm∣0≤n<m}L = \{a^nb^m \mid 0 \le n < m\}L={anbm∣0≤n<m} regular? If not, which test string proves this with the pumping lemma (pumping length ppp )?

    Not regular; test string s=apbp+1\boldsymbol{s = a^pb^{p+1}}s=apbp+1 y=aiy = a^iy=ai , and xyyz=ap+ibp+1xyyz = a^{p+i}b^{p+1}xyyz=ap+ibp+1 has at least as many aaa 's as bbb 's.

  41. [Exercises] Is L={1n∣n is prime}L = \{1^n \mid n \text{ is prime}\}L={1n∣n is prime} regular? If not, how does the pumping lemma (pumping length ppp ) prove this?

    Not regular; test string s=1ks = 1^ks=1k with kkk prime, k>pk > pk>p , and xyk+1z∉L\boldsymbol{xy^{k+1}z \notin L}xyk+1z∈/L With y=1iy = 1^iy=1i ( i≥1i \ge 1i≥1 ): xyk+1z=1k+ki=1k(i+1)xy^{k+1}z = 1^{k + ki} = 1^{k(i+1)}xyk+1z=1k+ki=1k(i+1) , and k(i+1)k(i + 1)k(i+1) is not prime since k≥2k \ge 2k≥2 and i+1≥2i + 1 \ge 2i+1≥2 .

  42. [Exercises] Is L={0n1m∣2n>m}L = \{0^n1^m \mid 2n > m\}L={0n1m∣2n>m} regular? If not, which test string proves this with the pumping lemma (pumping length ppp )?

    Not regular; test string s=0p12p−1\boldsymbol{s = 0^p1^{2p-1}}s=0p12p−1 , pumped down y=0iy = 0^iy=0i , and xz=0p−i12p−1xz = 0^{p-i}1^{2p-1}xz=0p−i12p−1 has 2(p−i)≤2p−2<2p−12(p - i) \le 2p - 2 < 2p - 12(p−i)≤2p−2<2p−1 .

  43. [Exercises] Is L={anbm∣n and m are both odd}L = \{a^nb^m \mid n \text{ and } m \text{ are both odd}\}L={anbm∣n and m are both odd} regular? If yes, give a regular expression.

    Regular: a(aa)∗b(bb)∗\boldsymbol{a(aa)^*b(bb)^*}a(aa)∗b(bb)∗

  44. [Exercises] Is L={akbmcn∣k<m<n}L = \{a^kb^mc^n \mid k < m < n\}L={akbmcn∣k<m<n} regular? If not, which test string proves this with the pumping lemma (pumping length ppp )?

    Not regular; test string s=apbp+1cp+2\boldsymbol{s = a^pb^{p+1}c^{p+2}}s=apbp+1cp+2 y=aiy = a^iy=ai , and xyyz=ap+ibp+1cp+2xyyz = a^{p+i}b^{p+1}c^{p+2}xyyz=ap+ibp+1cp+2 has p+i≥p+1p + i \ge p + 1p+i≥p+1 , so k<mk < mk<m fails.

  45. [Exercises] Is L={akbmcn∣k≥2, m≥0, n≤2}L = \{a^kb^mc^n \mid k \ge 2, \ m \ge 0, \ n \le 2\}L={akbmcn∣k≥2, m≥0, n≤2} regular? If yes, give a regular expression.

    Regular: aaa∗b∗(ε∪c∪cc)\boldsymbol{aaa^*b^*(\varepsilon \cup c \cup cc)}aaa∗b∗(ε∪c∪cc)

  46. [Exercises] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 . B={w∈{0,1}∗∣w ends with 111}B = \{w \in \{0, 1\}^* \mid w \text{ ends with } 111\}B={w∈{0,1}∗∣w ends with 111} is regular, with p=4p = 4p=4 . How can every s∈Bs \in Bs∈B with ∣s∣≥4|s| \ge 4∣s∣≥4 be divide…

    x=ε\boldsymbol{x = \varepsilon}x=ε , yyy = the first symbol, zzz = the rest ∣xy∣=1≤4|xy| = 1 \le 4∣xy∣=1≤4 , and the first symbol is not part of the final 111111111 , so every xykzxy^kzxykz ends with 111111111 .

  47. [Exercises] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 . C={w∈{0,1}∗∣w contains 111}C = \{w \in \{0, 1\}^* \mid w \text{ contains } 111\}C={w∈{0,1}∗∣w contains 111} is regular, with p=4p = 4p=4 . How can every s∈Cs \in Cs∈C with ∣s∣≥4|s| \ge 4∣s∣≥4 be divided a…

    If sss starts with 111111111 : x=111x = 111x=111 , yyy = the fourth symbol. Otherwise: x=εx = \varepsilonx=ε , yyy = the first symbol. zzz = the rest. In both cases pumping yyy does not touch an occurrence of 111111111 .

  48. [Exercises] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 . D={w∈{0,1}∗∣w has odd length}D = \{w \in \{0, 1\}^* \mid w \text{ has odd length}\}D={w∈{0,1}∗∣w has odd length} is regular, with p=3p = 3p=3 . How can every s∈Ds \in Ds∈D with ∣s∣≥3|s| \ge 3∣s∣≥3 be divi…

    xxx = the first symbol, yyy = the second and third symbols, zzz = the rest ∣y∣=2|y| = 2∣y∣=2 is even, so every xykzxy^kzxykz has odd length; ∣xy∣=3≤3|xy| = 3 \le 3∣xy∣=3≤3 .

  49. [Exercises] Pumping lemma: for a regular language LLL there is an integer ppp (the pumping length) such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=xyzs = xyzs=xyz with ∣xy∣≤p|xy| \le p∣xy∣≤p , ∣y∣≥1|y| \ge 1∣y∣≥1 , and xykz∈Lxy^kz \in Lxykz∈L for each k≥0k \ge 0k≥0 . E={w∈{0,1}∗∣w starts and ends with the same symbol}E = \{w \in \{0, 1\}^* \mid w \text{ starts and ends with the same symbol}\}E={w∈{0,1}∗∣w starts and ends with the same symbol} is regular, with p=3p = 3…

    xxx = the first symbol, yyy = the second symbol, zzz = the rest Pumping yyy changes neither the first nor the last symbol.