MCQ Computer Science

# Automata Theory Multiple Choice Question & Answers (MCQs) set-15

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

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

Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.
3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned

Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.
4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6

Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
5. State true or false:
Statement: A CNF parse tree’s string yield (w) can no longer be 2h-1.
a) true
b) false

Explanation: It is the parse tree theorem which states:
Given: Suppose we have a parse tree for a string w, according to a CNF grammar, G=(V, T, P, S). Let h be the height of the parse tree. Now, Implication: |w|<=2h-1.
8. Which of the following can be a LALR parser generator?
a) YACC
b) GNU Bison
c) YACC and GNU Bison
d) None of the mentioned

Explanation: YACC is a computer code for UNIX operating system which generates a LALR parser. On the other hand GNU Bison or Bison can generate LALR and GLR parsers.
9. Which of the following parsers do not relate to Bottom up parsing?
a) LL parser
b) Recursive descent parser
c) Earley parsers
d) All of the mentioned

Explanation: All the following mentioned are top down parsers and begin their operation from the starting symbol.
10. Which of the following is true for a predictive parser?
a) Recursive Descent parser
b) no backtracking
c) Recursive Descent parser and no backtracking
d) None of the mentioned

Explanation: Predictive parsing is possible only for the class of LL-grammars, which are the CFG for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input.
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

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

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

Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.
14. Number of states require to simulate a computer with memory capable of storing ‘3’ words each of length ‘8’.
a) 3 * 28
b) 2(3*8)
c) 2(3+8)
d) None of the mentioned

Explanation: 2(m*n) states requires .
15. FSM with output capability can be used to add two given integer in binary representation. This is
a) True
b) False
c) May be true
d) None of the mentioned