MCQ Computer Science

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

1. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be ____________ under an operation op.
a) open
b) closed
c) decidable
d) none of the mentioned

Explanation: If two regular languages are closed under an operation op, then the resultant of the languages over an operation op will also be regular.

2. Suppose a regular language L is closed under the operation halving, then the result would be:
a) 1/4 L will be regular
b) 1/2 L will be regular
c) 1/8 L will be regular
d) Al of the mentioned

Explanation: At first stage 1/2 L will be regular and subsequently, all the options will be regular.

3. If E=F+G;
Er=?
a) Fr+Gr
b) (F+G)r
c) Both (a) and (b)
d) None of the mentioned

Explanation: If E is a symbol a, e, or f, then Er=E. Other inductive properties include union of reversals, concatenation and Kleene.

4. With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n is the number of states of DFA, we can _________ the size of the regular expression constructed.
a) double
b) triple
d) none of the mentioned

Explanation: We can quadruple the size of the regular expression per round. Thus, we can simply write n3 expressions can take time O(n34n), where n =number of states of the DFA.

5. Which of the following are not meant to specify a regular language?
a) Regular Expression
b) DFA
c) NDFA and epsilon-NFA
d) All of the mentioned

Explanation: It is possible to convert from one specification to another. We can express a regular language in all the given four variants.

6. Which of the expression is appropriate?
For production p: a->b where a?V and b?_______
a) V
b) S
c) (V+?)*
d) V+ ?

Explanation: According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.

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

Explanation: 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. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned

Explanation: The advantage of using high level programming language like C and Pascal is that they allow us to write statements that look more like English.

9. __________ is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned

Explanation: In order to graphically represent a derivation of a grammar we need to use parse trees.

10. Grammar is checked by which component of compiler
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned

Answer: Parser or syntax analyzer is the one responsible for checking the grammar and reporting errors. In this phase, parse tree is generated and syntax is analyzed.

11. To derive a string using the production rules of a given grammar, we use:
a) Scanning
b) Parsing
c) Derivation
d) All of the mentioned

Explanation: Parsing is required to check the acceptability of a string. Further, comes the syntactical phase which is taken care by other phases of compiler.

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. 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.

15. The original YACC as written in __________ language
a) R programming language
b) C programming language
c) B programming language
d) None of the mentioned