95 views
0 0 votes

Consider the grammar $$S\rightarrow aS\mid Sb\mid b$$ Which of the following statements are correct?

  1. The given grammar is a Type $3$ grammar.
     
  2. The given grammar is a Type $2$ grammar.
     
  3. The language generated by the grammar is $a^*b^+$ and is therefore regular.
     
  4. No Type $3$ grammar can generate the same language.

1 Answer

0 0 votes

Every production has exactly one nonterminal on the left-hand side.

$S \rightarrow \alpha$

Therefore, the given grammar satisfies the definition of a context-free grammar. 

Hence, it is a Type $2$ grammar.

However, it is not a Type $3$ grammar in the standard linear form because it contains both

$S\rightarrow aS$ which is right-linear, 

and $S\rightarrow Sb$ which is left-linear.

A regular grammar must be consistently right-linear or consistently left-linear.

Therefore, the given grammar is Type $2$ but not Type $3$.

So A is false and B is true.

Now consider the language generated by the grammar.

Repeated use of $S\rightarrow aS$ can add any number of $a$'s to the left.

Repeated use of $S\rightarrow Sb$ can add any number of $b$'s to the right.

Finally,

$S\rightarrow b$ terminates the derivation.

Hence every generated string is of the form $a^ib^j, i\geq0,\ j\geq1$.

$\therefore L(G)=a^*b^+$.

Since $a^*b^+$ is a regular language, there exists an equivalent Type $3$ grammar that generates the same language.

Thus,

Answer : B, C

 

Key point: The type of a particular grammar and the type of the language it generates are not necessarily the same.

A Type $2$ grammar can generate a regular language.

Answer:
Position:
Show:

Related questions

1 1 vote
1 1 answer
106
106 views
GO Classes asked Sep 3
106 views
Consider the grammar $G$ with start variable $A$ and productions $:$$$\begin{aligned}A &\to aB \mid bC \\B &\to aB \mid \epsilon \\C &\to aD \mid A \mid bC \\D &\to aD \m...
0 0 votes
1 1 answer
97
97 views
GO Classes asked Sep 24
97 views
Let $\Sigma=\{0,1\}.$Which of the following are valid examples?$A=\{01\}, \qquad B=\{0^n1^n\mid n\ge0\}$where $A$ is regular, $B$ is nonregular, and $A\subseteq B$. $C=\{...
0 0 votes
1 1 answer
83
83 views
GO Classes asked Sep 24
83 views
Let \(I \subseteq \Sigma^*\) be any nonregular language.For every string \(w \notin I\), define $R_w = \Sigma^* - \{w\}.$Now consider $K = \bigcap_{w \notin I} R_w.$What ...
0 0 votes
1 1 answer
100
100 views
GO Classes asked Sep 24
100 views
For every $n\geq 0$, define $L_n=\{a^nb^n\}$.Which statement is correct?Every $L_n$ is nonregular, but $\bigcup_{n=0}^{\infty}L_n$ is regular. Every $L_n$ is regular, and...