CSCI 250 (GOLDWEBER)
Spring 08: 2/26/08
Homework 5
Due Date: Monday, March 3, 2008.
There is a possible 42 points for this homework assignment.
Problem 1. (4 pts.) Exercise 3.22 on page 114 of the text.
Problem 2. (4 pts.) Exercise 3.23 on page 114 of the text.
Problem 3. (8 pts.) Exercise 3.24 on page 114 of the text.
Problem 4. (5 pts.) Exercise 3.25 on page 114 of the text.
Problem 5. (8 pts.) In both cases below, a transition table is given for a PDA with initial state q0 and accepting state q2. Describe in each case the language that is accepted.
a)
| Move No. | State | Input | Stack Symbol | Move(s) |
|
| 1 | q0 | a | Z0 | (q1,aZ0) |
| 2 | q0 | b | Z0 | (q1,bZ0) |
| 3 | q1 | a | a | (q1,a),(q2,a) |
| 4 | q1 | b | a | (q1,a) |
| 5 | q1 | a | b | (q1,b) |
| 6 | q1 | b | b | (q1,b),(q2,b) |
| (all other combinations) | none |
b)
| Move No. | State | Input | Stack Symbol | Move(s) |
|
| 1 | q0 | a | Z0 | (q0,XZ0) |
| 2 | q0 | b | Z0 | (q0,XZ0) |
| 3 | q0 | a | X | (q0,XX) |
| 4 | q0 | b | X | (q0,XX) |
| 5 | q0 | c | X | (q1,X) |
| 6 | q0 | c | Z0 | (q1,Z0) |
| 7 | q1 | a | X | (q1,) |
| 8 | q1 | b | X | (q1,) |
| 9 | q1 | | Z0 | (q2,Z0) |
| (all other combinations) | none |
Problem 6. (4 pts.) Show that if L is accepted by a PDA, then L is accepted by a PDA that never crashes (i.e., for which the stack never empties and no configuration is reached from which there is no move defined).
Problem 7. (9 pts.) Suppose M1 and M2 are PDAs accepting L1 and L2 respectively. Describe a procedure for constructing a PDA accepting each of the following languages. Note that in each case, nondeterminism will be necessary. Be sure to say precisely how the stack of the new machine works: no relationship is assumed to exist between the stack alphabets of M1 and M2
a) Union: L1 ∪ L2
b) Concatenation: L1L2
c) Kleene-stardom: L1*
File translated from
TEX
by
TTH,
version 3.74.
On 26 Feb 2008, 12:06.