Register

GO Classes DPP | TOC|CFG

• edited by
557 views
7 7 votes

Consider the following context-free grammar $G$, where $S, A$ and $B$ are the variables (nonterminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as:

$$
\begin{aligned}
& S \rightarrow A \mid B \\
& A \rightarrow a A b ~|~ a A ~|~ a \\
& B \rightarrow a B b ~|~ B b ~|~ b
\end{aligned}
$$


Which of the following languages $L(G)$ are accepted by $G$ ?
 

  1. $L(G)=\left\{a^n b^m \mid n \geq m \geq 0\right\}$
     
  2. $L(G)=\left\{a^n b^m \mid m \geq n \geq 1\right\}$
     
  3. $L(G)=\left\{a^n b^m \mid n \neq m, n, m \geq 0\right\}$
     
  4. $L(G)=\left\{a^n b^m \mid n \neq m, n \geq 1, m \geq 1\right\} \cup\left\{a^n \mid n \geq 1\right\} \cup\left\{b^n \mid n \geq 1\right\}$

4 Answers

1 1 vote
If question asked which language describes  the  grammar then answer should be. D  but here they asked which language accepted by this grammar so C, D is answer
1 1 vote
Just try to find out the behaviour accepted by the string and we will find that the grammar wants the two to cases to happen with an OR condition which are as follows:

                                                      b =1 at end with n a's at start ( S -> A )

                                                      a = 1 at start with n b's at start ( S -> B )

AND the conditions of m >= n >= 1 or the vice versa and n>=m>=1 or the vice versa won't clearly fit the reuqired behaviour. Therefore, only three cases left that is,

                                            1) n =! m which is a must because if they are equal machine will reject it

                                            2) n,m > 0 we can only give them lower boundation and that too not relative i.e. n>m is not allowed or vice versa.

                                           3) n,m > 1 another one both are not compulsory but one of them among 2,3 option is a must as it defines the starting point of n, m.

Thus, on seeing options only C and D matches. And since asks about acceptation and not description therefore both will be answer or else it would have been D.
0 0 votes

My approach is for A the langauge = a^na^+b^n which comes as L = {a^ib^j where i>j}

and similarly for B ,L= {a^ib^j where i<j} 

by combining this to for S the language is L = {a^nb^m where n != m } and by this we can also drive option d .

So both option C and D is correct 

Voting & Accepting an answer helps improve the community
Answer:
← Previous · Research Scholarship...Next → · GO Classes DPP | TOC...
← Previous in category · regular languagesNext in category → · GO Classes DPP | TOC...
Position:
Show:

Related questions

6 6 votes
2 2 answers
480
480 views
GO Classes asked Nov 25, 2025
480 views
GO Classes DPP | TOC|CFG
Consider the Context-Free Grammar (CFG) given below:$$S \rightarrow a a S b ~|~ a S b ~|~ \epsilon$$Which of the following inequalities correctly defines the relationship...
11 11 votes
1 1 answer
526
526 views
GO Classes asked Nov 25, 2025
526 views
GO Classes DPP | TOC|DECIDABILITY
Consider the language $L_{Logic}$ defined over the set of all Turing Machines descriptions $\langle M\rangle$ :$L_{Logic}=\{\langle M\rangle \mid \text{ The language } L(...
6 6 votes
6 6 answers
666
666 views
GO Classes asked Nov 25, 2025
666 views
GO Classes DPP | TOC|FSM
Consider a Finite State Automaton (FSA) $\mathbf{M1}$ designed to recognize a specific language over the alphabet $\{0,1\}$. Which of the following best describes the lan...
10 10 votes
2 2 answers
345
345 views
GO Classes asked Nov 25, 2025
345 views
GO Classes DPP | TOC|FSM
The following Finite State Automaton $\mathbf{M2}$ is defined over the alphabet $\{\mathrm{a}, \mathrm{b}\}$ :What is the partition of states into equivalence classes aft...