Solu tion
Let us assume that L T M
= ( ), where the automaton M has n states.
If p is a prime number greater than n, consider
z a
L
p
=
∈ .
By using pumping lemma, s = uvw and uv w L
i
∈ for i ≥ 1.
Also
uv w L
P +
∈
1
.
But |
| |
| | |
uv w uvw v
p pm
P
P
+
=
+
= +
1
where m = | v |.
This is a contradiction as we see that p + pm cannot be prime.
Therefore the language L is not prime.
Ì Exam ple 3.4.3: Construct a deterministic Pushdown Automata to
accept L ( ) , the language of nested, balanced parantheses.
Solu tion
The idea is to store all left parantheses on the stack and then pop them off as
each one matches a right parantheses.
Let us define
M
q q
q q
= ({ , }, {( , )}, , , { })
0
1
0
1
δ
where δ is given in the table below.
Table: Tran si tion Table for DPDA.
Tran si tion
Num ber
Cur rent
state
Input
sym bol
Stack
Top
New
state
Input
op
Stack
op
1
q 0
(
>
q 0
+
push (
2
q 0
(
(
q 0
+
push (
3
q 0
)
(
q 0
+
pop
4
q 0
>
>
q 1
0
0
5
q 0
>
(
q 2
0
0
6
q 0
)
>
q 2
0
0
Transitions (1) and (2) are used to push opening parantheses on the stack;
transition (3) is used to to match a closing paranthesis with an open one on the
stack; (4) accepts the input, and (5) and (6) send the machine into a rejecting
state, which halts the machine.
178
Theory of Automata, Formal Languages and Computation