COSC1107/1105 Computing Theory
School of Computing Technologies Semester 2, 2021
Tutorial No. 4: PDAs
Before this tutorial you are expected to have read Section 4 of the Computing Theory notes.
The aim of this tutorial is to gain some familiarity with pushdown automata. By the end of this tutorial you should be able to analyse the execution of a PDA and to generate some simple machines from a specification.
PART1: PushdownAutomata…………………………………………………………………… Pushdown automata are an extension of Finite State Machines in the sense that they involve the addition of a stack which basically gives them the ability to count. In particular, we can build a PDA for the language {anbn | n ≥ 0}. Each state transition may now involve reading a symbol and possibly reading the stack; as with empty-transitions in NFAs, we can ignore the input and/or stack on any particular transition. A transition involves moving to a new state (which may be the same as the current one) and possibly adding a symbol to the stack (which may be the same as the one read). The stack is empty at the start of a computation and must be empty at the end, for a computation to be successful.
For instance, by pushing an A onto the stack each time an a is read and then popping an A off whenever a b is read, we can write a PDA that accepts {anbn | n >= 0}.
PDAs accept context-free languages, i.e. a language is context-free if and only if there is a PDA which accepts it. Formally, a pushdown automaton is a tuple M = (Q, Σ, Γ, δ, q0 , F ), where:
Q is a finite set of states,
Σ is an alphabet (the input symbols),
Γ is an alphabet (the stack symbols),
q0 ∈ Q is the initial state,
F ⊆ Q is the set of final states, and
δ is the transition relation, a finite subset of
(Q×(Σ∪{λ})×(Γ∪{λ})×(Q×(Γ∪{λ})).
Transitions of the form δ(q0, a, λ) = {[q0, A]} means, that the machine is in state q0, the character being read is an a, λ
is popped from the stack and A is pushed onto the stack. Examples:
Let M be the PDA below. States = {q0, q1, q2}
δ(q0, a, λ) = {[q0, A]} δ(q0, b, λ) = {[q2, λ]}
Input alphabet = {a, b} δ(q1, λ, A) = {[q1, λ]} δ(q2, λ, A) = {[q2, λ]}
Stack alphabet = {A} δ(q0, λ, λ) = {[q1, λ]}
Final states = {q1, q2} δ(q2, b, A) = {[q2, λ]}
1. Draw a transition diagram for M
q2 b−A,−A b
a+A
q0 λ q1 −A
1
COSC1107/1105 – Computing Theory Tutorial 4: PDAs Page 2 of 4 2. Trace the computations of the strings aab, abb, aba in M
.
⊢ q0,aab,λ
⊢ q0,ab,A
⊢ q0,b,AA
⊢ q2,λ,AA
⊢ q2,λ,A
⊢ q2, λ, λ – accept
⊢ q0,abb,λ
⊢ q0,bb,A
⊢ q2,b,A
⊢ q2,λ,λ – accept
⊢ q0,aba,λ
⊢ q0,ba,A
⊢ q2,a,A – reject
A thing to note here is that we have chosen particular computations that work in some sense, but there are other possible computations for each of the cases above. For example, another possible computation for aab would be: q0,aab,λ ⊢ q0,ab,A ⊢ q1,ab,A ⊢ q1,ab,λ.
In this computation the string is not accepted. However, if there is at least one computation in which the string can be accepted then the string is in the language. Therefore, to show a string is not accepted (if we cannot prove it theoretically) all computations must be shown to fail.
3. Describe the language accepted by M .
L(M) is all as (if any) must precede all bs and the number of as must be greater than or equal to the number of bs −1 (or in Sudkamp’s notation, #a(w) ≥ #b(w) − 1).
4. Show that aabb, aaab ∈ L(M ).
They both are in the language since all as precede bs and number of as is greater than or equal to the number of bs −1. More formally we have
⊢ q0,aabb,λ ⊢ q0,abb,A ⊢ q0,bb,AA ⊢ q2,b,AA ⊢ q2,λ,A
⊢ q2, λ, λ – accept
⊢q0,aaab,λ ⊢q0,aab,A ⊢q0,ab,AA ⊢q0,b,AAA ⊢q2,λ,AAA ⊢ q2,λ,AA ⊢ q2,λ,A
⊢ q2, λ, λ – accept
5. Construct a context free grammar for the language.
S → ASb | b | λ A → aA | a
Let’s take another PDA for example. Consider the language below:
L={anb2n | n≥0} The PDA that accepts this language looks like this:
a+AA b−A q0 λ q1
However, if we look at the formal definition of PDAs, as given in the notes, a pushdown automaton is a tuple M = (Q,Σ,Γ,δ,q0,F), where:
Q is a finite set of states,
Σ is an alphabet (the input symbols),
Γ is an alphabet (the stack symbols),
q0 ∈ Q is the initial state,
F ⊆ Q is the set of final states, and
δ is the transition relation, a finite subset of
(Q×(Σ∪{λ})×(Γ∪{λ})×(Q×(Γ∪{λ})).
Using the highlighted definition above, it can be seen that the transition ((q0 , a, λ), (q0 , AA)) cannot be built; i.e. you
cannot get the pair (q0, AA) from the cross product {q0, q1} × ({A} ∪ {λ}).
RMIT CT 2021 (Semester 2) – Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 4: PDAs Page 3 of 4
This is technically correct and the simultaneous stack operation, that is shown above, can be thought of in the same way as the + notation is used in regular expressions; they are just “syntactical sugar” to make things easier for humans, but unnecessary in representing languages formally.
The textbook uses the term “extended PDAs” when referring to machines with simultaneous stack operations and explains that it makes no difference to the expressive power of the machine. This is so because an extended PDA can be readily converted into a regular one by adding k − 1 states, where k is the number of stack symbols being pushed simultaneously.
So, just as (a|b)+ is merely convenient shorthand for (a|b)(a|b)∗ , the transition ((q0 , a, λ), (q0 , AA)) is convenient short- hand for {((q0, a, λ), (q0′, A)), ((q0′, λ, λ), (q0, A))}, where q0′ is an extra state that is added to accommodate this extra transition.
The state diagram will look like this:
q0′
a+A λ+A
b−A q0 λ q1
Clearly, the transitions can now all be produced using the cross product {q0 , q0 ′ , q1 } × ({A} ∪ {λ}) and everything is just as expected using formal definitions.
NB: One final point to make is that be very careful of the order in which the symbols are added to stack; i.e., {(q0, a, AB), (q0, λ)} is different to {(q0, a, BA), (q0, λ)}! Again, as with the + notation in regular expressions, if you are unsure, it is always
better to err on the side of caution and use the formal representation (with single stack operations).
(a) Consider the pushdown automaton below. Q = {q0,q1},
F = {q1},
Σ = {a, b},
Γ = {A},
δ = {((q0, a, λ), (q0, A)), ((q0, b, λ), (q0, A)), ((q0, a, λ), (q1, λ)), ((q1, a, A), (q1, λ)), ((q1, b, A), (q1, λ))}.
i. Trace all possible sequences of transitions of M on input aba.
ii. Show that baa, bab, baaaa ∈ L(M ) and aba, aa, abb, ̸∈ L(M ).
Solution: The PDA is shown below:
a + A, b + A a − A, b − A q0 a q1
1. (q0,aba,λ) ⊢ (q0,ba,A) ⊢ (q0,a,AA) ⊢ (q0,λ,AAA). 2. (q0,aba,λ) ⊢ (q0,ba,A) ⊢ (q0,a,AA) ⊢ (q1,λ,AA). 3. (q0,aba,λ)⊢(q1,ba,λ).
Solution: You just have to show that at least one trace accepts the string for it to be accepted. However, to show that a string is not in the language, you have to show that no accepting trace exists, or in other words, that all possible traces for the string do not finish in an accepting configuration.
1. (q0,baa,λ) ⊢ (q0,aa,A) ⊢ (q1,a,A) ⊢ (q1,λ,λ).
2. (q0,bab,λ) ⊢ (q0,ab,A) ⊢ (q1,b,A) ⊢ (q1,λ,λ).
3. (q0,baaaa,λ) ⊢ (q0,aaaa,A) ⊢ (q0,aaa,AA) ⊢ (q1,aa,AA) ⊢ (q1,a,A) ⊢ (q1,λ,λ).
4. aba is as above.
5. • (q0,aa,λ) ⊢ (q0,a,A) ⊢ (q0,λ,AA)
• (q0,aa,λ) ⊢ (q0,a,A) ⊢ (q1,λ,A) • (q0,aa,λ) ⊢ (q1,a,λ)
RMIT CT 2021 (Semester 2) – Exercise 1 continues on the next page. . .
COSC1107/1105 – Computing Theory Tutorial 4: PDAs Page 4 of 4
6. • (q0,abb,λ) ⊢ (q0,bb,A) ⊢ (q0,b,AA) ⊢ (q0,λ,AAA) • (q0,abb,λ)⊢(q1,bb,λ)
iii. Describe L(M) in English.
(b) Construct pushdown automata that accept each of the following:
i. The language generated by the grammar G = (V, Σ, R, S) where:
V = {S},
Σ = {(,),[,]}, R={
S → λ, S → SS, S → [S], S → (S) }.
ii. Thelanguage{ambn |0≤m≤n≤2m}
iii. The language {w ∈ {a, b}∗ : w has twice as many b’s as a’}.
iv. Thelanguage{w∈{a,b}∗ :w=wR}.
(c) Construct a grammar over {a, b, c} whose language is {an bm c2n+m | n, m ≥ 0}.
(d) Construct a grammar over {a, b} whose language contains precisely those strings with the same number of a’s and b’s.
Solution: The language of this machine is all strings of odd length over { a,b } with an a as the middle character.
Solution: The PDA to recognise the brackets language is below. q0
(+A, [+B, ) − A, ] − B
Solution:
b − A, b − AA q0 λ q1
a+AA
Solution: There needs to be only one correct path through the PDA.
a + AA, b − A λ b + B, a − BB
q0 q1 λ, a − B + A
Solution: A palindrome.
a + A, b + B a − A, b − B
q λ, a, b q 01
Solution: One such grammar is
S → aScc | B B → bBc | λ
Solution: NOTE: This is almost the same question as that in assignment 1 of CT15. One such grammar is: S → SS | aSb | bSa | λ.
Another solution could be: S → SaSbS | SbSaS | λ.
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 4: PDAs Page 5 of 4 (e) For the following languages below, either give a PDA or indicate why this is not possible.
i. {aibjck | i ̸= j,i,j,k ≥ 0}
Solution: Looks familiar once again! Note that this question asks for a PDA instead of a grammar. It should be easy enough to convert, though, remember A → aAb means you push an A for each a and then pop an A for each B (the basic point here is that a context free grammar can only “count” two different variables. So whenever you have to count three different variables, it cannot be a context free grammar and hence no PDA).
Solution:
S → AD
A → aAb | B | C B → aB | a
C → bC | b
D → cD | λ
a/ε, A
λ/ε, ε
b/ε,ε q3
b/A, ε
q0 q1 q2
λ/A, ε
λ/A, ε
b/ε, ε λ/ε, ε
λ/ε, ε
q4 c/ε,ε
ii. {aibjck | j ̸= k,i,j,k ≥ 0}
Solution:
S → EF
E → aE | λ
F → bF c | G | H G → bG | b
H → cH | c
λ/A, ε q0 q1 q2 q3
c/ε, ε
q4 c/ε, ε
a/ε, ε
λ/ε, ε
b/ε, A
c/A, ε
λ/ε, ε
λ/A, ε
iii. {aibjck | i ̸= k,i,j,k ≥ 0}
Solution:
S → aSc | aA | Cc A → aA | B
B → bB | λ
C → Cc | B
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 4: PDAs Page 6 of 4
a/ε, A b/ε, ε λ/ε, ε
c/A, ε λ/A, ε λ/A, ε
λ/ε, ε
q0 q1 q2 q3
c/ε, ε
q4 c/ε, ε
iv. {aibjck |i̸=jorj̸=k,i,j,k≥0}
Solution: Possible (combine previous two solutions)
a/ε, A b/A, ε λ/A, ε
λ/ε, ε λ/A, ε
q1 q2 q3
λ/ε, ε q0
λ/ε, ε
λ/ε, ε
q6 q7 q8 q9
a/ε, ε b/ε, A c/A, ε λ/A, ε
b/ε, ε
λ/ε, ε b/ε, ε
q4
q5 c/ε,ε c/ε, ε
λ/ε, ε
λ/ε, ε λ/A, ε
v. {aibjck |i̸=jandj̸=k,i,j,k≥0}
Solution: Not possible, can count/compare only two variables.
vi. {aibjck |i=jorj=k,i,j,k≥0}
Solution: S → AB | CD A → aAb | λ
B → cB | λ
C → aC | λ
D → bDc | λ
RMIT CT 2021 (Semester 2) –
COSC1107/1105 – Computing Theory Tutorial 4: PDAs Page 7 of 4
λ/ε, ε q0
λ/ε, ε
a/ε, A b/A, ε c/ε, ε λ/ε, ε λ/ε, ε
q1 q2 q3
λ/ε, ε λ/ε, ε
q4 q5 q6
a/ε, ε b/ε, A c/A, ε
vii. {aibjck |i=jandj=k,i,j,k≥0}
Solution: Not possible, can count only two variables.
viii. {aibjckdn | i = j and k = n,i,j,k,n ≥ 0}
ix. {aibjckdlemfn | i = j and k = l and m = n,i,j,k,l,m,n ≥ 0}
x. {aibjckdn |i=nandj=k,i,j,k,n≥0}
Reflection
Would it be more powerful to use a PDA with two stacks? What would a deterministic PDA look like? How about adding a third stack?
End of tutorial worksheet
Solution:
a+X b−X c+Y d−Y q0 λ q1 λ q2 λ q3
Solution:
f−Z q0 λ q1 λ q2 λ q3 λ q4 λ q5
a+X b−X c+Y d−Y e+Z
Solution:
a+X b+Y c−Y d−X q0 λ q1 λ q2 λ q3
RMIT CT 2021 (Semester 2) –