Due 11:59pm Wednesday, 14 February 2018

The goals of this lab are to:

- Explore more NFA and regex features of Automata Tutor
- Practice developing machines that recognize regular languages
- Understand the benefits of non-determinism
- Describe the languages recognized by a given machine
- Understand the connection between regular expressions and DFAs/NFAs
- Identify and prove when a language is not regular using the pumping lemma.

This assignment consists of two parts: an online part for designing automata and a written homework portion. Write your written solution using $\LaTeX$. Submit the written portion using github. This is a partnered assignment. You may work with one partner and submit a joint assignment. It is OK to discuss approaches at a high level with other students that are not your partner, but you must do your own write-up. Do not share your write up with other groups, and do not read other group's solutions. Please refer to the syllabus or ask me if you have questions about the policy.

Cloning the starting files

wherecd ~/cs46git clone git@github.swarthmore.edu:CS46-S18/lab03-<group>.git ./lab03

Part 1: Automata Tutor

For this part, you will use the Automata Tutor to design and test machines. If working as a partnership, only one partner needs to submit a design.
Once signed in, you should see "Swarthmore CS46 S18". Clicking "Show" will take you to the set of active problem sets including the "Lab 3 Graded". For each problem, you are allowed 4 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. Additionally, you are encouraged to attempt the practice problems first so that you understand how to use the system.

- Construct a NFA for the language $L=\{ 100 \} $ over the alphabet $\Sigma = \{0, 1\}$.
- Let $\Sigma = \{a, b\}$, let $L_1 = \{ w\ |\ $ the length of $w$ is even $\}$, and let $L_2 = \{ w \ | \ w$ begins and ends with $a \}$. Construct a NFA for the Language $L=L_1 \cup L_2$.
- Construct a NFA for $L=L_1\circ L_2$ using $L_1, L_2$ defined in the previous problem.
- Let $\Sigma = \{a, b\}$, let $L_3 = \{ w \ | \ w $ has an odd number of $a$s or an odd number of $b$s $\}$. Construct a NFA for $L={L_3}^*$. You can use the constructions used to prove closure properties of NFAs, but if you think carefully about what $L$ looks like, you may be able to design a simpler machine.
- Convert the following NFA to a DFA that recognizes the same language.
- Convert the following NFA to a DFA that recognizes the same language.
- Write a regular expression for the language \[ \{ w \ | \ w \mathrm{\ contains\ the\ string\ } baa \mathrm{\ or\ ends\ in\ } ab \} \].
- Let $\Sigma = \{0, 1\}$ and let $L = \{ w \ | \ w$ contains the substring $0ab1$ or $1ab0$ where $a, b \in \Sigma \}$. Construct a DFA that recognizes $L$. You are
*strongly*encouraged to plan on paper, or multiple sheets of paper first. - Construct a NFA that recognizes $L$ defined in the previous problem. This machine should have many fewer states than the DFA.

Part 2: Written Homework

These questions appear in Readme survey

Before submitting the lab. Please complete the short survey in the file Submit

Once you have edited the files, you should publish your changes using the following steps:

$git add hw03.tex Readme.md$git commit -m "completed lab3"$git push

If you make changes to files after your push and want to share these changes, repeat the add, commit, push loop again to update the github server.

To recap, the git commit cycle is `git add, git commit, git
push`. Don't forget to `git push` when you have completed an
assignment.

You can review the basic git commands on the github help pages. Eventually, you should get in the habit of using git status to see if everything has been published, but we will talk about this more throughout the semester.

Remember
to *add, commit, push*. You may commit and push as often as you
like, and only the most recent push will be graded.