CS46 - Spring 2018

The goals of this lab are to:

Introduce you to Automata Tutor for interactive testing of DFAs and NFAs
Practice developing machines that recognize regular languages
Understand the benefits of non-determinism
Describe the languages recognized by a given machine
Explore closure properties of regular languages

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 an individual assignment. It is OK to discuss approaches at a high level, but you must do your own write-up. Do not share your write up with others, and do not read other student's solutions. Please refer to the syllabus or ask me if you have questions about the policy.

Cloning the starting files

cd ~/cs46
git clone git@github.swarthmore.edu:CS46-S18/lab02-<user>.git ./lab02

where <user> is your ITS username.

At this point, you should have the lab starter code and be ready to start the lab.

I recommend that you read the "Commands for using a git repo" that lists the commands that you will need to submit your lab assignments. In particular, you should understand how to use "git add", "git commit" and "git push".

Part 1: Automata Tutor

For this part, 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 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 the following machines

A DFA for the language $L=\{ \varepsilon \} $ over the alphabet $\Sigma = \{a, b\}$.
A DFA for the language $L=\{ w \ |\ w $ does not contain exactly two $a$s $\} $ over the alphabet $\Sigma = \{a, b\}$.
A DFA for the language $L=\{ w \ |\ 3 \leq |w| \leq 5 \} $ over the alphabet $\Sigma = \{a, b\}$.
A DFA for the language $L=\{ w \ | \ a $ appears $k$ times in $w$ where $k+1$ is divisible by 3 $\} $ over the alphabet $\Sigma = \{a, b\}$.
A DFA for the language $L=\{ w \ | \ $ every $b$ in $w$ is followed by exactly two $a$s $\} $ over the alphabet $\Sigma = \{a, b\}$.
A DFA for the language $L=\{ w\ | \ $ every odd position of $w=w_1w_2w_3\ldots w_n$ is a $1 \} $ over the alphabet $\Sigma = \{0, 1\}$.
A DFA for the language $L=\{ w\ | \ w$ is any non-empty string $ \} $ over the alphabet $\Sigma = \{0, 1\}$.
A DFA for the language $L=\{ w\ | \ w$ begins and ends with the same symbol $ \} $ over the alphabet $\Sigma = \{0, 1\}$. This language includes the empty string.
A NFA for the language $L=\{ w\ | \ w$ contains an odd number of $1$s or exactly two $0$s $\}$ over the alphabet $\Sigma = \{0, 1\}.$ Your NFA should have no more than six states.
A NFA for the language $L=(aa \cup ab)^*$ over the alphabet $\Sigma = \{a, b\}$ .

Part 2: Written Homework

These questions appear in hw02.tex which you can edit to write your solution. You may also review the original pdf template. To compile your document, I recommend running make to automate the building of the image files.

Readme survey

Before submitting the lab. Please complete the short survey in the file Readme.md. Your answers to the questions in this document will not impact your grade, but provide valuable feedback on the difficulty of the assignment and common sources of confusion or roadblocks. Your responses will help make the course better.

Submit

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

$ git add hw02.tex Readme.md
$ git commit -m "completed lab2"
$ 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.

Lab 02