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.

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

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

Answer 1