Due

Solutions are available.

Problem 0: Review old homeworks and exams.

Problem 1: Give a grammar that generates the same language as the regular expression (a + b)^*(a^* + (ba)^*).

Problem 2: Give a pushdown automaton that accepts the language {aⁿb^m | m > n >= 0}.

Problem 3: For each language given below either give a context free grammar for that language or prove that it is not context free.

• {aⁿbⁿaⁿbⁿ | n >= 0}
• {aⁿbⁿa^mb^m | m, n >= 0}

Problem 4:

• Give a grammar that generates postfix expressions using operators +, -, *, and /. Use the terminal "id" to stand for any variable name and "lit" to stand for integer literals.
• Show a derivation of "id lit id + *" in your grammar.
• Convert your grammar to Chomsky Normal Form.
• Show, using the dynamic programming algorithm, that "id id + lit lit id - * *" can be generated by the grammar.

Problem 5: Construct a Turing machine that changes all the a's on its tape to b's and vice versa. Show all the states and all the transitions. Trace your machine's operation for five steps on input ">.abba"

Problem 6: Construct a Turing machine that, given two strings of a's and b's as input, halts if and only if the second string is longer than the first string. Use the abbreviated notation for composing simple Turing Machines into complex ones.

Problem 7: Consider a modified single-tape Turing Machine that has two read/write heads. At each step, the machine changes states and moves its heads according to the current state and what symbol is under the two heads. Is this machine any more powerful than a standard Turing Machine? Explain your answer.

Problem 8: Describe a nondeterministic Turing Machine that, given a list of 2n numbers, determines if it is possible to split them into two groups each having the same sum.

Problem 9: There is a question in A. Tanenbaum's textbook Modern Operating Systems that can be paraphrased as follows: given the source code of a program, can you determine whether that program will be CPU-bound or I/O-bound? Discuss this question in light of your new found knowledge of the halting problem and other unsolvable problems.