Due on September 6th @ 3:00 PM (in class, to Drew, or at Engineering front office) |

Not accepted late |

Due on September 6th @ 3:00 PM (in class, to Drew, or at Engineering front office) |

Not accepted late |

Draw out the expression tree representation of the following regular expresssion

(ab*|ac)d

Remember to respect the precedence of regex operators.

Convert the regular expression from above into an ε-NFA (i.e. an NFA with ε-edges) using Thompson's algorithm.

Use the ε-elimination technique to remove the ε-edges from the previous ε-NFA.

Let *DotList* be a language such that:

- The empty string is in the language
- The single terminal
**dot**is in the language - Sequences of more than 1
**dot**terminal separated by the**comma**terminal are in the language. e.g.:**dot****comma****dot****dot****comma****dot****comma****dot**

No other strings are in the language

Write an unambiguous grammar that recognizes *DotList*