What is the complement of the language accepted by the NFA show below?
Assume Σ ={a} and ε is the empty string.

**A. ** ∅

**B. ** {ε}

**C. ** a *

**D. ** {a, ε}

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

**Explaination / Solution: **

Language accepted by NFA is a^{+} , so complement of this language is {є}

Language accepted by NFA is a

Workspace

Report

What is the correct translation of the following statement into mathematical logic?
“Some real numbers are rational”

**A. ** ∃x (real(x) v rational (x))

**B. ** ∀x (real(x)→rational (x))

**C. ** ∃x (real(x)∧ rational (x))

**D. ** ∃x (real(x)∧ rational (x))

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

**Explaination / Solution: **

Option A: There exists x which is either real or rational and can be both. Option B: All real numbers are rational Option C: There exists a real number which is rational. Option D: There exists some number which is not rational or which is real.

Option A: There exists x which is either real or rational and can be both. Option B: All real numbers are rational Option C: There exists a real number which is rational. Option D: There exists some number which is not rational or which is real.

Workspace

Report

If G is grammar with productions S → SaS|aSb|bSa|SS|∈ where S is the start variable, then which one of the following is not generated by G?

**A. ** abab

**B. ** aaab

**C. ** abbaa

**D. ** babba

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Consider the following languages over the alphabet ∑= {a, b,c}

**A. ** I only

**B. ** II only

**C. ** I and II

**D. ** Neither I nor II

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

**Explaination / Solution: **

Which of the following are context-free languages ?

I. L_{1 }∪ L_{2} II. L1 ∩ L2

Workspace

Report

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total
functional from A*
to B*
. We say f is computable if there exists a Turning machine M which
given an input x in A*
, always halts with f(x) on its tape. Let L_{f} denote the language
{x#f(x)|x∈A*}. Which of the following statements is true:
**A. ** f if computable if and only if L_{f} is recursive

**B. ** f is computable if and only Lf recursively enumerable.

**C. ** If f is computable then Lf is recursive, but not conversely.

**D. ** If f is computable then Lf is recursively enumerable, but not conversely.

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

**Explaination / Solution: **

A TM is recursive iff it halts for every input string (either in accept or reject state). Here, a computable function is defined in a similar way.

A TM is recursive iff it halts for every input string (either in accept or reject state). Here, a computable function is defined in a similar way.

Workspace

Report

Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are nonterminals

**A. ** Finite.

**B. ** Not finite but regular

**C. ** Context-free but not regular.

**D. ** Recursive but not context-free.

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

**Explaination / Solution: **

The Context free grammar given over alphabets Σ ={ a, b, c} with S and T as non terminals are:

G_{1} : S → aSb|T,T → cT|∈

G_{2} : S → bSa|T,T → cT|∈

The language L(G1) ∩ L(G2) is

The Context free grammar given over alphabets Σ ={ a, b, c} with S and T as non terminals are:

Workspace

Report

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively
enumerable but not recursive. Which of the following statements is not
necessarily true?

**A. ** L2 – L1 is recursively enumerable

**B. ** L1 – L3 is recursively enumerable

**C. ** L2 ∩ L1 is recursively enumerable

**D. ** L2 ∪ L1 is recursively enumerable

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

For the grammar below, a partial LL(1) parsing table is also presented along with the
grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty
string, $ indicates end of input, and | separates alternate right hand sides of productions.

**A. ** FIRST(A) = {a, b, ε } = FIRST (B)
**B. ** FIRST(A) = {a, b, $}
**C. ** FIRST(A) = {a, b, ε } = FIRST(B)
**D. ** FIRST(A) = {a, b,} = FIRST(B)
**Answer : ****Option A**

**Explaination / Solution: **

S → a AbB| bAa B| ε

A → S

B → S

The First and Follow sets for the non-terminals A and B are

FOLLOW(A) = {a, b}

FOLLOW(B) = {a, b, $}

FIRST(B) = {a, b, ε }

FOLLOW(A) = {a, b}

FOLLOW(B) ={$}

FIRST(A) = {a, b}

FOLLOW(B) = ∅

FIRST(A) = {a, b}

FOLLOW(B) ={a, b}

Workspace

Report

For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and | separates alternate right hand sides of productions.

**A. ** E1: S →aAbB, A →S

**B. ** E1: S →aAbB, S → ε

**C. ** E1: S →aAbB, S → ε

**D. ** E1: A →S, S→ ε

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

**Explaination / Solution: **

S → a AbB| bAa B| ε

A → S

B → S

The appropriate entries for E1, E2, and E3 are

E2: S →bAaB, B → S

E3: B →S

E2: S →bAaB, S → ε

E3: S → ε

E2: S →bAaB, S → ε

E3: B →S

E2: B →S, S → ε

E3: B →S

Workspace

Report

The grammar S → aSa|bS|c is

**A. ** LL(1) but not LR(1)

**B. ** LR(1) but not LR(1)

**C. ** Both LL(1) and LR(1)

**D. ** Neither LL(1) nor LR(1)

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

**Explaination / Solution: **

No Explaination.

No Explaination.

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)