Ch.9: Non-Context-Free Languages

Week 9 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 9.1. PDA - CFG Equivalence 9.2. Pumping Lemma for Context-Free Languages 9.3. Closure Properties of CFLs

49 flashcards · Computer Science · by lakesare

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

1. [PDA - CFG Equivalence] Theorem. A language is context-free if and only if … ?

   There is a PDA (pushdown automaton) recognizing it. So: given a CFG, we can find an equivalent PDA, and given a PDA, we can find an equivalent CFG.

2. [PDA - CFG Equivalence] To turn a CFG into an equivalent PDA, into which form is the grammar put first?

   Every production has the form A→aBCD⋯A \to aBCD \cdotsA→aBCD⋯ : a single terminal, followed by zero or more variables. Example: S→1SAA∣0∣0BS \to 1SAA \mid 0 \mid 0BS→1SAA∣0∣0B , A→1\ A \to 1 A→1 , B→0\ B \to 0 B→0 has this form.

3. [PDA - CFG Equivalence] Rewrite the grammar S→1S11∣0∣00S \to 1S11 \mid 0 \mid 00S→1S11∣0∣00 so that every right-hand side is a single terminal followed by zero or more variables.

   S→1SAA∣0∣0B,A→1,B→0\boldsymbol{S \to 1SAA \mid 0 \mid 0B, \quad A \to 1, \quad B \to 0}S→1SAA∣0∣0B,A→1,B→0 New variables AAA and BBB stand for the terminals 111 and 000 that are not in first position.

4. [PDA - CFG Equivalence] Give the PDA for the grammar S→1SAA∣0∣0BS \to 1SAA \mid 0 \mid 0BS→1SAA∣0∣0B , A→1\ A \to 1 A→1 , B→0\ B \to 0 B→0 (every right-hand side: one terminal, then variables).

   Three states: push S$S\text{\textdollar}S$ , then loop with one transition " a,A→αa, A \to \alphaa,A→α " per production A→aαA \to a\alphaA→aα , then pop $\text{\textdollar}$ and accept. 1,S→SAA1, S \to SAA1,S→SAA comes from S→1SAAS \to 1SAAS→1SAA ; 0,B→ε\ 0, B \to \varepsilon 0,B→ε comes from B→0B \to 0B→0 .

5. [PDA - CFG Equivalence] In PDA transitions, what does "push SASASA " mean: which symbol is pushed first, and which ends up on top?

   First push AAA , then push SSS ; so SSS is on top. The leftmost symbol of the pushed string is on top of the stack.

6. [PDA - CFG Equivalence] A PDA built from a CFG in the form A→aBC⋯A \to aBC\cdotsA→aBC⋯ (one terminal, then variables) simulates which derivation?

   The leftmost derivation; at each step the stack holds the string of variables of the current step. Example: for S→1SAA∣0S \to 1SAA \mid 0S→1SAA∣0 , A→1A \to 1A→1 : derivation S⇒1SAA⇒10AAS \Rightarrow 1SAA \Rightarrow 10AAS⇒1SAA⇒10AA , the stack goes S→SAA→AAS \to SAA \to AAS→SAA→AA .

7. [PDA - CFG Equivalence] A PDA is built from a CFG whose productions all have the form A→aBC⋯A \to aBC\cdotsA→aBC⋯ (one terminal, then variables), and simulates the leftmost derivation.What happens on the stack at each step?

   Input At each step, one symbol of the input is read. Example: the transition 1,S→SAA1, S \to SAA1,S→SAA reads 111 . Variable replaced by a terminal That variable is popped from the stack: it disappears from the derivation. Example: A→1A \to 1A→1 gives the transition 1,A→ε1, A \to \varepsilon1,A→ε . Variable replaced by a terminal and variables The variable is popped and the new variables are pushed in the correct order, the leftmost on top. Example: S→1SAAS \to 1SAAS→1SAA gives 1,S→SAA1, S \to…

8. [PDA - CFG Equivalence] A PDA built from a CFG has several transitions for the same input and stack top (e.g. 0,S→ε0, S \to \varepsilon0,S→ε and 0,S→B0, S \to B0,S→B ). What in the grammar does this nondeterminism correspond to?

   The choice between several productions for the same variable (branching in the grammar). 0,S→ε0, S \to \varepsilon0,S→ε and 0,S→B0, S \to B0,S→B come from S→0S \to 0S→0 and S→0BS \to 0BS→0B .

9. [PDA - CFG Equivalence] A PDA transition pushes a single symbol. How can a transition like 1,S→SAA1, S \to SAA1,S→SAA that pushes several symbols be realized?

   With extra states: push one symbol per transition, moving through intermediate states.

10. [PDA - CFG Equivalence] PDA: start state, then ε,ε→S$\varepsilon, \varepsilon \to S\text{\textdollar}ε,ε→S$ ; a loop state with transitions 0,S→ε0, S \to \varepsilon0,S→ε ; 0,S→B\ 0, S \to B 0,S→B ; 0,B→ε\ 0, B \to \varepsilon 0,B→ε ; 1,S→SAA\ 1, S \to SAA 1,S→SAA ; 1,A→ε\ 1, A \to \varepsilon 1,A→ε ; then ε,$→ε\varepsilon, \text{\textdollar} \to \varepsilonε,$→ε to the accept state.Trace the stack on the input 101110111011 . Is it accepted?

    Yes: S$→SAA$→AA$→A$→$→S\text{\textdollar} \to SAA\text{\textdollar} \to AA\text{\textdollar} \to A\text{\textdollar} \to \text{\textdollar} \toS$→SAA$→AA$→A$→$→ empty, then accept. Transitions used: 1,S→SAA1, S \to SAA1,S→SAA ; 0,S→ε\ 0, S \to \varepsilon 0,S→ε ; 1,A→ε\ 1, A \to \varepsilon 1,A→ε ; 1,A→ε\ 1, A \to \varepsilon 1,A→ε .Matching derivation in S→1S11∣0∣00S \to 1S11 \mid 0 \mid 00S→1S11∣0∣00 : S⇒1S11⇒1011S \Rightarrow 1S11 \Rightarrow 1011S⇒1S11⇒1011 .

11. [Pumping Lemma for Context-Free Languages] Pumping lemma for context-free languages. If LLL is context-free, there is a pumping length ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p can be divided as s=uvxyzs = uvxyzs=uvxyz with which three conditions?

    1. uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for each k≥0k \ge 0k≥0 ; 2. ∣vy∣>0|vy| > 0∣vy∣>0 ; 3. ∣vxy∣≤p|vxy| \le p∣vxy∣≤p . Example: L={anbn∣n≥0}L = \{a^nb^n \mid n \ge 0\}L={anbn∣n≥0} , s=aabbs = aabbs=aabb : u=au = au=a , v=av = av=a , x=εx = \varepsilonx=ε , y=by = by=b , z=bz = bz=b ; then uvkxykz=ak+1bk+1∈Luv^kxy^kz = a^{k+1}b^{k+1} \in Luvkxykz=ak+1bk+1∈L .

12. [Pumping Lemma for Context-Free Languages] In the pumping lemma for CFLs ( s=uvxyzs = uvxyzs=uvxyz ), what does the condition ∣vy∣>0|vy| > 0∣vy∣>0 say, and why is it needed?

    vvv and yyy are not both ε\varepsilonε ; without it, the lemma would be true but say nothing. With v=y=εv = y = \varepsilonv=y=ε , uvkxykz=s∈Luv^kxy^kz = s \in Luvkxykz=s∈L for every kkk , for any language.

13. [Pumping Lemma for Context-Free Languages] In the pumping lemma for CFLs ( s=uvxyzs = uvxyzs=uvxyz , pumping length ppp ), what does the condition ∣vxy∣≤p|vxy| \le p∣vxy∣≤p say?

    The pieces vvv , xxx , yyy together have length at most ppp . So vvv and yyy lie within a window of ppp consecutive symbols of sss .Example: in apbpcpa^pb^pc^papbpcp , vxyvxyvxy cannot contain both an aaa and a ccc .

14. [Pumping Lemma for Context-Free Languages] LLL is the language of palindromes of odd length over {0,1}\{0, 1\}{0,1} . What is a pumping length, and how is s=11011s = 11011s=11011 divided as uvxyzuvxyzuvxyz ?

    p=3p = 3p=3 ; u=1,v=1,x=0,y=1,z=1\ u = 1, v = 1, x = 0, y = 1, z = 1 u=1,v=1,x=0,y=1,z=1 (pump the symbols next to the middle). uvkxykz=1 1k 0 1k 1uv^kxy^kz = 1\,1^k\,0\,1^k\,1uvkxykz=11k01k1 is again an odd palindrome.

15. [Pumping Lemma for Context-Free Languages] In the proof of the pumping lemma for CFLs, why does some variable repeat in the parse tree of a long string s∈Ls \in Ls∈L ?

    By the pigeonhole principle: a long string has a tall parse tree, so some path has more variables than the grammar has, and some variable BBB repeats. The upper BBB derives vxyvxyvxy , the lower BBB derives xxx .

16. [Pumping Lemma for Context-Free Languages] In the parse tree of s=uvxyz∈Ls = uvxyz \in Ls=uvxyz∈L , a variable BBB occurs twice on one path: the upper BBB derives vxyvxyvxy , the lower BBB derives xxx .How does the proof of the pumping lemma for CFLs get uxz∈Luxz \in Luxz∈L ?

    Replace the subtree of the upper BBB by the subtree of the lower BBB . The result is a parse tree of the grammar, so uv0xy0z=uxz∈Luv^0xy^0z = uxz \in Luv0xy0z=uxz∈L .

17. [Pumping Lemma for Context-Free Languages] In the parse tree of s=uvxyz∈Ls = uvxyz \in Ls=uvxyz∈L , a variable BBB occurs twice on one path: the upper BBB derives vxyvxyvxy , the lower BBB derives xxx .How does the proof of the pumping lemma for CFLs get uv2xy2z∈Luv^2xy^2z \in Luv2xy2z∈L ?

    Replace the subtree of the lower BBB by a copy of the subtree of the upper BBB . Repeating this gives uvkxykzuv^kxy^kzuvkxykz for every kkk ; each string has a parse tree in the grammar, so it is in LLL .

18. [Pumping Lemma for Context-Free Languages] How is the pumping lemma used to show that a language LLL is not context-free?

    Assume LLL is a CFL with pumping length ppp ; choose s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p ; show that for every division s=uvxyzs = uvxyzs=uvxyz with ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p , some uvkxykz∉Luv^kxy^kz \notin Luvkxykz∈/L . Then sss cannot be pumped, a contradiction.

19. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .Why is L={0n10n10n∣n≥0}L = \{0^n10^n10^n \mid n \ge 0\}L={0n10n10n∣n≥0} not context-free? Which test string?

    s=0p10p10ps = 0^p10^p10^ps=0p10p10p : if vvv or yyy contains a 111 , uv2xy2zuv^2xy^2zuv2xy2z has more than two 1's; if both consist of 0's, pumping changes at most two of the three blocks of 0's. ∣vxy∣≤p|vxy| \le p∣vxy∣≤p , so vxyvxyvxy cannot touch all three blocks.

20. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .Why is {anbncn∣n≥0}\{a^nb^nc^n \mid n \ge 0\}{anbncn∣n≥0} not context-free? Test string: s=apbpcps = a^pb^pc^ps=apbpcp .

    vvv or yyy contains more than one symbol Then uv2xy2zuv^2xy^2zuv2xy2z has symbols out of order. Example: v=abv = abv=ab gives ⋯abab⋯\cdots abab \cdots⋯abab⋯ , an aaa after a bbb . vvv and yyy each contain a single symbol Then pumping changes at most two of the three counts; the third stays ppp . Example: v=av = av=a , y=by = by=b : uv2xy2z=ap+1bp+1cp∉Luv^2xy^2z = a^{p+1}b^{p+1}c^p \notin Luv2xy2z=ap+1bp+1cp∈/L . So sss cannot be pumped.

21. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .Why is {akbmcn∣k<m<n}\{a^kb^mc^n \mid k < m < n\}{akbmcn∣k<m<n} not context-free? Test string: s=apbp+1cp+2s = a^pb^{p+1}c^{p+2}s=apbp+1cp+2 .

    If vyvyvy contains aaa 's, pump up twice ( uv3xy3zuv^3xy^3zuv3xy3z ): at least p+2p + 2p+2 aaa 's, as many as ccc 's. Otherwise pump down ( uxzuxzuxz ): m≤pm \le pm≤p or n≤p+1n \le p + 1n≤p+1 . vvv , yyy each contain one kind of symbol (else symbols are out of order). vxyvxyvxy cannot contain both aaa 's and ccc 's, since ∣vxy∣≤p|vxy| \le p∣vxy∣≤p and there are p+1p + 1p+1 bbb 's between them.Pumping down without aaa 's: removing bbb 's gives m≤p=km \le p = km≤p=k ; removing only ccc 's gives n…

22. [Pumping Lemma for Context-Free Languages] Is A={anbmcmdn∣n,m≥0}A = \{a^nb^mc^md^n \mid n, m \ge 0\}A={anbmcmdn∣n,m≥0} context-free?

    Yes: S→aSd∣TS \to aSd \mid TS→aSd∣T , T→bTc∣ε\ T \to bTc \mid \varepsilon T→bTc∣ε PDA: push aaa 's, then push bbb 's, then pop a bbb for each ccc and an aaa for each ddd .

23. [Pumping Lemma for Context-Free Languages] Is B={anbncmdm∣n,m≥0}B = \{a^nb^nc^md^m \mid n, m \ge 0\}B={anbncmdm∣n,m≥0} context-free?

    Yes: S→TUS \to TUS→TU , T→aTb∣ε\ T \to aTb \mid \varepsilon T→aTb∣ε , U→cUd∣ε\ U \to cUd \mid \varepsilon U→cUd∣ε PDA: push aaa 's, pop an aaa for each bbb ; then push ccc 's, pop a ccc for each ddd .

24. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .Is C={anbmcndm∣n,m≥0}C = \{a^nb^mc^nd^m \mid n, m \ge 0\}C={anbmcndm∣n,m≥0} context-free?

    No. Test string anbmcndma^nb^mc^nd^manbmcndm with m,n>pm, n > pm,n>p : vvv and yyy would have to be aaa 's and ccc 's, or bbb 's and ddd 's, and both violate ∣vxy∣≤p|vxy| \le p∣vxy∣≤p . If vvv or yyy contains two kinds of symbol, pumping puts symbols out of order; if vyvyvy changes only one of two equal counts, pumping breaks the equality.

25. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .To show L={ww∣w∈{0,1}∗}L = \{ww \mid w \in \{0, 1\}^*\}L={ww∣w∈{0,1}∗} is not context-free, why is s=0p10p1s = 0^p10^p1s=0p10p1 a bad test string?

    It can be pumped: v=0v = 0v=0 (last 0 of the first block), x=1x = 1x=1 , y=0y = 0y=0 (first 0 of the second block). uvkxykz=0p+k−11 0p+k−11∈Luv^kxy^kz = 0^{p+k-1}1\,0^{p+k-1}1 \in Luvkxykz=0p+k−110p+k−11∈L for all k≥0k \ge 0k≥0 , so no conclusion follows.

26. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .Why is L={ww∣w∈{0,1}∗}L = \{ww \mid w \in \{0, 1\}^*\}L={ww∣w∈{0,1}∗} not context-free? Test string: s=0p1p0p1ps = 0^p1^p0^p1^ps=0p1p0p1p .

    To keep the form wwwwww , vvv and yyy must be identical and in corresponding places of the two halves; these are more than ppp apart, so ∣vxy∣≤p|vxy| \le p∣vxy∣≤p fails. Within ppp symbols, a vvv of 0's can only be followed by a yyy of 1's, and then uv2xy2z∉Luv^2xy^2z \notin Luv2xy2z∈/L .

27. [Pumping Lemma for Context-Free Languages] The pumping lemma says: LLL context-free ⇒\Rightarrow⇒ LLL pumpable. Which of these follow? (a) LLL not pumpable ⇒\Rightarrow⇒ LLL not context-free. (b) LLL pumpable ⇒\Rightarrow⇒ LLL context-free.

    (a) yes (contrapositive); (b) no. Some non-context-free languages are pumpable. To show that LLL is context-free, give a CFG or a PDA.

28. [Pumping Lemma for Context-Free Languages] A={0n1m03n∣n,m≥0}A = \{0^n1^m0^{3n} \mid n, m \ge 0\}A={0n1m03n∣n,m≥0} : how can every s∈As \in As∈A with ∣s∣≥4|s| \ge 4∣s∣≥4 be pumped, and does this prove that AAA is context-free?

    m≥1m \ge 1m≥1 : v=1v = 1v=1 , y=εy = \varepsilony=ε ; m=0m = 0m=0 : v=0v = 0v=0 , y=000y = 000y=000 . This does not prove that AAA is context-free. AAA is context-free because of the CFG S→0S000∣TS \to 0S000 \mid TS→0S000∣T , T→1T∣ε\ T \to 1T \mid \varepsilon T→1T∣ε .The production S→0S000S \to 0S000S→0S000 corresponds to the choice v=0v = 0v=0 , y=000y = 000y=000 ; T→1TT \to 1TT→1T to v=1v = 1v=1 .

29. [Pumping Lemma for Context-Free Languages] Is B={0n10m10n+m∣n,m≥0}B = \{0^n10^m10^{n+m} \mid n, m \ge 0\}B={0n10m10n+m∣n,m≥0} context-free?

    Yes: S→0S0∣1TS \to 0S0 \mid 1TS→0S0∣1T , T→0T0∣1\ T \to 0T0 \mid 1 T→0T0∣1 It is also pumpable with pumping length 4: v=0v = 0v=0 (left or middle block), y=0y = 0y=0 (right block). That alone would not prove it context-free.

30. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .Why is A={an!∣n≥0}A = \{a^{n!} \mid n \ge 0\}A={an!∣n≥0} not context-free? Test string: s=ap!s = a^{p!}s=ap! .

    p!<∣uv2xy2z∣≤p!+p<(p+1)!p! < |uv^2xy^2z| \le p! + p < (p+1)!p!<∣uv2xy2z∣≤p!+p<(p+1)! , so the length of uv2xy2zuv^2xy^2zuv2xy2z is not a factorial. ∣vy∣>0|vy| > 0∣vy∣>0 gives the first inequality, ∣vxy∣≤p|vxy| \le p∣vxy∣≤p the second.

31. [Pumping Lemma for Context-Free Languages] Why is p!+p<(p+1)!p! + p < (p+1)!p!+p<(p+1)! for p≥2p \ge 2p≥2 ?

    (p+1)!=p!+p⋅p!(p+1)! = p! + p \cdot p!(p+1)!=p!+p⋅p! , and p⋅p!>pp \cdot p! > pp⋅p!>p . Example: p=3p = 3p=3 : 3!+3=9<24=4!3! + 3 = 9 < 24 = 4!3!+3=9<24=4! .

32. [Pumping Lemma for Context-Free Languages] Pumping lemma (CFL): if LLL is context-free, there is a ppp such that every s∈Ls \in Ls∈L with ∣s∣≥p|s| \ge p∣s∣≥p is s=uvxyzs = uvxyzs=uvxyz with uvkxykz∈Luv^kxy^kz \in Luvkxykz∈L for all k≥0k \ge 0k≥0 , ∣vy∣>0|vy| > 0∣vy∣>0 , ∣vxy∣≤p|vxy| \le p∣vxy∣≤p .Why is B={an2∣n≥0}B = \{a^{n^2} \mid n \ge 0\}B={an2∣n≥0} not context-free? Test string: s=ap2s = a^{p^2}s=ap2 .

    p2<∣uv2xy2z∣≤p2+p<(p+1)2p^2 < |uv^2xy^2z| \le p^2 + p < (p+1)^2p2<∣uv2xy2z∣≤p2+p<(p+1)2 , so the length of uv2xy2zuv^2xy^2zuv2xy2z is not a square. (p+1)2=p2+2p+1>p2+p(p+1)^2 = p^2 + 2p + 1 > p^2 + p(p+1)2=p2+2p+1>p2+p .

33. [Closure Properties of CFLs] AAA and BBB are CFLs with start variables S1S_1S1​ and S2S_2S2​ . How do you get CFGs for A∪BA \cup BA∪B , A∘BA \circ BA∘B and A∗A^*A∗ ?

    Union A∪BA \cup BA∪B New start variable S0→S1∣S2S_0 \to S_1 \mid S_2S0​→S1​∣S2​ , plus all productions of both grammars. Example: S1→aS1b∣εS_1 \to aS_1b \mid \varepsilonS1​→aS1​b∣ε , S2→cS2∣εS_2 \to cS_2 \mid \varepsilonS2​→cS2​∣ε give {anbn}∪{cm}\{a^nb^n\} \cup \{c^m\}{anbn}∪{cm} . Concatenation A∘BA \circ BA∘B S0→S1S2S_0 \to S_1S_2S0​→S1​S2​ , plus all productions of both grammars. Example: with the same S1S_1S1​ , S2S_2S2​ : {anbncm∣n,m≥0}\{a^nb^nc^m \mid n, m \ge 0\}{anbncm∣n,m≥0} . Star A∗…

34. [Closure Properties of CFLs] Combining CFGs for AAA and BBB into a CFG for A∪BA \cup BA∪B or A∘BA \circ BA∘B : what condition must the two sets of variables satisfy?

    They must be disjoint; if necessary, rename some variables. Otherwise productions of one grammar could be applied to variables of the other.

35. [Closure Properties of CFLs] Is the class of context-free languages closed under intersection?

    No. {anbncm∣n,m≥0}\{a^nb^nc^m \mid n, m \ge 0\}{anbncm∣n,m≥0} and {anbmcm∣n,m≥0}\{a^nb^mc^m \mid n, m \ge 0\}{anbmcm∣n,m≥0} are CFLs, but their intersection {anbncn∣n≥0}\{a^nb^nc^n \mid n \ge 0\}{anbncn∣n≥0} is not.

36. [Closure Properties of CFLs] Why is the class of context-free languages not closed under complement?

    Otherwise for CFLs A,BA, BA,B , also A‾∪B‾‾=A∩B\overline{\overline{A} \cup \overline{B}} = A \cap BA∪B=A∩B would be a CFL, but CFLs are not closed under intersection. Closure under union is used for A‾∪B‾\overline{A} \cup \overline{B}A∪B .

37. [Closure Properties of CFLs] Regular languages are closed under union, concatenation, star, intersection and complement; context-free languages are closed only under union, concatenation and star.

38. [Exercises] Is L={anbmc2nd2m∣m,n≥0}L = \{a^nb^mc^{2n}d^{2m} \mid m, n \ge 0\}L={anbmc2nd2m∣m,n≥0} context-free?

    No. Test string apbpc2pd2pa^pb^pc^{2p}d^{2p}apbpc2pd2p . vvv , yyy each hold one kind of symbol, and ∣vxy∣≤p|vxy| \le p∣vxy∣≤p means vxyvxyvxy cannot reach both the aaa 's and the ccc 's, nor both the bbb 's and the ddd 's. So pumping changes a count without its partner.

39. [Exercises] Is L={anbmcn−md3∣n>m≥0}L = \{a^nb^mc^{n-m}d^3 \mid n > m \ge 0\}L={anbmcn−md3∣n>m≥0} context-free?

    Yes: S→AdddS \to AdddS→Addd , A→aAc∣aBc\ A \to aAc \mid aBc A→aAc∣aBc , B→aBb∣ε\ B \to aBb \mid \varepsilon B→aBb∣ε anbmcn−m=an−m(ambm)cn−ma^nb^mc^{n-m} = a^{n-m}(a^mb^m)c^{n-m}anbmcn−m=an−m(ambm)cn−m , with n−m≥1n - m \ge 1n−m≥1 .

40. [Exercises] Is L={0n1m∣m>n+4}L = \{0^n1^m \mid m > n + 4\}L={0n1m∣m>n+4} context-free?

    Yes: S→0S1∣TS \to 0S1 \mid TS→0S1∣T , T→1T∣11111\ T \to 1T \mid 11111 T→1T∣11111 0n1m0^n1^m0n1m with m≥n+5m \ge n + 5m≥n+5 is 0n 1m−n−5 11111 1n0^n\,1^{m-n-5}\,11111\,1^n0n1m−n−5111111n .

41. [Exercises] Is L={0n1m∣m=n2}L = \{0^n1^m \mid m = n^2\}L={0n1m∣m=n2} context-free?

    No. Test string 0p1p20^p1^{p^2}0p1p2 . If vyvyvy has only 0's or only 1's, one count changes alone. If v=0tv = 0^tv=0t , y=1uy = 1^uy=1u ( t,u≥1t, u \ge 1t,u≥1 ): (p+t)2=p2+2pt+t2>p2+u(p+t)^2 = p^2 + 2pt + t^2 > p^2 + u(p+t)2=p2+2pt+t2>p2+u , since u≤pu \le pu≤p . So uv2xy2z∉Luv^2xy^2z \notin Luv2xy2z∈/L .

42. [Exercises] Is L={0n1m∣n≠m}L = \{0^n1^m \mid n \ne m\}L={0n1m∣n=m} context-free?

    Yes: S→0S1∣A∣BS \to 0S1 \mid A \mid BS→0S1∣A∣B , A→0A∣0\ A \to 0A \mid 0 A→0A∣0 , B→B1∣1\ B \to B1 \mid 1 B→B1∣1 0k 0j 1k0^k\,0^j\,1^k0k0j1k or 0k 1j 1k0^k\,1^j\,1^k0k1j1k with j≥1j \ge 1j≥1 extra symbols.

43. [Exercises] Is L={anbmcn∣n odd,m even}L = \{a^nb^mc^n \mid n \text{ odd}, m \text{ even}\}L={anbmcn∣n odd,m even} context-free?

    Yes: S→aaScc∣aTcS \to aaScc \mid aTcS→aaScc∣aTc , T→bTb∣ε\ T \to bTb \mid \varepsilon T→bTb∣ε aaSccaaSccaaScc adds 2 to nnn , aTcaTcaTc makes nnn odd, bTbbTbbTb adds 2 to mmm .

44. [Exercises] Is L={akbmcn∣n>m and n>k}L = \{a^kb^mc^n \mid n > m \text{ and } n > k\}L={akbmcn∣n>m and n>k} context-free?

    No. Test string apbpcp+1a^pb^pc^{p+1}apbpcp+1 . If vyvyvy contains ccc 's, it contains no aaa 's ( ∣vxy∣≤p|vxy| \le p∣vxy∣≤p ); pump down: n≤p=kn \le p = kn≤p=k . Otherwise pump up: kkk or mmm becomes ≥p+1=n\ge p + 1 = n≥p+1=n .

45. [Exercises] Is L={akbmcn∣k>m>n>0}L = \{a^kb^mc^n \mid k > m > n > 0\}L={akbmcn∣k>m>n>0} context-free?

    No. Test string ap+2bp+1cpa^{p+2}b^{p+1}c^pap+2bp+1cp . If vyvyvy contains aaa 's, pump down: k≤mk \le mk≤m or m≤p=nm \le p = nm≤p=n . If vyvyvy contains bbb 's but no aaa 's, pump up: m≥km \ge km≥k . If vyvyvy has only ccc 's, pump up: n≥mn \ge mn≥m .

46. [Exercises] Is L={akbmcn∣n=k+2m+1}L = \{a^kb^mc^n \mid n = k + 2m + 1\}L={akbmcn∣n=k+2m+1} context-free?

    Yes: S→aSc∣TS \to aSc \mid TS→aSc∣T , T→bTcc∣c\ T \to bTcc \mid c T→bTcc∣c akbmcn=ak bm c c2m cka^kb^mc^n = a^k\,b^m\,c\,c^{2m}\,c^kakbmcn=akbmcc2mck .

47. [Exercises] Is L={anbm∣n+m=4}L = \{a^nb^m \mid n + m = 4\}L={anbm∣n+m=4} context-free?

    Yes: S→aaaa∣aaab∣aabb∣abbb∣bbbbS \to aaaa \mid aaab \mid aabb \mid abbb \mid bbbbS→aaaa∣aaab∣aabb∣abbb∣bbbb Every finite language is context-free (and regular).

48. [Exercises] Is L={akbmcmbncnak∣k,m,n≥0}L = \{a^kb^mc^mb^nc^na^k \mid k, m, n \ge 0\}L={akbmcmbncnak∣k,m,n≥0} context-free?

    Yes: S→aSa∣ABS \to aSa \mid ABS→aSa∣AB , A→bAc∣ε\ A \to bAc \mid \varepsilon A→bAc∣ε , B→bBc∣ε\ B \to bBc \mid \varepsilon B→bBc∣ε The outer aaa 's match like anbmcmdna^nb^mc^md^nanbmcmdn ; inside, two independent blocks bmcmb^mc^mbmcm and bncnb^nc^nbncn .

49. [Exercises] Is L={anbmcnm∣m,n≥1}L = \{a^nb^mc^{nm} \mid m, n \ge 1\}L={anbmcnm∣m,n≥1} context-free?

    No. Test string apbpcp2a^pb^pc^{p^2}apbpcp2 . If v=btv = b^tv=bt , y=cuy = c^uy=cu with t≥1t \ge 1t≥1 : p(p+t)=p2+ptp(p+t) = p^2 + ptp(p+t)=p2+pt but only u≤p−t<ptu \le p - t < ptu≤p−t<pt ccc 's are added. Changing only aaa 's and bbb 's, or only one block, also breaks ccc -count =nm= nm=nm .