## CSE 431S (Spring 2017) Quiz 2: NFAs and Regular Expressions [ Solution ] [ Given In Class Quiz ]

Set Problems Posted
Solution posted
23 Jan 30 Jan
1. Dragon Book
Textbook exercise #3.7.3 on page 166, using just algorithm 3.20 (which is given on page 159). Remember, their ε is my λ.
Crafting a Compiler
Textbook exercise #17 on page 89, using the structurally inductive technique shown in class
2. Dragon Book
Textbook exercise #3.7.1 on page 166
Crafting a Compiler
Textbook exercise #4 on page 87
3. Consider a strange programming language in which identifiers are constructed using symbols from the alphabet Σ = { a, b, c, d, e } Stranger still, the language requires that all identifiers end in a different letter than they begin. Show the (nondeterministic) finite-state automaton that recognizes identifiers in this language.
4. Consider a language L. Let Rev(L) be the language containing the reverse of each string in L. For example, L contains the string cat if and only if Rev(L) contains the string tac. Show that if L is regular, then Rev(L) is necessarily regular.

Hint: given a regular expression for R, show how to generate a regular expression for Rev(R), using constructions based on the operators of a regular expression.

5. Consider the finite-state machine:
• Describe its language.
• Show the right-linear grammar constructed from this machine.
6. Given the FSA shown below, construct the corresponding FSA that doesn't use lambda.
7. Show an FSA that can recognize comments in the style
```    //   stuff up to the newline
```
assuming the comment characters don't show up in the comment text.