edited by
12,634 views
67 votes
67 votes

Consider the following grammars. Names representing terminals have been specified in capital letters.
$$\begin{array}{llll}\hline \text{$G1$ :}  &  \text{stmnt} & \text{$\rightarrow$} & \text{WHILE (expr) stmnt} \\%\hline 
\text{}  &  \text{stmnt} & \text{$\rightarrow$} & \text{OTHER} \\%\hline 
\text{}  &  \text{expr} & \text{$\rightarrow$} & \text{ID} \\\hline 
\text{ $G2$ :}  &  \text{stmnt} & \text{$\rightarrow$} & \text{WHILE (expr) stmnt} \\%\hline
\text{}  &  \text{stmnt} & \text{$\rightarrow$} & \text{OTHER} \\%\hline
\text{}  &  \text{expr} & \text{$\rightarrow$} & \text{expr $+$ expr} \\%\hline
\text{}  &  \text{expr} & \text{$\rightarrow$} & \text{expr $*$ expr} \\%\hline
\text{}  &  \text{expr} & \text{$\rightarrow$} & \text{ID} \\\hline  \end{array}$$

Which one of the following statements is true?

  1. $G_1$ is context-free but not regular and $G_2$ is regular
  2. $G_2$ is context-free but not regular and $G_1$ is regular
  3. Both $G_1$ and $G_2$ are regular
  4. Both $G_1$ and $G_2$ are context-free but neither of them is regular
edited by

3 Answers

Best answer
74 votes
74 votes

Regular grammar is either right linear or left linear. A left linear grammar is one in which there is at most $1$ non-terminal on the right side of any production, and it appears at the left most position. Similarly, in right linear grammar non-terminal appears at the right most position.

Here, we can write a right linear grammar for $G1$ as

$S \rightarrow w(E$
$E \rightarrow id)S$
$S \rightarrow o$

(w - WHILE, o - OTHER)

So, $L(G1)$ is regular.

Now for $G2$ also we can write a right linear grammar:

$S \rightarrow w(E$
$E \rightarrow id)S$
$E \rightarrow id+E$
$E \rightarrow id*E$
$S \rightarrow o$

making its language regular. 

So, both $G1$ and $G2$ have an equivalent regular grammar. But given in the question both these grammars are neither right linear nor left linear and hence not a regular grammar. So, D must be the answer. 

http://www.cs.odu.edu/~toida/nerzic/390teched/regular/grammar/reg-grammar.html

edited by
4 votes
4 votes
Answer:

Related questions

42 votes
42 votes
7 answers
4
Ishrat Jahan asked Oct 30, 2014
7,776 views
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression $R$?