Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L is the set of all bit strings
with even number of 1s. Which one of the regular expressions below represents
L?

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

**B. ** 0 * (10 * 10 *) *

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

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

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Consider the languages L1 = {0^{i}1j | i≠j}. L2 = {0i1j | i=j}. L3 = {0i1j | i=2j+1}. L4 = {0i1j | i≠2j}. Which one of the following statements is true?

**A. ** Only L2 is context free

**B. ** Only L2 and L3 are context free

**C. ** Only L1 and L2 are context free

**D. ** All are context free

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Which of the following statements is/are FALSE?

**A. ** 1 and 4 only

**B. ** 1 and 3 only

**C. ** 2 only

**D. ** 3 only

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

**Explaination / Solution: **

(1) NTM ≅ DTM

(1) For every non-deterministic Turing machine, there exists an equivalent deterministic
Turing machine.

(2) Turing recognizable languages are closed under union and complementation.

(3) Turing decidable languages are closed under intersection and complementation

(4) Turing recognizable languages are closed under union and intersection.

(1) NTM ≅ DTM

(2) RELs are closed under union & but not complementation

(3) Turing decidable languages are recursive and recursive languages are closed under
intersection and complementation

(4) RELs are closed under union & intersection but not under complementation

Workspace

Report

Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w.
What is the minimum number of states in a non-deterministic finite automaton
that accepts L?

**A. ** n-1

**B. ** n

**C. ** n+1

**D. ** 2^{n-1}

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a
grammar with no epsilon- and unit-production (i.e., of type A → ∈ and A → a) to parse a
string with n tokens?

**A. ** n/2

**B. ** n-1

**C. ** 2n-1

**D. ** 2^{n}

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

**Explaination / Solution: **

To have maximum number of reduce moves, all the productions will be of the typeA→αβ (where α and β could be terminals or non-terminals). Consider the following illustration then:

To have maximum number of reduce moves, all the productions will be of the typeA→αβ (where α and β could be terminals or non-terminals). Consider the following illustration then:

Workspace

Report

Consider the languages L_{1 }= Φ and L_{2 }= {a} . Which one of the following represents L_{1} L2* UL_{1}* ?

**A. ** {∈}

**B. ** Φ

**C. ** a *

**D. ** {ε, a}

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Which of the following is/are undecidable?

**A. ** 3 only

**B. ** 3 and 4 only

**C. ** 1, 2 and 3 only

**D. ** 2 and 3 only

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

**Explaination / Solution: **

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable

1. G is a CFG. Is L (G) = Φ?

2. G is a CFG. IS L (G) = Σ*?

3. M is a Turning machine. Is L(M) regular?

4. A is a DFA and N is a NFA. Is L (A) = L (N) ?

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to convert NFA to DFA hence 1 and 4 are decidable

Workspace

Report

Consider the following two sets of LR(1) items of an LR(1) grammar

**A. ** 1 only

**B. ** 2 only

**C. ** 1 and 4 only

**D. ** 1, 2, 3 and 4

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

**Explaination / Solution: **

X → c.X, c / d X → c.X, $

X → .cX, c / d X → .cX, $

X → .d, c / d X → .d, $

Which of the following statements related to merging of the two sets in the corresponding
LALR parser is/are FALSE?

1. Cannot be merged since look aheads are different

2. Can be merged but will result in S–R conflict

3. Can be merged but will result in R–R conflict

4. Cannot be merged since goto on c will lead to two different sets

1. Merging of two states depends on core part (production rule with dot operator), not on
look aheads.

2. The two states are not containing Reduce item ,So after merging, the merged state can not
contain any S-R conflict

3. As there is no Reduce item in any of the state, so can’t have R-R conflict.

4. Merging of stats does not depend on further goto on any terminal.
So all statements are false.

Workspace

Report

Consider the DFA given below.

**A. ** 1 and 3 only

**B. ** 2 and 4 only

**C. ** 2 and 3 only

**D. ** 3 and 4 only

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

**Explaination / Solution: **

Which of the following are FALSE?

1. Complement of L(A) is context–free

2. L(A) = L ((11*0+0)(0+1)*0*1*)

3. For the language accepted by A, A is the minimal DFA

4. A accepts all strings over {0, 1} of length at least 2

(1) L(A) is regular, its complement is also regular and if it is regular it is also context free.

(2) L(A) = (11*0+0)(0+1)*0*1* = 1*0(0+1)* Language has all strings where each string contains ‘0’.

(3) A is not minimal, it can be constructed with 2 states

(4) Language has all strings, where each string contains ‘0’. (atleast length one)

Workspace

Report

Consider the following languages

**A. ** L_{2} is context–free

**B. ** L_{1} ∩ L_{2 }is context–free

**C. ** Complement of L_{2} is recursive

**D. ** Complement of L1 is context–free but not regular

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

**Explaination / Solution: **

Which one of the following statements is FALSE?

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)