**CSCE A351 Midterm Problems**

The midterm is open book and open notes. You are free to use a calculator or any other computing devices you feel may be useful as long as you are not communicating with other people or searching online. Since this test covers so much material I have decided to tell you specific types of problems that will be on the exam so that you can direct your studies appropriately. The exam covers the material up to P/NP, but does not include the P/NP material.

- Create a DFA based on a problem description
- Convert an NFA (either regular or epsilon) to a DFA
- Turn a DFA into a regular expression.
- Generate a regular expression given a description of the language.
- Generate a context-free grammar given a description of the language.
- Use the pumping lemma to show that a language is either not regular or not context free
- Describe a Turing Machine given a description of the language
- Determine if a language is decidable or undecidable and why
- And some short-answer questions that could cover anything :-) But will mostly focus on theory as opposed to a problem to work through (e.g. why properties of the pumping lemma hold, decidability and undecidable problems, etc.)