Lab 03

Problems and topics listed here are for open discussion and practice. Feel free to work with a partner or ask the instructor questions. Towards the end of the lab period we may review some but not necessarily all answers. You are welcome to discuss solutions and strategies to these problems openly with classmates and the instructor outside of lab/class, on Piazza, and office hours.

Reading for next week

Check the reading for next week and read through chapters 2.1 and 2.2.

You do not need to submit any solutions to these problems. This work will not be graded. The purpose of these practice problems is to get more comfortable designing and understanding DFAs and NFAs. You will use the Automata Tutor to design and test machines.

Under "Swarthmore CS46 S18", click "Show" to display the set of active problem sets including the "Lab 3 Practice". For each practice problem, you are allowed 10 attempts to solve the problem. If you get the solution wrong, the site will give you feedback on how to improve your solution. I would encourage you to design/test your solutions on paper first before trying them on the website.

1. Construct a NFA with three states that recognizes the language $1^*(001^+)^*$ over $\Sigma=\{0, 1\}$.
2. Construct a DFA over $\Sigma=\{0, 1\}$ that recognizes the language $L=\{ w \ | \ w $ contains the substring $101$ or $111 \}$.
3. Construct a NFA over $\Sigma=\{0, 1\}$ that recognizes the language $L=\{ w \ | \ w $ contains the substring $101$ or $111 \}$.
4. Construct a regular expression for the language $L=\{ w \ | \ w $ contains the substring $ab \}$ over $\Sigma=\{a, b\}$.
5. Construct a regular expression for the finite language $L=\{ aa,abba \}$ over $\Sigma=\{a, b\}$.
6. Construct a regular expression for the finite language $L=\{ w \ | \ w $ contains exactly two $a$s $\}$ over $\Sigma=\{a, b\}$.