| Introduction to Automata
Theory, Languages, and Computation
|
Solutions for Chapter 6
Solutions for Section 6.1
Solutions for Section 6.2
Solutions for Section 6.3
Solutions for Section 6.4
Solutions for Section 6.1
Exercise 6.1.1(a)
(q,01,Z0) |- (q,1,XZ0) |- (q,ε,XZ0) |- (p,ε,Z0)
|- (p,1,Z0) |- (p,ε,ε)
Return to Top
Solutions for Section 6.2
Exercise 6.2.1(a)
We shall accept by empty stack.
Symbol X will be used to count the 0's on the input.
In state q, the start state, where we have seen no 1's, we add an
X to the stack for each 0 seen.
The first X replaces Z0, the start symbol.
When we see a 1, we go to state p, and then only pop the stack,
one X for each input 1.
Formally, the PDA is ({q,p},{0,1},{X,Z0},δ,q,Z0).
The rules:
- δ(q,0,Z0) = {(q,X)}
- δ(q,0,X) = {(q,XX)}
- δ(q,1,X) = {(p,ε)}
- δ(p,1,X) = {(p,ε)}
Exercise 6.2.2(a)
Revised 6/20/02.
Begin in start state q0, with start symbol Z0,
and immediately guess whether to check for:
- i=j=0 (state q1).
- i=j>0 (state q2).
- j=k (state q3).
We shall accept by final state; as seen below, the accepting states are
q1 and q3.
The rules, and their explanations:
- δ(q0,ε,Z0) = {(q1,Z0), (q2,Z0), (q3,Z0)}, the
initial guess.
- δ(q1,c,Z0) = {(q1,Z0)}.
In case (1), we assume there are no a's or b's, and we
consume all c's.
State q1 will be one of our accepting states.
- δ(q2,a,Z0) = {(q2,XZ0)}, and δ(q2,a,X) =
{(q2,XX)}.
These rules begin case (2).
We use X to count the number of a's read from the input,
staying in state q2.
- δ(q2,b,X) = δ(q4,b,X) = {(q4,ε)}.
When b's are seen, we go to state q4 and pop X's
against the b's.
- δ(q4,ε,Z0) = {(q1,Z0)}.
If we reach the bottom-of-stack marker in state q4, we have seen
an equal number of a's and b's.
We go spontaneously to state q1, which will accept and consume
all c's, while continuing to accept.
- δ(q3,a,Z0) = {(q3,Z0)}.
This rule begins case (3).
We consume all a's from the input.
Since j=k=0 is possible, state q3 must be an accepting
state.
- δ(q3,b,Z0) = {(q5,XZ0)}.
When b's arrive, we start counting them and go to state
q5, which is not an accepting state.
- δ(q5,b,X) = {(q5,XX)}.
We continue counting b's.
- δ(q5,c,X) = δ(q6,c,X) = {(q6,ε)}.
When c's arrive, we go to state q6 and match the
c's against the b's.
- δ(q6,ε,Z0) = {(q3,ε)}.
When the bottom-of-stack marker is exposed in state q6, we have
seen an equal number of b's and c's.
We spontaneously accept in state q3, but we pop the stack so we
cannot accept after reading more a's.
Exercise 6.2.4
Introduce a new state q, which becomes the initial state.
On input ε and the start symbol of P, the new PDA has a
choice of popping the stack (thus accepting ε), or going to the
start state of P.
Exercise 6.2.5(a)
Revised 4/30/10
(q0,bab,Z0) |- (q2,ab,BZ0) |- (q3,b,Z0) |- (q1,b,AZ0) |-
(q1,ε,Z0) |- (q0,ε,Z0) |- (f,ε,ε)
Exercise 6.2.8
Suppose that there is a rule that (p,X1X2...Xk) is a choice in
δ(q,a,Z).
We create k-2 new states r1,r2,...,rk-2
that simulate this rule but do so by
adding one symbol at a time to the stack.
That is, replace (p,X1X2...Xk) in the rule by
(rk-2,Xk-1Xk).
Then create new rules
δ(rk-2,ε,Xk-1) = {(rk-3,Xk-2Xk-1)}, and so on, down
to δ(r2,ε,X3) = {(r1,X2X3)} and
δ(r1,ε,X2) =
{(p,X1X2)}.
Return to Top
Solutions for Section 6.3
Exercise 6.3.1
({q},{0,1),{0,1,A,S},δ,q,S) where δ is defined by:
- δ(q,ε,S) = {(q,0S1), (q,A)}
- δ(q,ε,A) = {(q,1A0), (q,S), (q,ε)}
- δ(q,0,0) = {(q,ε)}
- δ(q,1,1) = {(q,ε)}
Exercise 6.3.3
In the following, S is the start symbol, e stands for the
empty string, and Z is used in place of Z0.
- S -> [qZq] | [qZp]
The following four productions come from rule (1).
- [qZq] -> 1[qXq][qZq]
- [qZq] -> 1[qXp][pZq]
- [qZp] -> 1[qXq][qZp]
- [qZp] -> 1[qXp][pZp]
The following four productions come from rule (2).
- [qXq] -> 1[qXq][qXq]
- [qXq] -> 1[qXp][pXq]
- [qXp] -> 1[qXq][qXp]
- [qXp] -> 1[qXp][pXp]
The following two productions come from rule (3).
- [qXq] -> 0[pXq]
- [qXp] -> 0[pXp]
The following production comes from rule (4).
- [qXq] -> e
The following production comes from rule (5).
- [pXp] -> 1
The following two productions come from rule (6).
- [pZq] -> 0[qZq]
- [pZp] -> 0[qZp]
Exercise 6.3.6
Convert P to a CFG, and then convert the CFG to a PDA, using the
two constructions given in Section 6.3.
The result is a one-state PDA equivalent to P.
Return to Top
Solutions for Section 6.4
Exercise 6.4.1(b)
Not a DPDA.
For example, rules (3) and (4) give a choice, when in state q,
with 1 as the next input symbol, and
with X on top of the stack, of either using the 1 (making no
other change) or making a move on ε input that pops the stack and
going to state p.
Exercise 6.4.3(a)
Suppose a DPDA P
accepts both w and wx by empty stack, where
x is not ε (i.e., N(P) does not have the prefix
property).
Then (q0,wxZ0) |-* (q,x,ε) for some state q, where
q0 and Z0 are the start state and symbol of P.
It is not possible that (q,x,ε) |-* (p,ε,ε) for
some state p, because we know x is not ε, and a PDA
cannot have a move with an empty stack.
This observation contradicts the assumption that wx is in
N(P).
Exercise 6.4.3(c)
Modify P' in the following ways to create DPDA P:
-
Add a new start state and a new start symbol.
P, with this state and symbol, pushes the start symbol of
P' on top of the stack and goes to the start state of P'.
The purpose of the new start symbol is to make sure P doesn't
accidentally accept by empty stack.
-
Add a new ``popping state'' to P.
In this state, P pops every symbol it sees on the stack, using
ε input.
-
If P' enters an accepting state, P enters the popping
state instead.
As long as L(P') has the prefix property, then any string that
P' accepts by final state, P will accept by empty stack.
Return to Top