Consider the following statements **A. ** Only II

**B. ** Only III

**C. ** Only I and II

**D. ** Only I and III

**Answer : ****Option D**

**Explaination / Solution: **

Turing decidable ⟶ Recursive language

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?

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

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

**Answer : ****Option A**

**Explaination / Solution: **

Lexical Analysis is implemented by finite automata

Lexical Analysis is implemented by finite automata

Workspace

Report

An algorithm to find the length of the longest monotonically increasing sequence
of numbers in an array A[0 : n - 1] is given below.

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

**Answer : ****Option A**

**Explaination / Solution: **

No Explaination.

Let L_{i} denote the length of the longest monotonically increasing sequence starting
at index i in the array

Initialize L_{n}-1 =1

For all i such that 0 ≤ i ≤ n − 2

Finally the length of the longest monotonically increasing sequence is max (L0, L1,....,Ln-1). Which of the following statements is TRUE?

No Explaination.

Workspace

Report

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 {p^{n} q^{n} | n ∈ N}). Then which of the following is ALWAYS regular?

**A. ** P ∩ Q

**B. ** P − Q

**C. ** ∑ * − P

**D. ** ∑ * − Q

**Answer : ****Option C**

**Explaination / Solution: **

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

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

Workspace

Report

Consider the alphabet ∑ = {0.1},
the null/empty string λ and the sets of strings
X_{0} , X_{1} , and
X_{2} generated by the corresponding non-terminals of regular grammar. X_{0}, X_{1}, and X_{2} are
related as follows:

**A. ** 10(0*+(10)*)1

**B. ** 10(0*+(10)*)*1

**C. ** 1(0+10)*1

**D. ** 10(0+10*)*1+110(0+10)*1

**Answer : ****Option C**

**Explaination / Solution: **

No Explaination.

X0 = 1X1

X1 = 0X1 + 1X2

X2 = 0X1 + {λ}

Which one of the following choices precisely represents the strings in X0?

No Explaination.

Workspace

Report

Which of the following languages is/are regular?

**A. ** L_{1 }and L_{3 }only
**B. ** L1 only
**C. ** L2 and L3only

**D. ** L3 only
**Answer : ****Option A**

**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

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

**Answer : ****Option B**

**Explaination / Solution: **

NPDA is more powerful than DPDA.

NPDA is more powerful than DPDA.

Workspace

Report

Definition of a language L with alphabet {a} is given as following

**A. ** k + 1

**B. ** n + 1

**C. ** 2^{n + 1}

**D. ** 2^{k + 1}

**Answer : ****Option B**

**Explaination / Solution: **

Let n = 3 and k=1

L = {a^{nk} | k > 0, and n is a positive integer constant}

What is the minimum number of states needed in a DFA to recognize L?

Let n = 3 and k=1

(n + 1) states

Workspace

Report

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

**A. **

**B. **

**C. **

**D. **

**Answer : ****Option A**

**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

Which of the following finite state machines is a valid minimal DFA which accepts
the same language as D?

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

Consider the languages L1, L2 and L3 as given below

**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

**Answer : ****Option C**

**Explaination / Solution: **

L1: regular language L2: context free language L3: context sensitive language

Which of the following statements is NOT TRUE?

L1: regular language L2: context free language L3: context sensitive language

Workspace

Report

**Preparation Study Material**- Digital Electronics (Study/Preparation)
- Digital Logic Circuits (Study/Preparation)
- Computer Architecture (Study/Preparation)
- Programming and Data Structures I (Study/Preparation)
- Programming and Data Structure II (Study/Preparation)
- Database Management Systems (Study/Preparation)
- Computer Networks (Study/Preparation)
- Operating Systems (Study/Preparation)
- Software Engineering (Study/Preparation)
- Theory of Computation (Study/Preparation)
- Design and Analysis of Algorithms (Study/Preparation)
- Compiler Design (Study/Preparation)

- Engineering Mathematics (Practise Test)
- Digital Logic (Practise Test)
- Computer Organization and Architecture (Practise Test)
- Programming and Data Structures (Practise Test)
- Algorithms (Practise Test)
- Theory of Computation (Practise Test)
- Compiler Design (Practise Test)
- Operating System (Practise Test)
- Databases (Practise Test)
- Computer Networks (Practise Test)