MCQ Computer Science

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

1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11

Explanation : string of length 0 = 1
string of length 1 = 4
string of length 2 = 3
string of length 3 = 3

2. Which of the following regular expression is equivalent to R(1,0)?
R(1,0)={111*}*
a) (11+111)*
b) (111+1111)*
c) (111+11*)*
d) All of the mentioned

Explanation: What we observe from the question is that, it includes e and 11 and any number of 1’s then. Therefore, its simplifies when we write the same reg. Expression as (11+111)*.

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

Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body

4. For an automata, which of the following are equivalent variants?
DFA,NFA and NFA with epsilon transitions
a) DFA and NFA
b) NFA and epsilon NFA
c) DFA and epsilon NFA
d) All of the mentioned

Explanation: For a given automata, all the formats of representation be it deterministic finite automata or non deterministic finite automata or non deterministic finite automata with epsilon transitions, all are equivalent variants.

5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2

Explanation : Finite state machine and regular expression have same power to express a language.

6. Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes.
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.
c) A language L is NFA-regular if and only if it is DFA-regular.
d) None of the mentioned

Explanation: Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.

7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language

Explanation : According to Chomsky hierarchy .

8. What does the following segment of code does?
grep -i man heroes.txt
a) manually opens a file called heroes.txt
b) manages heroes.txt
c) search for “man” in the file “heroes.txt”
d) none of the mentioned

Explanation: grep is a command which finds the pattern in a particular text segment.Here, it scans each line in heroes.txt and looks for an m followed by a and then followed by n.

9. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned

abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.

10. For the given Regular expression, the minimum number of terminals 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|e
A->011|1
C->DC|e
D->01

11. Choose the correct option:
Statement: Unambiguity is the ideal structure of a language.
a) true
b) partially true
c) false
d) cant be said

Explanation: Ideally, there should be only one parse tree for each string, i.e. the language should be unambiguous.

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

13. YACC is a computer program for ______ operation system.
a) Windows
b) DOS
c) Unix
d) openSUSE

Explanation: YACC technique is a computer code for the Unix operating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code.

14. XML uses _________ principle to formally describe the data.
a) DDL
b) DTD
c) DML
d) None of the mentioned

Explanation: A document type definition (DTD) is a set of markup declarations that define a document type for an SGML-family markup language (SGML, XML, HTML). A Document Type Definition (DTD) defines the legal building blocks of an XML document. It defines the document structure with a list of legal elements and attributes.

15. A CFG is ambiguous if
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned