General instructions

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

2. Please copy the description of the problem as well as your solution. 

3. Submit your work through Gradescope:

   1. Homework 3 part 1: Regular Expressions to NFAs (autograded)

   2. Homework 3 part 2: Regular Expressions (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:

1. Create your machines using the automaton simulator. [demo video]

2. Take a screenshot to save an image of each machine (you’ll need these for your self-assessment & reflection).

3. Copy/paste the Plaintext description of each machine (by using the Save button) into a plaintext file called homework3.txt, using the template below.
   
   It is important that you:

   • Name the file exactly homework3.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.

4. Upload the homework3.txt text file to Gradescope for the Homework 3 part 1: Regular Expressions to NFAs (autograded) assignment.

5. 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 3 part 2: Regular Expressions (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. Regular Expressions to NFAs ( autograded)

Submit the NFAs (in the Automaton Simulator plain text format) in a text file named homework3.txt.

• 1.19bc [provide the FINAL machine only, but keep your work for your self-assessment & reflection]

Part 2: Regular Expressions (written answers)

• Screenshot of the NFA (and intermediate work) for Part 1.

• 1.18abdgi

• 1.20begh

• 1.21b [rip states in the order: 1, 2, 3]

• 1.24f

• 1.25

• 1.40 (Labeled as a Problem -- be sure to give yourself enough time to think about this!)