Note: This quiz focuses on techniques. The exam will be more theoretical.

1. Present a finite state automaton (non-determinism and lambda transitions are allowed) to recognize the following regular expression: ...

 
2. Present a Mealy Model finite state machine that ...

 
3. Let L be defined as the language accepted by the finite state automaton A: ...

Using the technique of collapsing states, replacing transition letters by regular expressions, develop the regular expression associated with A that generates L.
 
4. Let L be defined as the language accepted by the finite state automaton A: ...

a.) Present the regular equations associated with each of A's states, solving for L.
b.) Assuming that we designate A as state 1, B as state 2 , etc., use Rijk expressions to compute the regular expression for L.
 
 
5. Let L be defined as the language accepted by the finite state automaton A: ...

a.) Present a new automaton A that accepts Lc the complement of L.
b.) Present a new automaton A' that accepts L.Lc, the concatenation of the language L onto its complement from Lc. You may use non-determinism and lambda-transitions.
c.) Present a new automaton A" that accepts the intersection of the languages L and L", where L" is accepted by the automaton below ...
Your new automaton must be deterministic.
 
6. Let L be defined as the language accepted by the finite state automaton A: ...

Fill in the following table, showing the lambda-closures for each of A's states.
Convert A to an equivalent deterministic finite state automaton. Use states like AC to denote the subset of states {A,C}. Be careful -- lambda-closures are important.
 
7. Analyze the following language, L, proving it non-regular by showing that there are an infinite number of equivalence classes formed by the relation RL defined by: x RL y if and only if for all z xz is inL exactly when yz is in L. You don't have to present all equivalence classes, but you must demonstrate a pattern that gives rise to an infinite number of classes.

 
8. Given the finite state automaton denoted by the transition table shown below, fill in the equivalent states matrix or use the text's technique for determining indistinguishable states. Use this result to create an equivalent, minimal state automaton.

 
9. Show the following grammar is ambiguous by presenting two distinct leftmost derivations of some string in the associated language. You must show every step of the two leftmost derivations of your chosen string.