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 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 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 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 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


There are 5 questions to complete.

10 thoughts on “Context Free Grammar”

Leave a Comment