GATE CSE concept:context-free-grammars PYQs & Answers

Questions 1–10 of 10. Imported answers require independent review unless marked reviewed.

Consider the following context-free grammar

In the above grammar,

is the start symbol,

and

are terminal symbols, and

and

are non-terminal symbols.

Let

be the language generated by the grammar

. For a string

, let

be the number of

’s in

and

be the number of

’s in

Which of the following statements is/are true?

Your answerSelect all correct options. You can choose more than one.

There is a string

such that

For every string

There is a string

such that

For every string

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following context-free grammar

, where

, and

are the variables (non-terminals),

and

are the terminal symbols,

is the start variable, and the rules of

are described as:

Which ONE of the languages

is accepted by

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

be Context Free Grammars (CFGs) and

be a regular expression. For a grammar

, let

denote the language generated by

Which ONE among the following questions is decidable?

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider a context-free grammar G with the following 3 rules.

S → aS, S → aSbS, S → c

Let w ∈ L(G). Let n_a(w), n_b(w), n_c(w) denote the number of times a, b, c occur in w, respectively. Which of the following statements is/are TRUE?

Your answerSelect all correct options. You can choose more than one.

n_a(w) ≥ n_b(w)

n_a(w) > n_c(w) − 2

n_c(w) = n_b(w) + 1

n_c(w) = n_b(w) * 2

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

be a context-free grammar in Chomsky Normal Form with

and

containing 10 variable symbols including the start symbol

. The string

is derivable from

. The number of steps (application of rules) in the derivation

is ________

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the context-free grammar

below

where

and

are non-terminals, and

and

are terminal symbols. The starting non-terminal is

Which one of the following statements is CORRECT?

Your answerChoose one option.

The language generated by

is not a regular language

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following context-free grammar where the set of terminals is

.\n\n

\n\n

\n\nThe following is a partially-filled LL(1) parsing table. ("blank" denotes that the corresponding cell is empty.)\n\n| |

|\n|---|---|---|---|---|---|---|\n|

| ① | | |

| ② | |\n|

| ③ | |

| ④ |\n|

| | |

| |

| |\n\nWhich one of the following choices represents the correct combination for the numbered cells in the parsing table?

Your answerChoose one option.

①

; ②

; ③

; ④

① blank; ②

; ③

; ④

①

; ② blank; ③ blank; ④

① blank; ②

; ③ blank; ④ blank

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following context-free grammar over the alphabet

with

as the start symbol:

Which one of the following represents the language generated by the above grammar?

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the context-free grammars over the alphabet

given below.

and

are non-terminals.

The language

Your answerChoose one option.

Finite.

Not finite but regular.

Context-Free but not regular.

Recursive but not context-free.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?

I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ∅? III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ? IV. Given a Turing machine M and a string w, is w ∈ L(M)?

Your answerChoose one option.

I and IV only

II and III only

II, III and IV only

III and IV only

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE concept:context-free-grammars PYQs

How to practice concept:context-free-grammars

Question 52

Question 19

Question 25

Question 52

Question 59

Question 39

Question 31

Question 10

Question 37

Question 41