Register

GO Classes | CSE Course | Theory Of Computation

• edited by
479 views
5 5 votes

Consider the following CFG $G$ over $\Sigma = \{\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}\}$:
\[
\begin{array}{rcl}
S & \rightarrow & S\mathbf{a} \;\mid\; \mathbf{d}T \\
T & \rightarrow & \mathbf{b}T\mathbf{b} \;\mid\; \mathbf{c}
\end{array}
\]

How many of the following strings are in $\mathcal{L}(G)$?

 

  • dca
  • cad
  • bcb
  • dtaa


(A) 1
(B) 2
(C) 3
(D) 4
 

2 Answers

0 0 votes
the string dca will be  accepted .  S -> Sa -> dTa -> dca ✅

the format for accepting strings are   d(b^m c  b^m) a^n
Voting & Accepting an answer helps improve the community
Answer:
← Previous · Maths MA 2013 Q. 5Next → · GO Classes Probabili...
← Previous in category · UGC NET CSE | August...Next in category → · UGC NET CSE | Januar...
Position:
Show:

Related questions

4 4 votes
2 2 answers
201
201 views
GO Classes asked Sep 1
201 views
GO Classes DPP | GATE CS | Theory of Computation | Language of CFG
Consider the CFG$$\begin{aligned}S &\to VS \mid cT \\T &\to VT \mid cU \\U &\to \epsilon \mid VU \\V &\to a \mid b\end{aligned} $$Which language is generated by this gram...
2 2 votes
1 1 answer
111
111 views
GO Classes asked Sep 1
111 views
GO Classes DPP | GATE CS | Theory of Computation | Union of CFLs
Which CFG generates the language $L = \{a^m b^n \mid 2m=n \text{ or } m=2n\}$?$S \to aSbb \mid aaSb \mid \epsilon$ $S \to X \mid Y$$X \to aXbb \mid \epsilon$$Y \to aaYb \...
3 3 votes
2 2 answers
1.4k
1.4k views
Rajesh Reddy asked Jan 3, 2022
1,410 views
#Gate CS Applied Course Mock Test
Is this Language a CFL?If yes, Can you please explain the implementation.
0 0 votes
0 0 answers
263
263 views
Shubham Sharma 2 asked Sep 10, 2025
263 views
UGC NET CSE | June 2025 | Part 2 | Question: 72
Which of the following Grammars is/are only Context Free?$\begin{array}{|l|l|l|l|} \hline \textbf{I} & \begin{array}{l} S \rightarrow A b \\ a S \rightarrow a A \\ A \ri...