Introduction to Automata Theory, Languages, and Computation

## Solutions for Chapter 6

Solutions for Section 6.1

## Solutions for Section 6.1

### Exercise 6.1.1(a)

```(q,01,Z0) |- (q,1,XZ0) |- (q,ε,XZ0) |- (p,ε,Z0)
|- (p,1,Z0)  |- (p,ε,ε)
```

## 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:

• δ(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)}.

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

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