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:

  1. δ(q,0,Z0) = {(q,X)}
  2. δ(q,0,X) = {(q,XX)}
  3. δ(q,1,X) = {(p,ε)}
  4. δ(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:

  1. i=j=0 (state q1).
  2. i=j>0 (state q2).
  3. 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:

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:

  1. δ(q,ε,S) = {(q,0S1), (q,A)}
  2. δ(q,ε,A) = {(q,1A0), (q,S), (q,ε)}
  3. δ(q,0,0) = {(q,ε)}
  4. δ(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.

  1. S -> [qZq] | [qZp]

    The following four productions come from rule (1).

  2. [qZq] -> 1[qXq][qZq]
  3. [qZq] -> 1[qXp][pZq]
  4. [qZp] -> 1[qXq][qZp]
  5. [qZp] -> 1[qXp][pZp]

    The following four productions come from rule (2).

  6. [qXq] -> 1[qXq][qXq]
  7. [qXq] -> 1[qXp][pXq]
  8. [qXp] -> 1[qXq][qXp]
  9. [qXp] -> 1[qXp][pXp]

    The following two productions come from rule (3).

  10. [qXq] -> 0[pXq]
  11. [qXp] -> 0[pXp]

    The following production comes from rule (4).

  12. [qXq] -> e

    The following production comes from rule (5).

  13. [pXp] -> 1

    The following two productions come from rule (6).

  14. [pZq] -> 0[qZq]
  15. [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:

  1. 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.

  2. Add a new ``popping state'' to P. In this state, P pops every symbol it sees on the stack, using ε input.

  3. 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