EXERCISES
1. Construct a Pushdown automata (PDA) accepting the language
L
i
j
i i
j
j
=
≥ ∪
≥
{
|
} {
|
}
0 1
0
0 1
0
2
.
2. For Σ = { , },
0 1 design DPDAs to accept the following languages:
(a) 0*
(b) {
| ,
}
0 1 0 1
0
i i j j i j ≥
(c) {
|
}
0 1
1
2i i i ≥
(d) {
|
}
0 1
m n m n
≠
3. Define the concepts of string and language acceptance for PDAs.
4. For Σ = { , },
01 design PDA to accept the following languages:
(a) { |
{ , } }
*
xx x ∈ 0 1
(b) { |
{ , }
}
*
x x
x x
R
∈
=
0 1 and
(c) {
|
}
0 1
2
m n n m n
≤ ≤
(d) {
|
}
0 1 3
7
m n
n m n
≤ ≤
5. Construct a PDA accepting {
|
}
a b n
n
n
3
1
≥ by empty store.
6. Obtain the PDA accepting {
| ,
}
a b c m n
m n n
≥1 by empty store.
7. Obtain the PDA accepting {
| ,
}
a b c m n
m n n
≥1 by final state.
8. Given L a b m n
n m
=
<
{
|
}. Derive
(a) a CFG that accepts L
(b) a PDA accepting L by empty store
(c) a PDA accepting L by final state.
9. Construct a PDA accepting L wcw w a b
T
=
∈
{
:
{ , } }
* by final state.
10. Construct a PDA accepting L wcw w a b
T
=
∈
{
:
{ , } }
* by empty store.
11. If the PDA A Q
q Z F
= { , , , , , , )
Σ Γ δ 0 0
accepts L by final state, prove that
there exists another PDA B accepting L by empty store, i.e., T(A) = T(B)
= L.
12. Find PDA accepting the following sets by final state
(a) { { , } : ( )
( )}
*
x a b n x n x
a
b
∈
>
(b) x a b n x x x
a
b
∈
<
{ , } : ( )
( )}
*
13. Design a PDA recognizing the set L of all non-palindromes over {a, b}.
14. Construct a PDA equivalent to the CFG.
S
BB B
S B
S B
→
→
→
→
0
0
1
0
,
,
,
15. Construct a CFG accepting L a b n m
m n
=
<
{
|
} and construct a PDA
accepting L by empty store.
Pushdown Automata
181