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 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 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 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 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 6
Consider the following expression grammar G:
E\rightarrowE-T|T
T\rightarrowT+F|F
F\rightarrow(E)|id
Which of the following grammars is not left recursive, but is equivalent to G?
A
E\rightarrowE-T|T
T\rightarrowT+F|F
F\rightarrow(E)|id
B
E\rightarrowTE'
E'\rightarrowTE'|\in
T\rightarrowT+F|F
F\rightarrow(E)|id
C
E\rightarrowTX
X\rightarrow-TX|\in
T\rightarrowFY
Y\rightarrow+FY|\in
F\rightarrow(E)|id
D
E\rightarrowTX|(TX)
X\rightarrow -TX|+TX|\in
T \rightarrowid
GATE CSE 2017 SET-2   Theory of Computation
Question 7
Identify the language generated by the following grammar, where S is start variable.
S\rightarrow XY
X\rightarrow aX|a
Y \rightarrowaYb|\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 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 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 10
Consider the following grammar.

P\rightarrowxQRS
Q\rightarrowyz|z
R\rightarroww|\varepsilon
S\rightarrowy

What is FOLLOW (Q) ?
A
{R}
B
{w}
C
{w, y}
D
{w, $}
GATE CSE 2017 SET-1   Theory of Computation
There are 10 questions to complete.

10 thoughts on “Context Free Grammar”

Leave a Comment