Reflection on Regular Languages

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

• What is a finite automaton? What is the difference between a DFA and an NFA? When might one use one or the other of these automatons?
• What is a regular language? What does it mean for a finite automaton to recognize a language?
• What types of problems can regular languages be used to model? How would you express a problem in terms of a language and then show it is regular?
• Give an example of a language that is not regular. What characteristics does the language have that makes a finite automaton not a powerful enough tool to recognize this language? Discuss how you would prove this language is not regular. (You do not need to give the proof, but you should include how and why the Pumping Lemma can be applied.)
• (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?