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
cd ~/cs46
git clone git@github.swarthmore.edu:CS46-S18/lab03-<group>.git ./lab03
where
<group> is your group name. It is probably best to just log into
github and find your repo name there.
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". Additionally, if your are working with a partner, it becomes more important to push more frequently to share changes with your partner. Your partner can then git pull your changes. In the event of merge conflicts, consult the merge conflict guide, ask on Piazza, or stop by my office. The best way to avoid merge conflicts is to work on the writeup together and add,commit,push changes when you take a break.
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 hw03.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 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.