Reflection on Computational Models

Write up your answers to the following prompts and submit a pdf file on Kit.

• For each of the following languages, name the least powerful type of machine that will accept it, and prove your answer. (Hint: a finite state automata is less powerful than a pushdown automata, which in turn is less powerful than a Turing Machine.) For example, to prove a language needs a PDA to accept it, you would use the Pumping Lemma to show it is not regular, and then build the PDA or CFG that accepts the language.
  1. L₁ = {aⁱ b^j aⁱ b^j | i, j ≥ 0 }
  2. P = {u | uw ∈ L}, prefixes of L, where L is a language over {a, b, c} and L = {w | w ends with an a}
  3. L₂ = {aⁱ b²ⁱ | i ≥ 0}
• How did you approach working on the problem? What things did you need to consider with each of the different models of computation?
• (Overall reflection) Reflect on what you have learned so far from the readings, in-class discussions, and assignments. What has been new or surprising? What has been the most interesting? What has been the most challenging? How has what you have learned so far changed or deepened your understanding of computers or computing?