Exercise 2.

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.

G1	$$\left\{\vphantom{ \begin{array}{rcl} S & \longmapsto & A \\ A & ... ...longmapsto & {\bf )} \ B \\ B & \longmapsto & {\bf )} \\ \end{array} }\right.$$$$\begin{array}{rcl} S & \longmapsto & A \\ A & \longmapsto & {\bf... ...\\ B & \longmapsto & {\bf )} \ B \\ B & \longmapsto & {\bf )} \\ \end{array}$$
G2	$$\left\{\vphantom{ \begin{array}{rcl} S & \longmapsto & E \\ E & ... ...f (} \ E \ {\bf )} \ E \\ E & \longmapsto & {\varepsilon} \end{array} }\right.$$$$\begin{array}{rcl} S & \longmapsto & E \\ E & \longmapsto & {\bf (} \ E \ {\bf )} \ E \\ E & \longmapsto & {\varepsilon} \end{array}$$

Answer 2