Computer Science 456/656: Automata and Formal Languages

Fall 1998

Homework Assignment, due November 10, 1998

  1. Work Exercise 8.1 (a), (c), (e), on page 251 of your textbook.

  2. Work Exercise 8.6 (a), (c), (e), (g), (i), (k) on page 251 of your textbook.

    The book says to prove your answers. The proofs can be very informal. Some of those proofs can be done in a single line. If you can't think of even an informal proof, give some sort of reasoning to support your answer.

  3. Design a deterministic PDA with output that translates infix expressions into postfix (RPN) expressions.

    Let L be the language over the alphabet {a,b,c,+,-,(,),*} consisting of algebraic expressions where variables have one-letter names, and where the minus sign always indicates subtraction.

    For example, if the input string is a-b-c*(a*c-b-(a-b)) then the output string should be ab-cac*b-ab--*

Back to Course Page