Prentice-Hall     Addision-Wesley

Copyright © 2007 Gradiance Corporation.

 

Gradiance Online Accelerated Learning

 

 

 

 

 

     

Pushdown Automata

 

 

1.  

Consider the pushdown automaton with the following transition rules:

  1. δ(q,0,Z0) = {(q,XZ0)}
  2. δ(q,0,X) = {(q,XX)}
  3. δ(q,1,X) = {(q,X)}
  4. δ(q,ε,X) = {(p,ε)}
  5. δ(p,ε,X) = {(p,ε)}
  6. δ(p,1,X) = {(p,XX)}
  7. δ(p,1,Z0) = {(p,ε)}

The start state is q. For which of the following inputs can the PDA first enter state p with the input empty and the stack containing XXZ0 [i.e., the ID (p,ε,XXZ0)]?

 

 

 

 a) 

001111

 

 b) 

0101010

 

 c) 

001110

 

 d) 

111001

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.  

Here are the transitions of a determininstic pushdown automaton. The start state is q0, and f is the accepting state.

State-Symbol

a

b

ε

q0-Z0

(q1,AAZ0)

(q2,BZ0)

(f,ε)

q1-A

(q1,AAA)

(q1,ε)

-

q1-Z0

-

-

(q0,Z0)

q2-B

(q3,ε)

(q2,BB)

-

q2-Z0

-

-

(q0,Z0)

q3-B

-

-

(q2,ε)

q3-Z0

-

-

(q1,AZ0)

Describe informally what this PDA does. Then, identify below the one input string that the PDA accepts.

 

 

 

 a) 

bbbab

 

 b) 

abbbab

 

 c) 

abbbabb

 

 d) 

bbaabab

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  

Here are the transitions of a deterministic pushdown automaton. The start state is q0, and f is the accepting state.

State-Symbol

a

b

ε

q0-Z0

(q1,AAZ0)

(q2,BZ0)

(f,ε)

q1-A

(q1,AAA)

(q1,ε)

-

q1-Z0

-

-

(q0,Z0)

q2-B

(q3,ε)

(q2,BB)

-

q2-Z0

-

-

(q0,Z0)

q3-B

-

-

(q2,ε)

q3-Z0

-

-

(q1,AZ0)

Describe informally what this PDA does. Then, identify below, the one input string that takes the PDA into state q3 (with any stack).

 

 

 

 a) 

baabba

 

 b) 

babbbaa

 

 c) 

bbabbba

 

 d) 

baba

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.  

Consider the pushdown automaton with the following transition rules:

  1. δ(q,0,Z0) = {(q,XZ0)}
  2. δ(q,0,X) = {(q,XX)}
  3. δ(q,1,X) = {(q,X)}
  4. δ(q,ε,X) = {(p,ε)}
  5. δ(p,ε,X) = {(p,ε)}
  6. δ(p,1,X) = {(p,XX)}
  7. δ(p,1,Z0) = {(p,ε)}

From the ID (p,1101,XXZ0), which of the following ID's can NOT be reached?

 

 

 

 a) 

(p,101,XXZ0)

 

 b) 

(p,1101,XZ0)

 

 c) 

(p,ε,XZ0)

 

 d) 

(p,101,XXXZ0)

 

 

 

 

 

5.  

Suppose one transition rule of some PDA P is δ(q,0,X) = {(p,YZ), (r,XY)}. If we convert PDA P to an equivalent context-free grammar G in the manner described in Section 6.3.2 (p. 247), which of the following could be a production of G derived from this transition rule? You may assume s and t are states of P, as well as p, q, and r.

 

 

 

 a) 

[qXp] → 0[rXq][rYp]

 

 b) 

[qXp] → 0[pYq][rZp]

 

 c) 

[qXp] → 0[pYq][qZp]

 

 d) 

[qXp] → 0[qYq][qZp]

 

 

 

 

 

6.  

If we convert the context-free grammar G: 

    S → AS | A
    A → 0A | 1B | 1
    B → 0B | 0

to a pushdown automaton that accepts L(G) by empty stack, using the construction of Section 6.3.1, which of the following would be a rule of the PDA?

 

 

 

 a) 

δ(q,0,B) = {(q,B), (q,ε)}

 

 b) 

δ(q,ε,S) = {(q,AS), (q,A)}

 

 c) 

δ(q,ε,S) = {(q,A)}

 

 d) 

δ(q,ε,A) = {(q,0A)}