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 be sure finish reading chapter 1 by Tuesday. When reading about the pumping lemma, think about the following questions, but please be prepared to ask any questions you may have about the lemma, its proof, or its use to class.

• After reading all sections of Chapter 1, what is the best way to show a language is regular?
• How can you show a language is not regular?
• For a given non-regular language, is there an easy way to determine the pumping length $p$?

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 an online resource called the Automata Tutor to design and test machines. Unfortunately, you will need to create yet another login. Please enter your preferred first and last name, as I will be using this information to grade actual lab problems as well. You can use any email you want, but you will need to confirm your email address.

Once you sign in, you can enroll in the CS46 course using the following information:

• Course ID: 158SWARTH
• Course Password: ET2AJNNG

Once enrolled, you should see "Swarthmore CS46 S18". Clicking "Show" will take you to the set of active problem sets including the "Lab 2 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.

Construct the following DFAs on the alphabet $\Sigma=\{a,b\}$.

1. $\{w | w $ contains the substring $ab \}$.
2. $\{w | w $ does not contain the substring $ab \}$.
3. $\{w | w $ contains the substring $baba \}$.
4. $\{w | w $ does not contain the substring $baba \}$.
5. Construct a DFA for the finite language $\{aa, abbba \}$.
   You may want to consider breaking this problem into pieces:
   1. Construct a DFA for the language $\{aa \}$.
   2. Construct a DFA for the language $\{abba \}$.
   3. Use the proof idea from theorem 1.25 (regular languages are closed under union) to construct the final DFA
   You can also skip this advice entirely and design the machine from scratch.
6. Construct a DFA for the language $\{w | w$ contains exactly two $a$s and at least two $b$s $\}$.
   Again, you may want to consider breaking this problem into pieces (or ignoring this advice):
   1. Construct a DFA for $L_1 = \{w | w$ contains exactly two $a$s $\}$.
   2. Construct a DFA for $L_2 = \{w | w$ contains exactly two $a$s $\}$.
   3. Use the footnote on theorem 1.25 to construct the DFA for $L_1 \cap L_2$.

The following problems on the alphabet $\Sigma=\{0,1\}$ will give you some practice with NFAs too.

1. Construct a DFA for the language $\{w | w $ begins with $1$ and ends with $0 \}$.
2. Construct a NFA for the language $\{w | w $ begins with $1$ and ends with $0 \}$.
3. Construct a NFA with only three states for the language $\{w | w $ ends with $00 \}$.