Finite State Automata

1. Write a regular expression that accepts the following (input symbols: {a, b, c}): All input strings that start with an x, followed by a z, followed by any number of ys or zs, and finally ending with a y followed by an x.

2. In the space below, draw a diagram for the nondeterministic finite automaton (NFA) representing your regular expression (RE) from part (1); make certain that you show your work (you should draw NFAs for smaller components of the RE and then connect them together).

3. On a separate sheet of paper, convert your NFA to a deterministic finite automaton (DFA); make certain that you show all steps involved and that you draw the final DFA.