MCQ Computer Science

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

1.The given regular language corresponds to which of the given regular language
e+1+(1+0)*0+(0+1)*11
a) The language of all strings that end with 11 or 00
b) The language of all strings that end with 0 or 1
c) The language of all strings which does not end with 01
d) None of the mentioned

Explanation: According to the given regular expression, e is accepted by its language and it does not end with 00 or 11 or 0 or 1. Thus option a and b are eliminated. Further, the regular expression is valid for the third option.

2. The conversion of NFA to DFA can be done in:
a) exponential time
b) linear time
c) logarithmic time
d) all of the mentioned

Explanation: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n3) time, without changing the number of states.Next, producing to DFA can take exponential time.

3. Language classes have the following property:
a) Closure property
b) Decision property
c) Closure & Decision property
d) None of the mentioned

Explanation: A decision property of a language class is an algorithm that takes a formal description of a language(e.g., a DFA) and tells whether or not some property holds.

4. The Grammar can be defined as: G=(V, ?, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these

Explanation: G=(V, ?, p, S), here V=Finite set of variables, ?= set of terminals, p= finite productions, S= Starting Variable.

5. Is the given statement correct?
Statement: The mere existence of several derivations is not an issue, its is the existence of several parse trees that ruins a grammar.
a) Yes
b) No

Explanation: It is also true that multiple leftmost or rightmost derivations do cause ambiguity. Unfortunately, it is not possible to remove the ambiguity always.

6. State true or false:
Statement: LALR parsers uses tables rather than mutually recursive functions.
a) true
b) false

Explanation: It is exactly the opposite case where LALR parsers uses mutually recursive functions instead of tables. It is a simplified version of canonical left to right parser.

7. Which of the following are not used to express CFG?
a) BNF
b) EBNF, ABNF
c) Van Wijngaarden form
d) None of the mentioned

Explanation: W grammar or van Wijngaarden form is used to define potentially infinite context free grammars in a finite number of rules. It is an example of larger class of affix grammars. This technique was used to define the P/L Algol 68.

8. SGML stands for:
a) Standard Generalized Markup Language
b) Standardized General Markup Language
c) Standard General Markup Language
d) Standard Generalized Markdown Language

Explanation: SGML is an acronym for Standard Generalized Markup Language.

9. In context to ambiguity, the number of times the following programming statement can be interpreted as:
Statement: if R then if T then P else V
a) 2
b) 3
c) 4
d) 1

Explanation: Dangling else problem
if R then (if T then P else V) and if R then (if T then P) else V are the two ways in which the given if else statement can be parsed.

10. NPDA stands for
a) Non-Deterministic Push Down Automata
b) Null-Push Down Automata
c) Nested Push Down Automata
d) All of the mentioned

Explanation: NPDA stands for non-deterministic push down automata whereas DPDA stands for deterministic push down automata.

11. Let ?={0,1}* and the grammar G be:
S->e
S->SS
S->0S1|1S0
State which of the following is true for the given
a) Language of all and only Balanced strings
b) It contains equal number of 0’s and 1’s
c) Ambiguous Grammar
d) All of the mentioned

Explanation: A string is said to be balanced if it consist of equal number of 0’s and 1’s.

12. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned

Explanation: The empty stack in the end is our requirement relative to finite state automatons.

13. The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned

Explanation: Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar

14. A CFG for a program describing strings of letters with the word “main” somewhere in the string:
a) -> m a i n
-> | epsilon
-> A | B | … | Z | a | b … | z
b) –> m a i n
–>
–> A | B | … | Z | a | b … | z
c) –> m a i n
–> | epsilon
–> A | B | … | Z | a | b … | z
d) None of the mentioned

Explanation: None.

15. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S}
d) None of the mentioned