MCQ Computer Science

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

1. The minimum length of a string {0,1}* not in the language corresponding to the given regular expression:
(0*+1*)(0*+1*)(0*+1*)
a) 3
b) 4
c) 5
d) 6

Explanation: 0101 or 1010 the strings with minimum length on {0,1}* which does not belong to the language of the given regular expression.Other strings like 111, 000, 1101, etc are accepted by the language .

2. Which of the technique can be used to prove that a language is non regular?
a) Ardens theorem
b) Pumping Lemma
c) Ogden’s Lemma
d) None of the mentioned

Explanation: We use the powerful technique called Pumping Lemma, for showing certain languages not to be regular. We use Ardens theorem to find out a regular expression out of a finite automaton.

3. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______
a) p*1
b) p+1
c) p-1
d) None of the mentioned

Explanation: Finite languages trivially satisfy the pumping lemma by having n equal to the maximum string length in l plus 1.

4. Which of the following is a function of Closure properties?
a) Helps construct representations
b) Helps show informally described languages not to be in class
c) Both (a) and (b)
d) None of the mentioned

Explanation: Using closure properties we can give a=solution to many problems like :
Is the regular languages L1 and L2 closed on concatenation operation?, etc.

5. The minimum number of productions required to produce a language consisting of palindrome strings over ?={a,b} is
a) 3
b) 7
c) 5
d) 6

Explanation: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}

6. Which of the following are distinct to parse trees?
a) abstract parse trees
b) sentence diagrams
c) both abstract parse trees and sentence diagrams
d) none of the mentioned

Explanation: Both of the mentioned are different from parse trees. Sentence diagrams are pictorial representations of grammatical structure of a sentence.

7. Which of the following is false for BNF?
a) BNF means Backus Naur Form
b) It is a normal form used in Data base normalization
c) It is a notation technique for context free grammar
d) None of the mentioned

Explanation: The normal form used in Data base normalization is BCNF i.e. Boyce Codd normal form and NOT Backus Naur Form.

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. Markup Languages are not used for which of the following?
a) playlists
b) content syndication
c) user interfaces
d) none of the mentioned

Explanation: Markup languages originated with text documents, but there is an increasing use of mark up language in presentation of other types of information, including playlists, vector graphics, user interfaces and web services.

10. A push down automaton employs ________ data structure.
a) Queue
c) Hash Table
d) Stack

Explanation: A push down automata uses a stack to carry out its operations. They are more capable than the finite automatons but less than the turing model.

11. A context free grammar is a ___________
a) English grammar
b) Regular grammar
c) Context sensitive grammar
d) None of the mentioned

Explanation: Context free grammar is the set which belongs to the set of context free grammar. Similarly, Regular grammar is a set which belongs to the the set of Context free grammar.

12. The production of the form A->B , where A and B are non terminals is called
a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form

Explanation: A->e is termed as Null production while A->B is termed as Unit production.

13. Which of the following assertion is false?
a) If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts L by empty stack i.e. L=L(PDA1)=L(PDA2)
b) If L is a CFL then there exists a push down automata P accepting CF; ; by empty stack i.e. L=M(P)
c) Let L is a language accepted by PDA1 then there exist a CFG X such that L(X)=M(P)
d) All of the mentioned

Explanation:
All the assertions mentioned are theorems or corollary.

14. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned

Explanation: A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)

15. Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned