# Context Free Grammar

 Question 1
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 1 Explanation:
 Question 2
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 2 Explanation:
 Question 3
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 3 Explanation:
 Question 4
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 4 Explanation:
 Question 5
CFG (Context Free Grammar) is not closed under:
 A Union B Complementation C Kleene star D Product
ISRO CSE 2018   Theory of Computation
Question 5 Explanation:
 Question 6
Consider the following expression grammar G:
E$\rightarrow$E-T|T
T$\rightarrow$T+F|F
F$\rightarrow$(E)|id
Which of the following grammars is not left recursive, but is equivalent to G?
 A E$\rightarrow$E-T|T T$\rightarrow$T+F|F F$\rightarrow$(E)|id B E$\rightarrow$TE' E'$\rightarrow$TE'|$\in$ T$\rightarrow$T+F|F F$\rightarrow$(E)|id C E$\rightarrow$TX X$\rightarrow$-TX|$\in$ T$\rightarrow$FY Y$\rightarrow$+FY|$\in$ F$\rightarrow$(E)|id D E$\rightarrow$TX|(TX) X$\rightarrow$ -TX|+TX|$\in$ T $\rightarrow$id
GATE CSE 2017 SET-2   Theory of Computation
Question 6 Explanation:
 Question 7
Identify the language generated by the following grammar, where S is start variable.
S$\rightarrow$ XY
X$\rightarrow$ aX|a
Y $\rightarrow$aYb|$\in$
 A $\{a^{m}b^{n}|m\geq n,n \gt 0\}$ B $\{a^{m}b^{n}|m\geq n,n \geq 0\}$ C $\{a^{m}b^{n}|m\gt n,n\geq 0\}$ D $\{a^{m}b^{n}|m\gt n,n \gt 0\}$
GATE CSE 2017 SET-2   Theory of Computation
Question 7 Explanation:
 Question 8
Which of the following statements about parser is/are CORRECT?
I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR
III. SLR is more powerful than Canonical LR.
 A I only B II only C III only D II and III only
GATE CSE 2017 SET-2   Theory of Computation
Question 8 Explanation:
 Question 9
If G is grammar with productions
$S\rightarrow SaS|aSb|bSa|SS|\epsilon$
where S is the start variable, then which one of the following is not generated by G?
 A abab B aaab C abbaa D babba
GATE CSE 2017 SET-1   Theory of Computation
Question 9 Explanation:
 Question 10
Consider the following grammar.

P$\rightarrow$xQRS
Q$\rightarrow$yz|z
R$\rightarrow$w|$\varepsilon$
S$\rightarrow$y

 A {R} B {w} C {w, y} D {w, \$}
GATE CSE 2017 SET-1   Theory of Computation
Question 10 Explanation:
There are 10 questions to complete.

### 8 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,