Reflection on Context Free, Turing-decidable, and Turing-Recognizable Languages

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

• What is a pushdown automaton? What is a context free grammar?
• What types of problems can context free languages be used to model?
• Give an example of a language that is not context free. What characteristics does the language have that makes a pushdown automaton not a powerful enough tool to recognize this language? Discuss how you would prove this language is not context free. (You do not need to give the proof, but you should include how and why the Pumping Lemma can be applied.)
• What is a Turing-decidable language? What is a Turing-recognizable language?
• What types of problems can be solved with Turing machines?
• (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?