Lab 03

Due 11:59pm Wednesday, 14 February 2018

The goals of this lab are to:

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<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.

    1. Construct a NFA for the language $L=\{ 100 \} $ over the alphabet $\Sigma = \{0, 1\}$.
    2. 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$.
    3. Construct a NFA for $L=L_1\circ L_2$ using $L_1, L_2$ defined in the previous problem.
    4. 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.
    5. Convert the following NFA to a DFA that recognizes the same language.
    6. Convert the following NFA to a DFA that recognizes the same language.
    7. Write a regular expression for the language \[ \{ w \ | \ w \mathrm{\ contains\ the\ string\ } baa \mathrm{\ or\ ends\ in\ } ab \} \].
    8. 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.
    9. 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 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.

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

    $ git add hw03.tex
    $ 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.