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

### View Answer

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 .

a) Ardens theorem

b) Pumping Lemma

c) Ogden’s Lemma

d) None of the mentioned

### View Answer

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.

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

### View Answer

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

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

### View Answer

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.

a) 3

b) 7

c) 5

d) 6

### View Answer

Explanation: The grammar which produces a palindrome set can be written as:

S-> aSa | bSb | e | a | b

L={e, a, b, aba, abbbaabbba…..}

a) abstract parse trees

b) sentence diagrams

c) both abstract parse trees and sentence diagrams

d) none of the mentioned

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

b) Linked List

c) Hash Table

d) Stack

### View Answer

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

### View Answer

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.

a) Null production

b) Unit production

c) Greibach Normal Form

d) Chomsky Normal Form

### View Answer

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

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

### View Answer

Explanation:

All the assertions mentioned are theorems or corollary.

a) symmetric and reflexive

b) transitive and reflexive

c) symmetric and transitive

d) none of the mentioned

### View Answer

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

: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

### View Answer

Explanation: All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.