# Context Free Grammar

 Question 1
Consider the context-free grammar $G$ below
$S\rightarrow aSb \;| \;X$
$X\rightarrow aX \;| \;Xb \;|\; a\;|\; b$
where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non-terminal is $S$.
Which one of the following statements is CORRECT?
 A The language generated by $G \text{ is }(a + b)^*$ B The language generated by $G \text{ is } a^*(a + b)b^*$ C The language generated by $G \text{ is }a^*b^*(a + b)$ D The language generated by $G$ is not a regular language
GATE CSE 2023   Theory of Computation
Question 1 Explanation:
 Question 2
Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$.

$\begin{array}{lll} S & \rightarrow & d \: a \: T \mid R \: f \\ T & \rightarrow & a \: S \: \mid \: b \: a \: T \: \mid \epsilon \\ R & \rightarrow & c \: a \: T \: R \: \mid \epsilon \end{array}$

The following is a partially-filled LL(1) parsing table.

Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?

 A A B B C C D D
GATE CSE 2021 SET-1   Theory of Computation
Question 2 Explanation:

 Question 3
The language which is generated by the grammar $S \rightarrow a S a\mid b S b\mid a\mid b$ over the alphabet of {a,b} is the set of
 A Strings that begin and end with the same symbol B All odd and even length palindromes C All odd length palindromes D All even length palindromes
ISRO CSE 2020   Theory of Computation
Question 3 Explanation:
 Question 4
Context free languages are closed under
 A union, intersection B union, kleene closure C intersection, complement D complement, kleene closure
ISRO CSE 2020   Theory of Computation
Question 4 Explanation:
 Question 5
A CFG (Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form $\mathrm{A} \rightarrow \mathrm{BC}$ or $\mathrm{A} \rightarrow \mathrm{a}$. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is:
 A 2x-1 B 2x C 2x+1 D $2^{x}$
ISRO CSE 2018   Theory of Computation
Question 5 Explanation:

There are 5 questions to complete.

### 11 thoughts on “Context Free Grammar”

1. Please add a function to Sort the PYQs like (a) Older to Latest and (b) Latest to Older

• Dear Tirth,
It’s already sorted from latest to Older order for Subject and Topicwise practice. From the analysis it is observed that practice of latest questions are very important.

2. Question no 25th answer is wrong ,
it should be option A.

• Thank you shivam,
We have updated the answer.

3. qes no 9 is wrong

• production is S→SaS∣aSb∣bSa∣SS∣ϵ

• Thank You devendra,
We have updated the question.