Homework 2
General instructions
At the top of your solutions, be sure to write down the names of anyone you discussed this assignment with or any resources you used!
Please copy the description of the problem as well as your solution.
Submit your work through Gradescope:
Homework 2 part 1: NFAs (autograded)
Homework 2 part 2: NFAs (written answers)
You may find it useful that all problems from the Sipser's Theory of Computation (2nd edition) can be found here.
I will be using autograding on Gradescope for the DFAs that you construct. To facilitate this, you will need to:
Create your machines using the automaton simulator. [demo video]
Take a screenshot to save an image of each machine (you’ll need these for your self-assessment & reflection).
Copy/paste the Plaintext description of each machine (by using the Save button) into a plaintext file called homework2.txt, using the template below.
It is important that you:Name the file exactly homework2.txt (do not add your name, do not capitalize, etc.)
Do not modify the lines that start with “Question” – the numbering that follows is used for checking. You may notice that some of the problems require machines for “simpler” languages as well. The template will first have you submit the machines for the simpler languages before the machine for the intersection/complement.
ONLY have the Plaintext description of your machine between the starting and ending 4 dashes (-)
Keep the starting and ending dashes on NEW lines
Otherwise, your machine will be incorrectly parsed!
You may use the Notes section to provide any notes/questions about the problem for me.
Upload the homework2.txt text file to Gradescope for the Homework 2 part 1: NFAs (autograded) assignment.
For the self-assessment & reflection, you’ll need to have a PDF that includes an image of each machine that you created. This will help you identify what went well (or not so well) and what questions you’d like to ask to clarify your understanding. Submit Part 2 and your self-assessment & reflection via Gradescope using Homework 2 part 2: NFAs (written answers).
Exercises and Problems
From Sipser, 2nd edition (pages 84-85 and 88). Note that Sipser labels some as “Problems” to indicate they are more challenging. You will want to look at them with plenty of time to think about your solution.
Part 1. NFAs (autograded)
Submit the NFAs in the Automaton Simulator plain text format in a text file named homework2.txt.
1.7cdg
1.8b
1.9a
1.10c
From Sipser, 2nd edition (page 88):
1.32 As described, the alphabet is composed of size 3 columns of 0s and 1s. The hint indicates you may be able to construct a machine for the reverse of the language. If you do, I recommend that you first draw it out on paper using the symbols specified. Then, please use the automaton simulator to build your machine. Since you cannot use the alphabet symbols specified, please use the symbols 0,1,2,3,4,5,6,7 with the replacements via the following image:
Part 2: NFAs (written answers)
Submit as a PDF.
Screenshots for the NFAs of Part 1.
1.11 [I realize the solution is in the book. However, I would like you to resist the urge to look at the solution until after you have completed your own. Remember that assignments are designed to help you learn the material!]
1.14b
1.31