250+ TOP MCQs on The Language of a Grammar, Inferences and Ambiguity and Answers

Automata Theory Problems on “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
Clarification: 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
Clarification: 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) Both Recursive Inference and Derivations
d) None of the mentioned

Answer: c
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
c) 2 Error
d) Invalid Expression

Answer: a
Clarification: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG, the language of G, denoted by L(G), is the set of terminal strings that have derivations from the start symbol.

8. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned

Answer: b
Clarification: Push down automata accepts context free language.

9. Which among the following is the correct option for the given grammar?
G->X111|G1,X->X0|00
a) {0^a1^b|a=2,b=3}
b) {0^a1^b|a=1,b=5}
c) {0^a1^b|a=b}
d) More than one of the mentioned is correct

Answer: a
Clarification: Using the recursive approach, we can conclude that option a is the correct answer, and its not possible for a grammar to have more than one language.

10. Which of the following the given language belongs to?
L={a^mb^mc^m| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned

Answer: d
Clarification: The given language is neither accepted by a finite automata or a push down automata. Thus, it is neither a context free language nor a regular language.

11. Choose the correct option:
Statement: There exists two inference approaches:
a) Recursive Inference
b) Derivation

a) true
b) partially true
c) false
d) none of the mentioned

Answer: a
Clarification: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.

12. Choose the correct option:
Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true

Answer: b
Clarification: Both the statements are false. Recursive Inference, using productions from body to head. Derivations, using productions from head to body.

13. Which of the following statements are correct for a concept called inherent ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned

Answer: a
Clarification: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.

14. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned

Answer: a
Clarification: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can only have ambiguous grammars.