Quiz 2: NFAs and Regular Expressions

Quiz | Posted (Thursdays) |
Given in class (Thursdays) |
||
---|---|---|---|---|

17 | Jan | 24 | Jan |

- Textbook exercise #17 on page 89, using the structurally inductive technique shown in class.
- Textbook exercise #4 on page 87.
- 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.
- Textbook problem #21 on page 90.
*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. - Consider the finite-state machine:
- Describe its language.
- Show the right-linear grammar constructed from this machine.

- Given the FSA shown below, construct the corresponding FSA that
doesn't use lambda.
- 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.