next up previous
Next: Exercise 2. Up: Final-2003 Previous: Guidelines.

Exercise 1.

We consider the alphabet $ \Sigma$ = {a, b, c}. For each of the following languages over $ \Sigma$ give a deterministic automaton that recognizes this language
  1. L1 is the language consisting of all words over $ \Sigma$ except the word w = ba.
  2. L2 is the language consisting of all words over $ \Sigma$ for which the word w = ba is not a factor. This means that a word over $ \Sigma$ belongs to L2 if and only if it does not match the LEX regular expression [a-c]*ba[a-c]*.

Answer 1  
\fbox{ \begin{minipage}{12 cm} \mbox{ } \\ \mbox{ } \\ \mbox{ } \\ \mbox{ } \... ...\mbox{ } \\ \mbox{ } \\ \mbox{ } \\ \mbox{ } \\ \mbox{ } \\ \end{minipage}}

next up previous
Next: Exercise 2. Up: Final-2003 Previous: Guidelines.
Marc Moreno Maza
2004-12-02