# Homework on Regular Expressions and NFA

(part of [CC 2022](https://github.com/alexhkurz/compiler-construction-2022/blob/master/lecture-by-lecture.md))

("the book" refers to [Introduction to Automata Theory, Languages, and Computation](http://ce.sharif.edu/courses/94-95/1/ce414-2/resources/root/Text%20Books/Automata/John%20E.%20Hopcroft,%20Rajeev%20Motwani,%20Jeffrey%20D.%20Ullman-Introduction%20to%20Automata%20Theory,%20Languages,%20and%20Computations-Prentice%20Hall%20%282006%29.pdf))

## Summary of Lecture 2.2

In the [lecture](https://hackmd.io/@alexhkurz/HkoNj8mmU), we worked through Exercise 2.5.3.a and used it to explain how NFAs and regular expressions work. Here is a quick summary:


(Actually, we fused all the final states into one final state.)

## Homework

To deepen and test your knowledge write out the NFAs and regular expressions for the languages specified in the following exercises:

- <font color=red> Write in your report regular expressions for the languages in Example 2.3.4 and Example 2.5.3. Deadline Sunday. </font>
- Read Section 2.3.2 for the definition of NFA.
- Section 2.3.3 and 2.3.4 define the notion of **language of an NFA**. All it says is that a word is in the language of an NFA, if there is a computation taking the word from the initial state to some final state.
- Read Section 3.1.1 "The Operators of Regular Expressions".
- Read Example 3.2.
- Do Exercise 3.2.4 about converting regular expressions to NFAs:

<!--
Ask any questions on the discussion forum.

## Coming Soon

- **Convert [these NFAs](https://github.com/alexhkurz/compiler-construction-2021/blob/master/Sources/nfas-assignment1.pdf) to DFAs**. Compare with the DFAs from the [first homework](https://hackmd.io/@alexhkurz/rycnvMvgu).
- Read Section 2.5.5 on eliminating $\epsilon$-transitions.
- **Convert [these $\epsilon$-NFAs](https://github.com/alexhkurz/compiler-construction-2021/blob/master/Sources/enfas-assignment1.pdf) to DFAs**. Compare with the NFAs above.
- Read Section 3.1.2 on the definition of regular expressions
- Read Section 3.2.3 on converting regular expressions to automata

For further practice for midterm and final, try some of the exercises in Sections 2.3.7 and 2.5.6.