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, q_{0},z_{0}, δ,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),**q*_{0}*is the initial state, q*_{0}∈*Q,**z*_{0}*is the initial stack symbol,**z*_{0}∈*Z*,δ

*is the transition function having a form Q*× {*T*∪ {λ}} × Z → 2^{Q}^{×},^{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
*q*_{0}, we can read the first letter of the input word,
and the stack contains only *z*_{0}. 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:
(*q*_{0}, *p*, *z*_{0}), 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 (

*q*_{1},*av, zw*) to (*q*_{2},*v, rw*) in one step, if it has a transition rule (*q*_{2},*r*) ∈ δ (*q*_{1},*a, z*), where*q*_{1},*q*_{2}∈*Q, a*∈*T, z*∈*Z, v*∈*T*^{*},*w*∈*Z*^{*}. Denote this transition (*q*_{1},*av, zw*) ⊦(_{PDA}*q*_{2},*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 (

*q*_{1},*v, zw*) to (*q*_{2},*v, rw*) in one step, if it has a transition rule (*q*_{2},*r*) ∈ δ (*q*_{1}, λ,*z*), where*q*_{1},*q*_{2}∈*Q, z*∈*Z, v*∈*T*^{*}, and*w*∈*Z*^{*}. Mark: (*q*_{1},*v, zw*) ⊦(_{PDA}*q*_{2},*v, rw*).

We can say that the PDA can change its configuration from (*q*_{1}, *v, w*) to
(*q*_{2}, *x, y*) in finite many steps, if there are configurations
*C*_{0}, *C*_{1},..., *C _{n}*
such that

Finally, we can define the language accepted by the pushdown automaton:

L(PDA) = {p∣p∈T^{*}, (q_{0},p, z_{0}) ⊦^{*}(_{PDA}q, λ,_{f}y),q∈_{f}F, y∈Z^{*}}.

**Example 47.** *This simple example shows the description of a pushdown automaton which accepts
the language
L* = {*a ^{i}b^{i}c^{j}d^{j}*∣

PDA= ({q_{0},q_{1},q_{2},q_{3},q_{4},q_{5}},{a,b,c,d},{x,z_{0}},q_{0},z_{0},δ,{q_{5}}), δ(q_{0},a,z_{0}) = {(q_{1},xz_{0})}, δ(q_{1},a,x) = {(q_{1},xx)}, δ(q_{1},b,x) = {(q_{2},λ)}, δ(q_{2},b,x) = {(q_{2},λ)}, δ(q_{2},c,z_{0}) = {(q_{3},xz_{0})}, δ(q_{3},c,x) = {(q_{3},xx)}, δ(q_{3},d,x) = {(q_{4},λ}, δ(q_{4},d,x) = {(q_{4},λ)}, δ(q_{4},λ,z_{0}) = {(q_{5},z_{0})}.

*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= ({q_{0},q,_{a}q},{_{b}a,b},{1,z_{0}},q_{0},z_{0},δ,{q}), δ(_{a}q_{0},a,z_{0}) = {(q,_{a}z_{0})}, δ(q_{0},b,z_{0}) = {(q,_{b}z_{0})}, δ(q,_{a}a,z_{0}) = {(q,1_{a}z_{0})}, δ(q,_{a}a,1) = {(q,11)}, δ(_{a}q,_{a}b,1) = {(q,λ)}, δ(_{a}q,_{a}b,z_{0}) = {(q_{0},z_{0})}, δ(q,_{b}b,z_{0}) = {(q,1_{b}z_{0})}, δ(q,_{b}b,1) = {(q,11)}, δ(_{b}q,_{b}a,1) = {(q,λ)}, δ(_{b}q,_{b}a,z_{0}) = {(q_{0},z_{0})}.

*The Figure 4.7. shows the graphical notation of this pushdown automaton.*

**Exercise 64.** *Create a pushdown automaton, which accepts the language
L* = {*a ^{i}b^{j}*∣0 ≤

**Exercise 65.** *Create a pushdown automaton, which accepts the language
L* = {*a ^{i}b^{j}c^{k}*∣

**Exercise 66.** *Create a pushdown automaton, which accepts the language
L* = {*a ^{i}b^{j}c^{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

PDA= (_{e}Q, T, Z, q_{0},z_{0}, δ)

by empty stack is

L(PDA) = {_{e}p∣p∈T^{*},(q_{0},p,z_{0})⊦^{*}(_{PDAe}q,λ,λ),q∈Q}.

**Example 49.** *This example shows the description of a pushdown automaton which
accepts by empty
stack the language L* = {*a ^{i}b^{i}c^{j}d^{j}*∣

PDA= ({q_{0},q_{1},q_{2},q_{3},q_{4},q_{5}},{a,b,c,d},{x,z_{0}},q_{0},z_{0},δ,{q_{5}}), δ(q_{0},a,z_{0}) = {(q_{1},xz_{0})}, δ(q_{1},a,x) = {(q_{1},xx)}, δ(q_{1},b,x) = {(q_{2},λ)}, δ(q_{2},b,x) = {(q_{2},λ)}, δ(q_{2},c,z_{0}) = {(q_{3},xz_{0})}, δ(q_{3},c,x) = {(q_{3},xx)}, δ(q_{3},d,x) = {(q_{4},λ}, δ(q_{4},d,x) = {(q_{4},λ)}, δ(q_{4},λ,z_{0}) = {(q_{4},λ}.

*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= ({q_{0}},{a,b},{0,1,z_{0}},q_{0},z_{0},δ), δ(q_{0},a,z_{0}) = {(q_{0},0z_{0})}, δ(q_{0},b,z_{0}) = {(q_{0},1z_{0})}, δ(q_{0},a,0) = {(q_{0},00)}, δ(q_{0},b,0) = {(q_{0},λ)}, δ(q_{0},b,1) = {(q_{0},11)}, δ(q_{0},a,1) = {(q_{0},λ)}, δ(q_{0},λ,z_{0})={(q_{0},λ)}.

*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 PDA_{e} such that
*L*(*PDA _{e}*) =

**Lemma 1.** *For each PDA* =
(*Q, T, Z, q*_{0}, *z*_{0}, δ, *F*)
*we can give PDA _{e}* = (

**Proof.** We are going to define a pushdown automaton PDA_{e}, 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 *q _{f}*, as well.
Then, PDA

Let (

*q*_{2},*r*) ∈ δ' (*q*_{1},*a,z*) if (*q*_{2},*r*) ∈ δ (*q*_{1},*a,z*), for each*q*_{1},*q*_{2}∈*Q, a*∈*T*∪ {λ},*z*∈*Z, r*∈*Z*^{*},let (

*q*,λ) ∈ δ' (_{f}*q*_{1},*a,z*) if (*q*_{2},*r*) ∈ δ (*q*_{1},*a,z*), for each*q*_{1}∈*Q, q*_{2}∈*F,a*∈*T*∪ {λ},*z*∈*Z,r*∈*Z*^{*}, andlet δ' (

*q*,λ,_{f}*z*) = {(*q*,λ)} for each_{f}*z*∈*Z*.

QED.

**Lemma 2.** *For each PDA _{e}* =
(

**Proof.** Again, we have a constructive proof. The automaton PDA first puts the initial stack symbol
of the automaton PDA*e* over the new initial stack symbol. Then it simulates the original PDA*e* automaton,
but each time when the original
automaton clears the stack completely, the new automaton goes into the new final state *q _{f}*.
The automaton PDA defined below accepts the same
language with final states which is accepted by the original automaton PDA

Let δ'(

*q'*_{0}, λ,*z'*_{0}) = {(*q*_{0},*z*_{0}*z'*_{0})},let (

*q*_{2},*r*) ∈ δ' (*q*_{1},*a,z*) if (*q*_{2},*r*) ∈ δ (*q*_{1},*a,z*), for each*q*_{1},*q*_{2}∈*Q, a*∈*T*∪ {λ},*z*∈*Z, r*∈*Z*^{*}, andlet δ'(

*q*,λ,*z'*_{0}) = {(*q*,λ)} for each_{f}*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 PDA_{e} with empty stack, then we show how to construct a PDA_{e} which
accepts the language
generated by a context-free grammar.

**Lemma 3.** *For each PDA _{e}* =
(

**Proof.** The set of input letters of the PDA*e* 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*_{[}_{q}_{0,}_{z}_{0,}_{q}_{]}∈*P*for each*q*∈*Q*,*A*_{[}_{q,z,t}_{]}→*aA*_{[}_{t,z}_{1,}_{q}_{1}_{]}*A*_{[}_{q}_{1,}_{z}_{2,}_{q}_{2}_{]}...*A*_{[}_{q}_{n}_{-1,}_{zn,}_{qn}_{]}∈*P*for each possible*q*_{1},...,*q*∈_{n}*Q*, if (*t*,*z*_{1}*z*_{2}...*z*) ∈ δ (_{n}*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 PDA* _{e}* 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

QED.

**Lemma 4.** *For each context-free grammar G* = (*N, T, S, P*)
*we can give a pushdown automaton
PDA _{e}* = (

**Proof.** The set of input letters of the PDA* _{e}* and the set of terminal symbols
of grammar

Let (

*q*_{0},*r*) ∈ δ (*q*_{0},λ,*A*), if*A*→*r*∈*P*, andlet (

*q*_{0},λ) ∈ δ (*q*_{0},*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 PDA _{d}* =
(

δ(

*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
*PDA _{de}*.
We can summarize these properties in the following expression:

L(PDA) ⊂_{de}L(PDA) ⊂_{d}L(PDA) =_{e}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, q*_{0}, *z*_{0}, δ, *F*)
*with the following property:*

*The set of states Q = Q*_{1}∪*Q*_{2},*where Q*_{1}∩*Q*_{2}= ∅,*q*_{0}∈*Q*_{1}*is the initial state,*δ :

*Q*× {*T*∪ {λ}} ×*Z*→ 2^{Q}^{×}^{Z*}*is the transition function such that each of its transitions is**either of the form*(*q',z'*) ∈ δ (*q,a,z*)*with q*∈*Q*_{1}, ,*q'*∈*Q, a*∈*T*∪ {λ},*z*∈*Z, z'*∈*Z*^{+},*or of the form*(*q',z'*) ∈ δ (*q,a,z*)*for q, q'*∈*Q*_{2},*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'* ∈
*Q*_{2}, then it can never go
back to a state in *Q*_{1}: 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* =
({*q*_{0},*q*_{1},*q _{f}*}, {0,1,2 },
{

Q_{1}= {q_{0}},Q_{2}= {q_{1},q},_{f}

*and δ is given by the following transitions: *

(q_{1},z) ∈ δ (q_{0},2,z), (q_{0},yz) ∈ δ (q_{0},0,z), (q_{0},yy) ∈ δ (q_{0},0,y), (q_{1},y) ∈ δ (q_{0},2,y), (q_{1}, λ) ∈ δ (q_{1},1,y), (q_{f}, λ) ∈ δ(q_{1},2,z).

*(For all other triplets of {q*_{0},*q*_{1},*q _{f}*}
× {0,1,2} × {

*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 q*_{1}*(first transition) and then, it reaches q*_{f}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*021^{n}2,^{n}*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 q*_{1}.*(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) = {021^{n}2∣^{n}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*

{

a∣^{n}b^{n}n∈ ℕ} ∪ {a^{n}b^{3}∣^{n}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*

{

a^{n}b^{m}c^{2}^{n}^{+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}.