next up previous
Next: Exercise 2. Up: Quiz10 Previous: Guidelines.

Exercise 1.

We consider the alphabet $ \Sigma$ = {$ \bf ($,$ \bf )$} consisting of the opening parenthesis and the closing parenthesis. For each of the following grammars, if its generated language is regular, then give a finite automaton recognizing this language, otherwise justify briefly why it is not regular.

$\displaystyle \begin{array}{rl} G_1: & \left\{ \begin{array}{rcl} S & \longmaps...
...& {\bf )} \ B \\  B & \longmapsto & {\bf )} \\  \end{array} \right. \end{array}$ $\displaystyle \begin{array}{rl} G_2: & \left\{ \begin{array}{rcl} S & \longmaps...
...{\bf )} \ E \\  E & \longmapsto & {\varepsilon} \end{array} \right. \end{array}$
   

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


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