1. All the regular languages can have one or more of the following descriptions:

i) DFA ii) NFA iii) e-NFA iv) Regular Expressions

Which of the following are correct?

a) i, ii, iv

b) i, ii, iii

c) i, iv

d) i, ii, iii, iv

### View Answer

Answer: d

Explanation: The class of languages known as the regular language has atleast four different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions

Explanation: The class of languages known as the regular language has atleast four different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions

Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.

a) Las Vegas Algorithm

b) Monte Carlo Algorithm

c) Atlantic City Algorithm

d) None of the mentioned

### View Answer

Answer: a

Explanation: The other type of algorithms are probabalistic algorithms, which depending upon the random input, have a chance of producing incorrect results or fail to produce a result.

Explanation: The other type of algorithms are probabalistic algorithms, which depending upon the random input, have a chance of producing incorrect results or fail to produce a result.

a) PSPACE=NPSPACE

b) Alternating Turing Machine

c) Time complexity

d) None of the mentioned

### View Answer

Answer: a

Explanation: Some important conclusions of Savitch theorem includes:

a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.

b) NL?L2

Explanation: Some important conclusions of Savitch theorem includes:

a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.

b) NL?L2

a) Generating

b) Pumping

c) Producing

d) None of the mentioned

### View Answer

Answer: b

Explanation: The process of repeatation is called pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.

Explanation: The process of repeatation is called pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.

5. There exists a language L. We define a string w such that w?L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?

a) n

b) |y|

c) |x|

d) none of the mentioned

### View Answer

Answer: a

Explanation: It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the maximum length of the substring xy in w can be n only.

Explanation: It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the maximum length of the substring xy in w can be n only.

a) at least 2 objects

b) at most 2 objects

c) no object

d) none of the mentioned

### View Answer

Answer: c

Explanation: This is one of the alternative formulations of the pigeon hole principle. As n < m, there will exist some place which will not receive any of the object.

Explanation: This is one of the alternative formulations of the pigeon hole principle. As n < m, there will exist some place which will not receive any of the object.

a) 6

b) 4

c) 2

d) 8

### View Answer

Answer: 4

Explanation: M is defined as: (Q, S, d, q0, F)

where Q=Q1*Q2 and F=F1*F2

Explanation: M is defined as: (Q, S, d, q0, F)

where Q=Q1*Q2 and F=F1*F2

Let L={abab,baba}

h-1(L)=_______

a) the language of two one’s and any number of zeroes

b) the language of two zeroes and any number of one’s

c) the language of two zeroes and two one’s

d) none of the mentioned

### View Answer

Answer: b

Explanation: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).

Explanation: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).

9. State true or false:

Statement: Regular expression can directly be converted to DFA without intermediate steps.

a) true

b) false

### View Answer

Answer: b

Explanation: There exists subsequent steps like formation of epsilon-NFA and NFA before the formation of corresponding DFA.

Explanation: There exists subsequent steps like formation of epsilon-NFA and NFA before the formation of corresponding DFA.

Statement: If an n-state DFA accepts a string w of length n or more, then there must be a state that appears twice on the path labeled w from the start state to the final state.

a) true

b) false

### View Answer

Answer: a

Explanation: This occurs because there are atleast n+1 states along the path while traversing the string w.

Explanation: This occurs because there are atleast n+1 states along the path while traversing the string w.

11. Are ambiguous grammar context free?

a) Yes

b) No

### View Answer

Answer: a

Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.

Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.

Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.

a) true

b) false

### View Answer

Answer: a

Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

S->aSbS|bSaS|e and w denotes terminal

a) wwr

b) wSw

c) Equal number of a’s and b’s

d) None of the mentioned

### View Answer

Answer: c

Explanation: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.

Explanation: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.

a) Production P

b) Terminal T

c) Variable V

d) Starting Variable S

### View Answer

Answer: d

Explanation: The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or with e.

Explanation: The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or with e.

a) generating

b) reachable

c) both generating and reachable

d) none of the mentioned

### View Answer

Answer: c

Explanation: For a symbol X to be useful, it has to be both reachable and generating i.e.

S->* aXb -> * w where w belongs to T*.

Explanation: For a symbol X to be useful, it has to be both reachable and generating i.e.

S->* aXb -> * w where w belongs to T*.