“The Language of a Grammar, Inferences and Ambiguity”.
1. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
Answer: d
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees
2. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of
the variable A, A being the starting variable.
a) true
b) false
Answer: a
Explanation: We apply the productions of CFG to infer that certain strings are in the
language of a certain variable.
3. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Recursive Inference and Derivations
d) None of the mentioned
Answer: c
, Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic
structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
Answer: d
Explanation: Parse trees are an alternative representation to derivations and recursive
inferences. There can be several parse trees for the same string.
5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
Answer: a
Explanation: Yes, they are equivalent. Both the terminologies represent the two
approaches of recursive inferencing.6. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
Answer: b
Explanation: A->aA=>aaA=>aab
7. An expression is mentioned as follows. Figure out number of incorrect notations or
symbols, such that a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
1. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
Answer: d
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees
2. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of
the variable A, A being the starting variable.
a) true
b) false
Answer: a
Explanation: We apply the productions of CFG to infer that certain strings are in the
language of a certain variable.
3. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Recursive Inference and Derivations
d) None of the mentioned
Answer: c
, Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic
structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
Answer: d
Explanation: Parse trees are an alternative representation to derivations and recursive
inferences. There can be several parse trees for the same string.
5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
Answer: a
Explanation: Yes, they are equivalent. Both the terminologies represent the two
approaches of recursive inferencing.6. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
Answer: b
Explanation: A->aA=>aaA=>aab
7. An expression is mentioned as follows. Figure out number of incorrect notations or
symbols, such that a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
