MCQ Computer Science

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-35

1. A regular language over an alphabet a is one that can be obtained from
a) union
b) concatenation
c) kleene
d) All of the mentioned

### View Answer

Answer : d
Explanation : None.

2. Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned

### View Answer

Answer : a
Explanation : Regular grammar is subset of context free grammar.

3. Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned

### View Answer

Answer : a
Explanation : Regular grammar is subset of context free grammar.

4. Are the given two patterns equivalent?
(1) gray|grey
(2) gr(a|e)y
a) yes
b) no

### View Answer

Answer: a
Explanation: Paranthesis can be used to define the scope and precedence of operators. Thus, both the expression represents the same pattern.

5.Which among the following statement is correct?
Statement 1: When the analyzer scans ‘int’ and ‘intvalue’, it is not able to decide whether the int leads to a keyword or an identifier.
Statement 2: Longest Match Rule
a) Statement 1 is assertion, Statement 2 is the reason
b) Statement 1 is assertion, Statement 2 is the solution
c) There is no such Statement 2
d) This is not a function of Lexical Analyzer

### View Answer

Answer: b
Explanation: The Longest Match rule states that the lexeme scanned should be determined on the basis of longest match among all the token available.

6. Statement: If we take the union of two identical expression, we can replace them by one copy of the expression.
Which of the following is a correct option for the given statement?
a) Absorption Law
b) Idempotent Law
c) Closure Law
d) Commutative Law

### View Answer

Answer: b
Explanation: Idempotent Law states that if we take the union of two like expression, we can use a copy of the expression instead i.e. L+L=L. The common arithmetic operators are not idempotent.

7. Which of the following fields may have pigeonhole principle violated?
a) Discrete mathematics
b) Computer Science
c) Quantum Mechanics
d) None of the mentioned

### View Answer

Answer: c
Explanation: Y Aharonov proved mathematically the violation of pigeon hole principle in Quantum mechanics and proposed inferometric experiments to test it.

8. If L is a regular language, then (L’)’ U L will be :
a) L
b) L’
c) f
d) none of the mentioned

### View Answer

Answer: a
Explanation: (L’)’ is equivalent to L and L U L is subsequently equivalent to L.

9. Which of the following cannot be converted in an ordinary NFA?
a) DFA
b) Regular Expression
c) e-NFA
d) None of the mentioned

### View Answer

Answer: d
Explanation: Each of the following can expressed in terms of ordinary NFA with different time complexities.

10. Suppose there is a string w=abbab, and there exists a DFA which accepts w. How many stepts will be required to test its membership?
a) 2
b) 1
c) 4
d) None of the mentioned

### View Answer

Answer: If a string belongs to a language, the number of steps required to test that member ship is equal to the length of string i.e. 5.

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

### View Answer

Answer: d
Explanation: Parse trees are an alternative representation to derivations and recursive inferences. There can be several parse trees for the same string.

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

### View Answer

Answer: a
Explanation: 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.

13. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a
a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned

### View Answer

Answer: b
Explanation: The following format of grammar is of Regular grammar and is a part of Context free grammar i.e. like a specific form whose finite automata can be generated.

14. Which among the following is a CFG for the given Language:
L={x?{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned

### View Answer

Answer: c
Explanation: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.

15. A grammar with more than one parse tree is called:
a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned

### View Answer

Answer: b
Explanation: A context free grammar G is ambiguous if there is at least one string in L(G) having two or more distinct derivation trees or equivalently, two or more distinct leftmost derivations.

Check Also
Close