Register

GO Classes DPP | TOC|CFG

278 views
5 5 votes

Let $G=(\{S, A, B\},\{a, b\}, R, S)$ be a context-free grammar, where the rules $R$ are:

$$
S \rightarrow a B|b A, \quad A \rightarrow a| a S|b A A, \quad B \rightarrow b| b S \mid a B B .
$$


Which of the following is true about $L(G)$ ?
 

  1. $L(G)$ consists of all strings over $\{a, b\}$ with an equal number of $a$ 's and $b$ 's.
     
  2. $L(G)$ consists of all non-empty strings over $\{a, b\}$ with an unequal number of $a$ 's and $b$ 's.
     
  3. $L(G)$ consists of all strings over $\{a, b\}$ where the number of $a$ 's is greater than the number of $b$ 's.
     
  4. $L(G)$ is regular.

1 Answer

2 2 votes

The grammar cannot generate the null string, but Option A implies that it does.

Ideally, Option A should have read: "L(G) consists of all non-empty strings..."

Best possible answer is Option A

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
1 1 answer
332
332 views
GO Classes asked Nov 22, 2025
332 views
GO Classes DPP | TOC|CFG
Let $G=(\{S\},\{(,)\}, R, S)$ be a context-free grammar, where the set of rules $R$ is$$S \rightarrow(S) S \mid \epsilon$$Which of the following statements is true? $G$ i...
5 5 votes
1 1 answer
366
366 views
GO Classes asked Nov 22, 2025
366 views
GO Classes DPP | TOC|DECIDABILITY
Define the language:$L=\{\langle M\rangle \mid M \text{ is a TM and there exists an input } w \text{ of length at most 100 such that} ~M \text{ halts on } w\}$.Which of t...
3 3 votes
1 1 answer
356
356 views
GO Classes asked Nov 22, 2025
356 views
GO Classes DPP | TOC|FSM
Consider a sequential circuit that detects the input sequence $\mathbf{101}$ on a serial input line $x$ (one bit per clock cycle) and produces an output $z$ as follows:In...
3 3 votes
1 1 answer
400
400 views
GO Classes asked Nov 22, 2025
400 views
GO Classes DPP | TOC|DFA
Let $L$ be the language over $\Sigma=\{0,1\}$ defined by:$$L=\{w \mid \text { the binary number represented by } w \text { is divisible by } 11\} .$$(Interpret $w$ as a b...