Ch.8: Pushdown Automata

Week 8 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 8.1. Operation of a PDA 8.2. PDA - CFG equivalence

53 flashcards · Computer Science · by lakesare

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

1. [Operation of a PDA] Why can no NFA recognize {anbn∣n≥0}\{a^n b^n \mid n \ge 0\}{anbn∣n≥0} ?

   An NFA has no memory apart from its finitely many states, so it cannot count the aaa 's. A pushdown automaton adds memory (a stack) to an NFA for this reason.

2. [Operation of a PDA] A stack is a LIFO memory: last in, first out.

   Only the symbol on top of the stack can be read.

3. [Operation of a PDA] What are pushing and popping on a stack?

   Pushing Writing a symbol on top of the stack. Example: pushing 1 onto the stack 0 10\,101 (top on the right) gives 0 1 10\,1\,1011 . Popping Reading the symbol on top of the stack, which removes it. Example: popping 0 1 10\,1\,1011 reads 1 and leaves 0 10\,101 .

4. [Operation of a PDA] Informally, what is a pushdown automaton (PDA)?

   An NFA plus a stack of unlimited size. The control unit reads the input and pushes symbols to and pops symbols from the stack.

5. [Operation of a PDA] What is the special symbol $\text{\textdollar}$ that a PDA pushes at the beginning of its computation for?

   To test whether the stack is at its bottom (empty apart from that symbol). A transition ε,$→ε\varepsilon, \text{\textdollar} \to \varepsilonε,$→ε can be taken only when $\text{\textdollar}$ is on top, i.e. when everything pushed after it has been popped.

6. [Operation of a PDA] A PDA chooses its next move based on what three things?

   The current state, the input symbol and the symbol on top of the stack. An NFA uses only the first two. The input symbol and the stack symbol may also be ε\varepsilonε (nothing read).

7. [Operation of a PDA] What is the formal definition of a pushdown automaton (PDA)?

   A 6-tuple (Q,Σ,Γ,δ,q0,F)(Q, \Sigma, \Gamma, \delta, q_0, F)(Q,Σ,Γ,δ,q0​,F) , where Q,Σ,Γ,FQ, \Sigma, \Gamma, FQ,Σ,Γ,F are finite sets and: QQQ is the set of states, Σ\SigmaΣ is the input alphabet, Γ\GammaΓ is the stack alphabet, δ\deltaδ is the transition function, q0∈Qq_0 \in Qq0​∈Q is the start state, F⊆QF \subseteq QF⊆Q is the set of accept states.

8. [Operation of a PDA] A PDA has states QQQ , input alphabet Σ\SigmaΣ and stack alphabet Γ\GammaΓ . What are the domain and codomain of its transition function δ\deltaδ ?

   δ:Q×(Σ∪{ε})×(Γ∪{ε})→P(Q×(Γ∪{ε}))\boldsymbol{\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \to \mathcal{P}(Q \times (\Gamma \cup \{\varepsilon\}))}δ:Q×(Σ∪{ε})×(Γ∪{ε})→P(Q×(Γ∪{ε})) Arguments: a state, an input symbol or ε\varepsilonε , a symbol to pop or ε\varepsilonε . Value: a set of pairs (next state, symbol to push or ε\varepsilonε ). It is a set because a PDA is nondeterministic.

9. [Operation of a PDA] Must the input alphabet Σ\SigmaΣ and the stack alphabet Γ\GammaΓ of a PDA be different?

   No, they may or may not be the same. Different alphabets make a PDA easier to read.Example: Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} , Γ={$,0,1}\Gamma = \{\text{\textdollar}, 0, 1\}Γ={$,0,1} .

10. [Operation of a PDA] A PDA has Σ={a,b,c}\Sigma = \{a, b, c\}Σ={a,b,c} and Γ={$,0,1}\Gamma = \{\text{\textdollar}, 0, 1\}Γ={$,0,1} . What does δ(q1,a,1)={(q2,0),(q3,ε)}\delta(q_1, a, 1) = \{(q_2, 0), (q_3, \varepsilon)\}δ(q1​,a,1)={(q2​,0),(q3​,ε)} mean?

    In state q1q_1q1​ , reading aaa and popping 1: go to q2q_2q2​ and push 0, or go to q3q_3q3​ and push nothing.

11. [Operation of a PDA] In the state diagram of a PDA, what does the label a,b→ca, b \to ca,b→c on an arrow from state ppp to state qqq mean?

    Read aaa from the input, pop bbb from the stack, push ccc to the stack, and move from ppp to qqq . Each of a,b,ca, b, ca,b,c may be ε\varepsilonε : then nothing is read, popped or pushed.Example: a loop b,a→cb, a \to cb,a→c at ppp reads bbb and replaces the top symbol aaa by ccc .

12. [Operation of a PDA] A PDA in state ppp has an arrow to qqq labelled a,b→εa, b \to \varepsilona,b→ε . The next input symbol is not aaa , or the top of the stack is not bbb . What happens to this branch of the computation?

    It stops and does not accept (the book says the branch dies). Other branches of the nondeterministic computation may continue.

13. [Operation of a PDA] Which PDA transition label describes a move just like an NFA's move on input aaa ?

    a,ε→ε\boldsymbol{a, \varepsilon \to \varepsilon}a,ε→ε : read aaa , push and pop nothing.

14. [Operation of a PDA] What do these PDA transition labels do (on an arrow from ppp to qqq )?

    a,ε→ca, \varepsilon \to ca,ε→c Read aaa , push ccc , move to qqq ; the stack is not read. ε,b→c\varepsilon, b \to cε,b→c Read no input, pop bbb , push ccc , move to qqq . ε,b→ε\varepsilon, b \to \varepsilonε,b→ε Read no input, pop bbb , push nothing, move to qqq .

15. [Operation of a PDA] Give a PDA that recognizes {anbn∣n≥0}\{a^n b^n \mid n \ge 0\}{anbn∣n≥0} .

    Push $\text{\textdollar}$ ; push 1 for each aaa ; pop 1 for each bbb ; pop $\text{\textdollar}$ and accept.

16. [Operation of a PDA] A PDA for {anbn∣n≥0}\{a^n b^n \mid n \ge 0\}{anbn∣n≥0} pushes $\text{\textdollar}$ , pushes 1 for each aaa , pops 1 for each bbb , and enters the accept state with ε,$→ε\varepsilon, \text{\textdollar} \to \varepsilonε,$→ε .Why must the last move be ε,$→ε\varepsilon, \text{\textdollar} \to \varepsilonε,$→ε ?

    It can be taken only after every pushed 1 has been popped, i.e. when there are as many bbb 's as aaa 's. Example: on aabaabaab one 1 is still on the stack after the input, so the PDA cannot reach the accept state.

17. [Operation of a PDA] Give a PDA that recognizes {wwR∣w∈{0,1}∗}\{ww^R \mid w \in \{0, 1\}^*\}{wwR∣w∈{0,1}∗} , where wRw^RwR is the reverse of www .

    Push each symbol of the first half; then for each symbol of the second half, pop the same symbol. These are the even palindromes. The stack gives the symbols back in reverse order.

18. [Operation of a PDA] A PDA for {wwR∣w∈{0,1}∗}\{ww^R \mid w \in \{0, 1\}^*\}{wwR∣w∈{0,1}∗} pushes the symbols of the first half and pops a matching symbol for each symbol of the second half.How does the PDA know where the middle of the input is?

    It guesses, using nondeterminism: the move ε,ε→ε\varepsilon, \varepsilon \to \varepsilonε,ε→ε to the popping state can be taken at any point. Only a branch that guesses the true middle can reach the accept state.

19. [Operation of a PDA] Give a PDA that recognizes {anbmc2n∣m,n≥0}\{a^n b^m c^{2n} \mid m, n \ge 0\}{anbmc2n∣m,n≥0} .

    Push 1 for each aaa , read the bbb 's without using the stack, pop one 1 for every two ccc 's.

20. [Operation of a PDA] Which language does this PDA recognize?

    {anbc3n∣n≥0}\boldsymbol{\{a^n b c^{3n} \mid n \ge 0\}}{anbc3n∣n≥0} It pushes $\text{\textdollar}$ , pushes 1 for each aaa , reads one bbb , then pops one 1 for every three ccc 's on the triangle, and accepts when $\text{\textdollar}$ is on top.

21. [Operation of a PDA] How can a PDA recognize the strings over {0,1}\{0, 1\}{0,1} with equal numbers of 0's and 1's?

    Keep the surplus on the stack: while 1's outnumber 0's, push 1's and pop one per 0; while 0's outnumber 1's, push 0's and pop one per 1. State q3q_3q3​ : so far, number of 0's ≥\ge≥ number of 1's. State q4q_4q4​ : so far, number of 1's ≥\ge≥ number of 0's.

22. [Operation of a PDA] Give a PDA with three states that recognizes the strings over {0,1}\{0, 1\}{0,1} with equal numbers of 0's and 1's.

    One middle state with four loops: 0,ε→00, \varepsilon \to 00,ε→0 ; 0,1→ε\ 0, 1 \to \varepsilon 0,1→ε ; 1,ε→1\ 1, \varepsilon \to 1 1,ε→1 ; 1,0→ε\ 1, 0 \to \varepsilon 1,0→ε . This design uses nondeterminism: a 0 may push a 0 even when a 1 is on top.

23. [Operation of a PDA] A PDA pushes $\text{\textdollar}$ , then in one state reads the input with the loops 0,ε→00, \varepsilon \to 00,ε→0 ; 0,1→ε0, 1 \to \varepsilon0,1→ε ; 1,ε→11, \varepsilon \to 11,ε→1 ; 1,0→ε1, 0 \to \varepsilon1,0→ε , and accepts after ε,$→ε\varepsilon, \text{\textdollar} \to \varepsilonε,$→ε .Why does every accepted string have equally many 0's and 1's?

    Each 0 pushes a 0 or pops a 1, each 1 pushes a 1 or pops a 0, and reaching $\text{\textdollar}$ means every pushed symbol was popped. So number of 0's = (0's pushed) + (1's popped) = (0's popped) + (1's pushed) = number of 1's.

24. [Operation of a PDA] Give a PDA that recognizes the palindromes of odd length over {0,1}\{0, 1\}{0,1} .

    Push the first half, read the middle symbol without using the stack ( 0,ε→ε0, \varepsilon \to \varepsilon0,ε→ε or 1,ε→ε1, \varepsilon \to \varepsilon1,ε→ε ), pop a matching symbol per symbol of the second half.

25. [Operation of a PDA] Give a PDA that recognizes all palindromes over {0,1}\{0, 1\}{0,1} .

    As for even palindromes, but the move to the popping state is ε,ε→ε\varepsilon, \varepsilon \to \varepsilonε,ε→ε , 0,ε→ε0, \varepsilon \to \varepsilon0,ε→ε or 1,ε→ε1, \varepsilon \to \varepsilon1,ε→ε . The middle move reads no symbol (even length) or one symbol (odd length).

26. [Operation of a PDA] Give a PDA that recognizes {akbmcn∣k,m,n≥0 and (k=m or k=n)}\{a^k b^m c^n \mid k, m, n \ge 0 \text{ and } (k = m \text{ or } k = n)\}{akbmcn∣k,m,n≥0 and (k=m or k=n)} .

    Push the aaa 's, then branch nondeterministically: one branch pops an aaa per bbb , the other pops an aaa per ccc . The two branches are two machines in parallel, each checking one of the two conditions.

27. [PDA - CFG equivalence] Which languages are recognized by some PDA?

    Exactly the context-free languages. Theorem: a language is context-free if and only if some PDA recognizes it. So from a CFG we can find an equivalent PDA, and from a PDA an equivalent CFG.This is the same relation as between regular expressions and NFAs.

28. [PDA - CFG equivalence] How does the characterization "context-free = recognized by a PDA" show that every regular language is context-free?

    Every NFA is a PDA that does not use its stack, so a language recognized by an NFA is recognized by a PDA. It also follows from regular grammars being a special kind of CFG.

29. [PDA - CFG equivalence] Which of a∗a^*a∗ , {anbn∣n≥0}\{a^n b^n \mid n \ge 0\}{anbn∣n≥0} , {anbncn∣n≥0}\{a^n b^n c^n \mid n \ge 0\}{anbncn∣n≥0} are regular, and which are context-free?

    a∗a^*a∗ : regular. anbna^n b^nanbn : context-free, not regular. anbncna^n b^n c^nanbncn : not context-free.

30. [PDA - CFG equivalence] Is {anbmcmdn∣n,m≥0}\{a^n b^m c^m d^n \mid n, m \ge 0\}{anbmcmdn∣n,m≥0} context-free? If so, give a CFG.

    Yes: S→aSd∣TS \to aSd \mid TS→aSd∣T , T→bTc∣ε\ T \to bTc \mid \varepsilon T→bTc∣ε . A PDA: push the aaa 's, push the bbb 's, pop a bbb per ccc , pop an aaa per ddd .

31. [PDA - CFG equivalence] Is {anbmcndm∣n,m≥0}\{a^n b^m c^n d^m \mid n, m \ge 0\}{anbmcndm∣n,m≥0} context-free?

    No. Informally: a PDA can push the aaa 's and then the bbb 's, but when the ccc 's come, the aaa 's are below the bbb 's and cannot be read. (A formal proof uses the pumping lemma for context-free languages.)

32. [PDA - CFG equivalence] Is {anbncmdm∣n,m≥0}\{a^n b^n c^m d^m \mid n, m \ge 0\}{anbncmdm∣n,m≥0} context-free? If so, give a CFG.

    Yes: S→ACS \to ACS→AC , A→aAb∣ε\ A \to aAb \mid \varepsilon A→aAb∣ε , C→cCd∣ε\ C \to cCd \mid \varepsilon C→cCd∣ε . A PDA: push 0 per aaa , pop 0 per bbb , push 1 per ccc , pop 1 per ddd .

33. [PDA - CFG equivalence] Is {anbncn∣n≥0}\{a^n b^n c^n \mid n \ge 0\}{anbncn∣n≥0} context-free?

    No. Informally: the stack can store the number of aaa 's and compare it with the number of bbb 's, but after that the stack is empty when the ccc 's come.

34. [PDA - CFG equivalence] Is {akbmcn∣k>m>n}\{a^k b^m c^n \mid k > m > n\}{akbmcn∣k>m>n} context-free?

    No. Informally: one stack is not enough to compare the aaa 's with the bbb 's and then the bbb 's with the ccc 's.

35. [PDA - CFG equivalence] Is {anbm∣n≤m≤2n}\{a^n b^m \mid n \le m \le 2n\}{anbm∣n≤m≤2n} context-free? If so, give a CFG.

    Yes: S→aSb∣aSbb∣εS \to aSb \mid aSbb \mid \varepsilonS→aSb∣aSbb∣ε . A PDA: push 1 per aaa ; then pop each 1 with one bbb or with two bbb 's (chosen nondeterministically).

36. [PDA - CFG equivalence] Is {anb2mcn+1∣n,m≥0}\{a^n b^{2m} c^{n+1} \mid n, m \ge 0\}{anb2mcn+1∣n,m≥0} context-free? If so, give a CFG.

    Yes: S→aSc∣TS \to aSc \mid TS→aSc∣T , T→bbT∣c\ T \to bbT \mid c T→bbT∣c . A PDA: push 1 per aaa , read the bbb 's in pairs without using the stack, pop 1 per ccc , pop $\text{\textdollar}$ , then read one more ccc .

37. [PDA - CFG equivalence] Which language does this PDA recognize?

    {1n+10m10m1n+1∣n,m≥0}\boldsymbol{\{1^{n+1} 0^m 1 0^m 1^{n+1} \mid n, m \ge 0\}}{1n+10m10m1n+1∣n,m≥0} At least one 1, any number of 0's, a single 1, and then the mirror image of the beginning.

38. [PDA - CFG equivalence] Give a CFG for {1n+10m10m1n+1∣n,m≥0}\{1^{n+1} 0^m 1 0^m 1^{n+1} \mid n, m \ge 0\}{1n+10m10m1n+1∣n,m≥0} .

    S→1S1∣1A1, A→0A0∣1\boldsymbol{S \to 1S1 \mid 1A1, \ \ A \to 0A0 \mid 1}S→1S1∣1A1, A→0A0∣1 Example: S⇒1A1⇒10A01⇒10101S \Rightarrow 1A1 \Rightarrow 10A01 \Rightarrow 10101S⇒1A1⇒10A01⇒10101 ( n=0n = 0n=0 , m=1m = 1m=1 ).

39. [Exercises] Construct a PDA that recognizes {a2nbn∣n≥0}\{a^{2n} b^n \mid n \ge 0\}{a2nbn∣n≥0} .

    Push 1 per aaa ; for each bbb , pop two 1's. Each bbb pops one 1, and an ε\varepsilonε -move pops a second one.

40. [Exercises] Construct a PDA that recognizes {anbm∣n≠m}\{a^n b^m \mid n \ne m\}{anbm∣n=m} .

    Match the bbb 's against the aaa 's on the stack; accept if the input ends with unmatched aaa 's ( n>mn > mn>m ) or has unmatched bbb 's ( m>nm > nm>n ). Here the first aaa pushes $\text{\textdollar}$ and each later aaa pushes 1, so b,$→εb, \text{\textdollar} \to \varepsilonb,$→ε reads the nnn -th bbb . The left path accepts bmb^mbm with m≥1m \ge 1m≥1 .

41. [Exercises] Construct a PDA that recognizes {w∈{a,b}∗∣w\{w \in \{a, b\}^* \mid w{w∈{a,b}∗∣w has odd length and its middle symbol is a}a\}a} .

    Push 1 per symbol, guess the middle aaa and read it without using the stack, then pop 1 per symbol.

42. [Exercises] Construct a PDA that recognizes {anb2n−1∣n≥1}\{a^n b^{2n-1} \mid n \ge 1\}{anb2n−1∣n≥1} .

    Read the first aaa without pushing, push 1 per further aaa ; read one bbb , then pop one 1 per two further bbb 's. Number of bbb 's: 1+2(n−1)=2n−11 + 2(n - 1) = 2n - 11+2(n−1)=2n−1 .

43. [Exercises] Construct a PDA that recognizes {akbℓc dmen∣k+ℓ=m+n}\{a^k b^\ell c\, d^m e^n \mid k + \ell = m + n\}{akbℓcdmen∣k+ℓ=m+n} .

    Push 1 per aaa and per bbb , read the ccc , pop 1 per ddd and per eee .

44. [Exercises] Construct a PDA that recognizes {an(bc)2man+m∣n,m≥0}\{a^n (bc)^{2m} a^{n+m} \mid n, m \ge 0\}{an(bc)2man+m∣n,m≥0} .

    Push 1 per aaa , push 1 per bcbcbcbcbcbc , pop 1 per aaa at the end.

45. [Exercises] Construct a PDA that recognizes {anbmc2n+3m∣n,m≥0}\{a^n b^m c^{2n+3m} \mid n, m \ge 0\}{anbmc2n+3m∣n,m≥0} .

    Push two 1's per aaa and three 1's per bbb ; pop one 1 per ccc . The extra 1's are pushed by ε\varepsilonε -moves.

46. [Exercises] Which language does this PDA recognize?

    {anbm∣n>m}\boldsymbol{\{a^n b^m \mid n > m\}}{anbm∣n>m} It pushes 1 per aaa and pops 1 per bbb ; the last move ε,1→ε\varepsilon, 1 \to \varepsilonε,1→ε needs at least one 1 left on the stack.

47. [Exercises] Which language does this PDA recognize?

    {ambm+ncn∣m,n≥0}\boldsymbol{\{a^m b^{m+n} c^n \mid m, n \ge 0\}}{ambm+ncn∣m,n≥0} The first mmm bbb 's pop the aaa 's; ε,$→$\varepsilon, \text{\textdollar} \to \text{\textdollar}ε,$→$ checks that all aaa 's are popped; the other bbb 's are pushed and popped by the ccc 's.

48. [Exercises] Which language does this PDA recognize?

    {akbmcn∣k,m,n≥1}\boldsymbol{\{a^k b^m c^n \mid k, m, n \ge 1\}}{akbmcn∣k,m,n≥1} This PDA never uses its stack: it is actually a DFA.

49. [Exercises] Which language does this PDA recognize?

    {anbmc dn+m+1∣m,n≥0}\boldsymbol{\{a^n b^m c\, d^{n+m+1} \mid m, n \ge 0\}}{anbmcdn+m+1∣m,n≥0} 1 is pushed per aaa and per bbb ; the first ddd is read without popping.

50. [Exercises] Which language does this PDA recognize?

    Strings over {a,b}\{a, b\}{a,b} with equally many aaa 's and bbb 's, where every prefix has at least as many aaa 's as bbb 's. Like balanced parentheses, with aaa as "(" and bbb as ")".Example: aabbabaabbabaabbab is accepted; abbaabbaabba is not (the prefix abbabbabb has more bbb 's).

51. [Exercises] Which of these languages {akbℓcmdn∣… }\{a^k b^\ell c^m d^n \mid \dots\}{akbℓcmdn∣…} are context-free? a) k+ℓ+m≥nk + \ell + m \ge nk+ℓ+m≥n \quad b) k<ℓ<m<nk < \ell < m < nk<ℓ<m<n \quad c) k>ℓk > \ellk>ℓ and m>nm > nm>n \quad d) m=2km = 2km=2k and n=3ℓn = 3\elln=3ℓ

    a) and c). a) A PDA pushes for a,b,ca, b, ca,b,c , pops for ddd , and accepts if the stack is not emptied.c) A PDA pushes for aaa and pops for bbb (some symbols must remain), then does the same for ccc and ddd .b) and d) are not context-free: their comparisons are chained or crossed, which one stack cannot do.

52. [Exercises] Give a CFG for {akbℓcmdn∣k+ℓ+m≥n}\{a^k b^\ell c^m d^n \mid k + \ell + m \ge n\}{akbℓcmdn∣k+ℓ+m≥n} .

    S→aSd∣AT, T→bTd∣BU, U→cUd∣C, A→aA∣ε, B→bB∣ε, C→cC∣ε\boldsymbol{S \to aSd \mid AT, \ T \to bTd \mid BU, \ U \to cUd \mid C, \ A \to aA \mid \varepsilon, \ B \to bB \mid \varepsilon, \ C \to cC \mid \varepsilon}S→aSd∣AT, T→bTd∣BU, U→cUd∣C, A→aA∣ε, B→bB∣ε, C→cC∣ε Each ddd is generated together with an aaa , bbb or ccc ; AAA , BBB , CCC generate the extra aaa 's, bbb 's and ccc 's.

53. [Exercises] Give a CFG for {akbℓcmdn∣k>ℓ and m>n}\{a^k b^\ell c^m d^n \mid k > \ell \text{ and } m > n\}{akbℓcmdn∣k>ℓ and m>n} .

    S→TU, T→aTb∣A, U→cUd∣C, A→aA∣a, C→cC∣c\boldsymbol{S \to TU, \ T \to aTb \mid A, \ U \to cUd \mid C, \ A \to aA \mid a, \ C \to cC \mid c}S→TU, T→aTb∣A, U→cUd∣C, A→aA∣a, C→cC∣c TTT generates akbℓa^k b^\ellakbℓ with k>ℓk > \ellk>ℓ , and UUU generates cmdnc^m d^ncmdn with m>nm > nm>n .