# Theory of Computation (Test 2)

## Gate Exam : Cs Computer Science And Information Technology

| Home | | Gate Exam | | Cs Computer Science And Information Technology | | Theory of Computation |

Theory of Computation
| Theory of Computation |
Q.1
Consider the following statements
I. The complement of every Turing decidable language is Turing decidable
II. There exists some language which is in NP but is not turing decidable
III. If L is a language in NP, L is turing decidable
Which of the above statements is/are true?
A. Only II
B. Only III
C. Only I and II
D. Only I and III
Explaination / Solution:

Turing decidable  Recursive language
Turing recognizable  Recursive enumerable language
I) Complement of turning decidable language is decidable which is true.
III) True ( Theorem ) Which violates (II) hence key is D

Workspace
Report
Q.2
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
A. Finite state automata
B. Deterministic pushdown automata
C. Non-Deterministic pushdown automata
D. Turing machine
Explaination / Solution:

Lexical Analysis is implemented by finite automata

Workspace
Report
Q.3
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 : n - 1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Initialize Ln-1 =1
For all i such that 0 ≤ i ≤ n − 2

Finally the length of the longest monotonically increasing sequence is max (L0L1,....,Ln-1). Which of the following statements is TRUE?
A. The algorithm uses dynamic programming paradigm
B. The algorithm has a linear complexity and uses branch and bound paradigm
C. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
D. The algorithm uses divide and conquer paradigm.
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
Let P be a regular language and Q be a context free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pn qn | n ∈ N}). Then which of the following is ALWAYS regular?
A. P ∩ Q
B. P − Q
C. ∑ * − P
D. ∑ * − Q
Explaination / Solution:

Σ* − P is the complement of P so it is always regular, since regular languages are closed under complementation

Workspace
Report
Q.5
Consider the alphabet ∑ = {0.1}, the null/empty string λ and the sets of strings X0 , X1 , and X2 generated by the corresponding non-terminals of regular grammar. X0, X1, and X2 are related as follows:
X0 = 1X1
X1 = 0X1 + 1X2
X2 = 0X1 + {λ}
Which one of the following choices precisely represents the strings in X0

A. 10(0*+(10)*)1
B. 10(0*+(10)*)*1
C. 1(0+10)*1
D. 10(0+10*)*1+110(0+10)*1
Explaination / Solution:
No Explaination.

Workspace
Report
Q.6
Which of the following languages is/are regular?

A. Land Lonly
B. Lonly
C. Land L3only
D. Lonly
Explaination / Solution:

Hence m ≠ n, that mean n is greater than m, or m is greater than n. So we need memory, so we can‟t draw DfA for it.

Workspace
Report
Q.7
Which of the following pairs have DIFFERENT expressive power?
A. Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
B. Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
C. Deterministic single-tape Turing machine and Non-deterministic single tape Turing machine
D. Single-tape Turing machine and multi-tape Turing machine
Explaination / Solution:

NPDA is more powerful than DPDA.

Workspace
Report
Q.8
Definition of a language L with alphabet {a} is given as following
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
A. k + 1
B. n + 1
C. 2n + 1
D. 2k + 1
Explaination / Solution:

Let n = 3 and k=1

(n + 1) states

Workspace
Report
Q.9
A deterministic finite automation (DFA)D with alphabet ∑ = {a,b} is given below

Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?
A.
B.
C.
D.
Explaination / Solution:

Options B and C will accept the string b Option – D will accept the string “bba” Both are invalid strings. So the minimized DFA is option A

Workspace
Report
Q.10
Consider the languages L1, L2 and L3 as given below

Which of the following statements is NOT TRUE?
A. Push Down Automata (PDA) can be used to recognize L1 and L2
B. L1 is a regular language
C. All the three languages are context free
D. Turing machines can be used to recognize all the languages