Register

GO Classes DPP | TOC|GRAMMAR

204 views
3 3 votes

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

$$
\begin{aligned}
& S \rightarrow a X \mid Y c \\
& X \rightarrow a X b \mid a b \\
& Y \rightarrow b Y c \mid b c
\end{aligned}
$$


Which ONE of the following languages $L(G)$ is generated by $G$ ?

  1. $L(G)=\left\{a^n b^n \mid n \geq 1\right\} \cup\left\{b^n c^n \mid n \geq 1\right\}$
     
  2. $L(G)=\left\{a^{n+1} b^n \mid n \geq 1\right\} \cup\left\{b^n c^{n+1} \mid n \geq 1\right\}$
     
  3. $L(G)=\left\{a^n b^{n+1} \mid n \geq 1\right\} \cup\left\{b^{n+1} c^n \mid n \geq 1\right\}$
     
  4. $L(G)=\left\{a^n b^n c \mid n \geq 1\right\} \cup\left\{a b^n c^n \mid n \geq 1\right\}$

1 Answer

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

Related questions

3 3 votes
2 2 answers
312
312 views
GO Classes asked Oct 30, 2025
312 views
GO Classes DPP | TOC|GRAMMAR
Consider the following context-free grammar $G$, with the set of variables $\{S, A, C, X, Y\}$, the set of terminal symbols $\{a, b, c\}$, and $S$ as the start variable. ...
3 3 votes
1 1 answer
288
288 views
GO Classes asked Oct 30, 2025
288 views
GO Classes DPP | TOC|CFL
Consider the following languages. Which of them are context-free?$$L_1:\left\{w \in\{a, b\}^* \mid\right.$$$w$ contains a string of the form $a^n b^n$ as a subsequence, f...
3 3 votes
1 1 answer
274
274 views
GO Classes asked Oct 30, 2025
274 views
GO Classes DPP | TOC|CFL
Which of the following languages are context-free? For any string $s$, let $n_x(s)$ denote the number of occurrences of the symbol $x$ in $s$.$L_1:\left\{w \in\{a, b\}^* ...
3 3 votes
2 2 answers
323
323 views
GO Classes asked Oct 30, 2025
323 views
GO Classes DPP | TOC|DFA
Which of the regular expressions given below represents the language accepted by this DFA?l. $\left(0+101^* 01+10\left(1+010^* 10\right)^* 01\right)^*$II. $\left(0+1\left...