Finite automata can accept regular languages, so we have to extend its definition so as it could accept context-free languages. The solution for this problem is to add a stack memory to a finite automaton, and the name of this solution is "pushdown automaton". The formal definition is the following:
Definition 22. A pushdown automaton (PDA) is the following 7-tuple:
PDA = (Q, T, Z, q0, z0, δ, F)
where
Q is the finite nonempty set of the states,
T is the set of the input letters (finite nonempty alphabet),
Z is the set of the stack symbols (finite nonempty alphabet),
q0 is the initial state, q0 ∈ Q,
z0 is the initial stack symbol, z0 ∈ Z,
δ is the transition function having a form Q × {T ∪ {λ}} × Z → 2Q×Z*, and
F is the set of the final states, F ⊆ Q.
In order to understand the operating principle of the pushdown automaton, we have to understand the operations of finite automata and the stack memory. Finite automata were introduced in Chapter 2, and we studied them through many pages. The stack is a LIFO (last in first out) memory, which has two operations, PUSH and POP. When we use the POP operation, we read the top letter of the stack, and at the same time we delete it. When we use the PUSH operation, we add a word to the top of the stack.
The pushdown automaton accepts words over the alphabet T. At the beginning the PDA is in state q0, we can read the first letter of the input word, and the stack contains only z0. In each step, we use the transition function to change the state and the stack of the PDA. The PDA accepts the input word, if and only if it can read the whole word, and it is in a final state when the end of the input word is reached.
More formally, in each step, the pushdown automaton has a configuration - also called instantaneous description - (q,v,w), where q ∈ Q is the current state, v ∈ T* is the unread part of the input word, and w ∈ Z* is the whole word contained by the stack. At the beginning, the pushdown automaton is in its initial configuration: (q0, p, z0), where p is the whole input word. In each step, the pushdown automaton changes its configuration, while using the transition function. There are two different kinds of steps, the first is the standard, the second is the so called λ-step.
The standard step is when the PDA reads its current state, current input letter, the top stack symbol, it finds an appropriate transition rule, it changes its state, it moves to the next input letter and changes the top symbol of the stack to the appropriate word. Formally, we can say the PDA can change its configuration from (q1, av, zw) to (q2, v, rw) in one step, if it has a transition rule (q2, r) ∈ δ (q1, a, z), where q1, q2 ∈ Q, a ∈ T, z ∈ Z, v ∈ T*, w ∈ Z*. Denote this transition (q1, av, zw) ⊦PDA (q2, v, rw).
The λ-step is when the PDA reads its current state, it does not read any input letters, it reads the top stack symbol, it finds an appropriate transition rule, and it changes its state, it does not move to the next input letter and it changes the top letter of the stack to the given word. Formally, we can say again that the PDA can change its configuration from (q1, v, zw) to (q2, v, rw) in one step, if it has a transition rule (q2, r) ∈ δ (q1, λ, z), where q1, q2 ∈ Q, z ∈ Z, v ∈ T*, and w ∈ Z*. Mark: (q1, v, zw) ⊦PDA (q2, v, rw).
We can say that the PDA can change its configuration from (q1, v, w) to (q2, x, y) in finite many steps, if there are configurations C0, C1,..., Cn such that C0 = (q1, v, w), Cn = (q2, x, y), and Ci ⊦PDA Ci+1 holds for each integer 0 ≤ i < n. Mark: (q1, v, w) ⊦*PDA (q2, x, y).
Finally, we can define the language accepted by the pushdown automaton:
L(PDA) = {p∣p ∈ T*, (q0, p, z0) ⊦*PDA (qf, λ, y), qf ∈ F, y ∈ Z*}.
Example 47. This simple example shows the description of a pushdown automaton which accepts the language L = {aibicjdj∣i, j ≥ 1}.
PDA = ({q0,q1,q2,q3,q4,q5},{a,b,c,d},{x,z0},q0,z0,δ,{q5}), δ(q0,a,z0) = {(q1,xz0)}, δ(q1,a,x) = {(q1,xx)}, δ(q1,b,x) = {(q2,λ)}, δ(q2,b,x) = {(q2,λ)}, δ(q2,c,z0) = {(q3,xz0)}, δ(q3,c,x) = {(q3,xx)}, δ(q3,d,x) = {(q4,λ}, δ(q4,d,x) = {(q4,λ)}, δ(q4,λ,z0) = {(q5,z0)}.
The Figure 4.6. shows the graphical notation of this pushdown automaton.
Example 48. This example shows the description of a pushdown automaton which accepts the language of words over the alphabet {a,b} containing more a's than b's.
PDA = ({q0,qa,qb},{a,b},{1,z0},q0,z0,δ,{qa}), δ(q0,a,z0) = {(qa,z0)}, δ(q0,b,z0) = {(qb,z0)}, δ(qa,a,z0) = {(qa,1z0)}, δ(qa,a,1) = {(qa,11)}, δ(qa,b,1) = {(qa,λ)}, δ(qa,b,z0) = {(q0,z0)}, δ(qb,b,z0) = {(qb,1z0)}, δ(qb,b,1) = {(qb,11)}, δ(qb,a,1) = {(qb,λ)}, δ(qb,a,z0) = {(q0,z0)}.
The Figure 4.7. shows the graphical notation of this pushdown automaton.
Exercise 64. Create a pushdown automaton, which accepts the language L = {aibj∣0 ≤ i ≤ j ≤ 2i}.
Exercise 65. Create a pushdown automaton, which accepts the language L = {aibjck∣i = j or j = k}.
Exercise 66. Create a pushdown automaton, which accepts the language L = {aibjck∣i = j or i = k}.
There is another method for accepting words with a pushdown automaton. It is called "acceptance by empty stack". In this case, the automaton does not have any final states, and the word is accepted by the pushdown automaton if and only if it can read the whole word and the stack is empty when the end of the input word is reached. More formally, the language accepted by automaton
PDAe = (Q, T, Z, q0, z0, δ)
by empty stack is
L(PDAe) = {p∣p∈T*,(q0,p,z0)⊦*PDAe(q,λ,λ),q∈Q}.
Example 49. This example shows the description of a pushdown automaton which accepts by empty stack the language L = {aibicjdj∣i, j ≥ 1}.
PDA = ({q0,q1,q2,q3,q4,q5},{a,b,c,d},{x,z0},q0,z0,δ,{q5}), δ(q0,a,z0) = {(q1,xz0)}, δ(q1,a,x) = {(q1,xx)}, δ(q1,b,x) = {(q2,λ)}, δ(q2,b,x) = {(q2,λ)}, δ(q2,c,z0) = {(q3,xz0)}, δ(q3,c,x) = {(q3,xx)}, δ(q3,d,x) = {(q4,λ}, δ(q4,d,x) = {(q4,λ)}, δ(q4,λ,z0) = {(q4,λ}.
The Figure 4.8. shows the graphical notation of this pushdown automaton.
Example 50. In this example, we are going to show the description of a pushdown automaton which accepts by empty stack the language with words over the alphabet {a,b} containing the same number of a's and b's.
PDA = ({q0},{a,b},{0,1,z0},q0,z0,δ), δ(q0,a,z0) = {(q0,0z0)}, δ(q0,b,z0) = {(q0,1z0)}, δ(q0,a,0) = {(q0,00)}, δ(q0,b,0) = {(q0,λ)}, δ(q0,b,1) = {(q0,11)}, δ(q0,a,1) = {(q0,λ)}, δ(q0,λ,z0)={(q0,λ)}.
The Figure 4.9. shows the graphical notation of this pushdown automaton.
The language class accepted by pushdown automata by final states and the language class accepted by pushdown automata by empty stack are the same. To prove this, we use two lemmas. First, we prove that for each PDA we can give PDAe such that L(PDAe) = L(PDA), second we show the reverse case.
Lemma 1. For each PDA = (Q, T, Z, q0, z0, δ, F) we can give PDAe = (Q', T, Z, q0, z0,δ') such that L (PDAe) = L(PDA).
Proof. We are going to define a pushdown automaton PDAe, which works the same way as the pushdown automaton PDA does, but each time when the original automaton goes into a final state, the new automaton goes into the state qf, as well. Then, PDAe clears out the stack, when it is in the state qf. Formally, let Q' = Q ∪ {qf} where {qf} ∩ Q = ∅, and the transition function is the following:
Let (q2,r) ∈ δ' (q1,a,z) if (q2,r) ∈ δ (q1,a,z), for each q1, q2 ∈ Q, a ∈ T ∪ {λ}, z ∈ Z, r ∈ Z*,
let (qf,λ) ∈ δ' (q1,a,z) if (q2,r) ∈ δ (q1,a,z), for each q1 ∈ Q, q2 ∈ F,a ∈ T ∪ {λ}, z ∈ Z,r ∈ Z*, and
let δ' (qf,λ,z) = {(qf,λ)} for each z ∈ Z.
QED.
Lemma 2. For each PDAe = (Q, T, Z, q0, z0, δ) we can give PDA = (Q', T, Z', q'0, z'0, δ', F) such that L(PDA) = L(PDAe).
Proof. Again, we have a constructive proof. The automaton PDA first puts the initial stack symbol of the automaton PDAe over the new initial stack symbol. Then it simulates the original PDAe automaton, but each time when the original automaton clears the stack completely, the new automaton goes into the new final state qf. The automaton PDA defined below accepts the same language with final states which is accepted by the original automaton PDAe with empty stack. Let Q' = Q ∪ {q'0,qf}, where {q'0} ∩ Q = {qf} ∩ Q = ∅, let Z' = Z ∪ {z'0}, where {z'0} ∩ Z = ∅, and let F = {qf}, so {qf} is the only final state, q'0 is the new initial state, and z'0 is the new initial stack symbol. The transition function is the following:
Let δ'(q'0, λ, z'0) = {(q0,z0z'0)},
let (q2,r) ∈ δ' (q1,a,z) if (q2,r) ∈ δ (q1,a,z), for each q1, q2 ∈ Q, a ∈ T ∪ {λ}, z ∈ Z, r ∈ Z*, and
let δ'(q,λ,z'0) = {(qf,λ)} for each q ∈ Q.
QED.
Theorem 22. The language class accepted by pushdown automata with final states is the same as the language class accepted by pushdown automata with empty stack.
Proof. This theorem is a direct consequence of Lemma 1. and Lemma 2.
QED.
The proof of Lemma 2. has the following consequences:
For each pushdown automaton we can give another pushdown automaton which accepts the same language with only one final state.
For each pushdown automaton we can give another pushdown automaton which accepts the same language with a final state and with empty stack at the same time.
In this subsection we are going to prove that the languages accepted by pushdown automata are the context-free languages. Again, we are going to give constructive proofs. First, we demonstrate that for each pushdown automaton we can give a context-free grammar generating the same language as accepted by the PDAe with empty stack, then we show how to construct a PDAe which accepts the language generated by a context-free grammar.
Lemma 3. For each PDAe = (Q, T, Z, q0, z0, δ) we can give a context-free grammar G = (N, T, S, P) such that L(G) = L(PDAe).
Proof. The set of input letters of the PDAe and the set of terminal symbols of grammar G are the same. The set of nonterminal letters is N = {S} ∪ {A[q,z,t]∣ for each q, t ∈ Q, z ∈ Z}. The production rules are the following:
S → A[q0,z0,q] ∈ P for each q ∈ Q,
A[q,z,t] → aA[t,z1,q1] A[q1,z2,q2]... A[qn-1,zn,qn] ∈ P for each possible q1,..., qn ∈ Q, if (t, z1z2... zn) ∈ δ (q,a,z), where a ∈ T ∪ {λ},
A[q,z,t] → a ∈ P, if (t,λ) ∈ δ (q,a,z), where a ∈ T ∪ {λ}.
Grammar G simulates the work of the PDAe in the following way: During the generating process the prefix of the generated word contains the the first part of the input word - which is already read by the pushdown automaton. It is followed by a nonterminal word A[q,z1,q1] A[q1,z2,q2]... A[qn-1,zn,qn], where z1z2... zn is the word contained by the stack, q is the current state and q1,q2,... qn can be any state. A[q,z,t] meaning that the automaton moves from state q to state t and removes the stack symbol z. The generated word keeps this structure during the generating process. When the automaton reaches the end of the input word and its stack is empty, then the word generated by the grammar contains the whole input word and does not contain any nonterminal symbols.
QED.
Lemma 4. For each context-free grammar G = (N, T, S, P) we can give a pushdown automaton PDAe = (Q, T, Z, q0, z0, δ) such that L(PDAe) = L(G).
Proof. The set of input letters of the PDAe and the set of terminal symbols of grammar G are the same. Let Q = {q0}, Z = N ∪ T, , and z0 = S. The production rules are very simple.
Let (q0,r) ∈ δ (q0,λ,A), if A → r ∈ P, and
let (q0,λ) ∈ δ (q0,a,a) for each a ∈ T.
During the computation of the PDAe, we use λ-steps to simulate the work of grammar G. The current word is always in the stack memory. We can remove the letters one by one, reading them from the input and clearing them at the same time from the top of the stack. The process is finished, when each letter is read and the stack is empty.
QED.
Theorem 23. A language is context-free, if and only if it is accepted by some pushdown automaton.
Proof. This theorem is a direct consequence of Lemma 3. and Lemma 4.
QED.
Finally, we have to note that for each context-free language we can give a pushdown automaton, which has only one state and accepts the context-free language by empty stack. This statement is a direct consequence of the proof of Lemma 4.
Definition 23. The pushdown automaton PDAd = (Q, T, Z, q0, z0, δ, F) is deterministic, if
δ(q,a,z) has at most one element for each triple q ∈ Q, a ∈ T ∪ {λ}, and z ∈ Z, and
if δ(q,λ,z), q ∈ Q, z ∈ Z has an element, then δ(q,a,z) = ∅ for each a ∈ T.
The language class accepted by deterministic pushdown automata with final states is a proper subset of the language class accepted by pushdown automata.
Definition 24. The class of languages accepted by deterministic pushdown automata is called the class of deterministic context-free languages.
In section 4.6.1. we have proven that the language class accepted by pushdown automata by final states and the language class accepted by pushdown automata by empty stack are the same. However, it is different for the deterministic case. The language class accepted by deterministic pushdown automata with empty stack is a proper subset of the language class accepted by deterministic pushdown automata with final states. Let us mark the deterministic pushdown automata accepting by empty stack with PDAde. We can summarize these properties in the following expression:
L (PDAde) ⊂ L (PDAd) ⊂ L (PDAe) = L (PDA).
In this subsection, we define a subclass of pushdown automata as it has already been mentioned in Subsection 3.2.
Definition 25. The one-turn pushdown automaton (OTPDA) is a pushdown automaton PDA = (Q, T, Z, q0, z0, δ, F) with the following property:
The set of states Q = Q1 ∪ Q2, where Q1 ∩ Q2 = ∅,
q0 ∈ Q1 is the initial state,
δ : Q × {T ∪ {λ}} × Z → 2Q×Z* is the transition function such that each of its transitions is
either of the form (q',z') ∈ δ (q,a,z) with q ∈ Q1, ,q' ∈ Q, a ∈ T ∪ {λ}, z ∈ Z, z' ∈ Z+,
or of the form (q',z') ∈ δ (q,a,z) for q, q' ∈ Q2, a ∈ T ∪ {λ}, z ∈ Z, z' ∈ Z ∪ {λ}.
According to the above definition, it is clear that in a run once the automaton reaches a state q' ∈ Q2, then it can never go back to a state in Q1: after the stack content has been decreasing in a step, it cannot increase again. This fact also appears in the name of these special automata: their runs have (at most) one turn point (measuring the stack content).
Example 51. Let PDA = ({q0,q1,qf}, {0,1,2 }, {y,z}, q0, z,δ, qf) be a one-turn pushdown automaton with
Q1 = {q0}, Q2 = {q1,qf},
and δ is given by the following transitions:
(q1,z) ∈ δ (q0,2,z), (q0,yz) ∈ δ (q0,0,z), (q0,yy) ∈ δ (q0,0,y), (q1,y) ∈ δ (q0,2,y), (q1, λ) ∈ δ (q1,1,y), (qf, λ) ∈ δ(q1,2,z).
(For all other triplets of {q0,q1,qf} × {0,1,2} × {y,z} there is no transition available. Thus, if PDA reaches a configuration defining a triplet non-listed above, it causes the process to stop without accepting.)
The work of the automaton can be described as follows:
if the input is 22, then by reading the first 2, it changes its state to q1 (first transition) and then, it reaches qf by the last transition, and thus this input is accepted. (Observe that no other input starting with 2 can be accepted.)
if the input is of the form 0n21n2, then by the second transition PDA is starting to count and by the third transition it is continuing to count the number of 0's by pushing as many y's into the stack as the number of 0's already read. Then, by reading a 2 PDA is at its turning point (having n y in the stack), and it changes its state to q1. (Observe that there were no transitions defined for reading a 1 before this point.) Then, PDA is reading 1's and counting their number by decreasing the number of y's in the stack (popping them out one by one). Finally, if and only if the number of 0's are the same as the number of 1's, then PDA can accept the output by reading the last 2.
PDA is not accepting any other input.
Thus, this pushdown automaton accepts the language
L (PDA) = {0n21n2∣n ∈ ℕ}.
We are going to present the following theorem without a proof.
Theorem 24. The class of languages accepted by one-turn pushdown automata and the class of linear languages coincide.
If there is at most one possible transition in every possible configuration of a one-turn pushdown automaton, then it is a deterministic one-turn pushdown automaton. Observe that PDA is deterministic in Example 51. The deterministic variant of the one-turn pushdown automaton is weaker than the non-deterministic one, and thus the class of them accepts a proper subclass of linear languages, namely, the deterministic linear languages.
Example 52. The language
{anbn∣n ∈ ℕ} ∪ {anb3n∣n ∈ ℕ}
is a union of two languages that are deterministic linear, however, it is not deterministic linear itself.
This chapter is concluded by some exercises.
Exercise 67. Give a one-turn pushdown automaton that recognizes the language of palindromes (a palindrome is a word that is identical to its reverse). (Hint: this language cannot be accepted by deterministic OTPDA.)
Exercise 68. Give a deterministic one-turn pushdown automaton that recognizes the language
{anbmc2n+3∣ n, m ∈ ℕ}
over the alphabet {a,b,c}.
Exercise 69. Give a one-turn pushdown automaton that accepts the language
{uc*(c+d)ddv∣u, v ∈ {a,b}* such that the number of a's in u and v are the same}.