Written work 2
Due on September 6th @ 3:00 PM (in class, to Drew, or at Engineering front office)
Not accepted late
Question 1

Draw out the expression tree representation of the following regular expresssion

Remember to respect the precedence of regex operators.

Question 2

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

Question 3

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

Question 4

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