Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate
P (x) = ¬ (x = 1) ∧ ∀y (∃z (x = y * z) ⇒ (y = x) ∨ (y = 1))

**A. ** P(x) being true means that x is a prime number

**B. ** P(x) being true means that x is a number other than 1

**C. ** P(x) is always true irrespective of the value of x

**D. ** P(x) being true means that x has exactly two factors other than 1 and x

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

**Explaination / Solution: **

No Explaination.

No Explaination.

Workspace

Report

Which of the following languages is generated by the given grammar?
S → aS|bS|ε

**A. ** {a^{n} b^{m} | n,m ≥ 0}

**B. ** {w ∈ {a,b}* | w has equal number of a 's and b's}

**C. ** {an | n ≥ 0} ∪ {bn | n ≥ 0} ∪ {an bn | n ≥ 0}

**D. ** {a, b}∗

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

**Explaination / Solution: **

Given grammar generates all strings of a’s and b’s including null string ∴ L = (a + b) *

Given grammar generates all strings of a’s and b’s including null string ∴ L = (a + b) *

Workspace

Report

Which of the following decision problems are undecidable?

**A. ** I and IV only

**B. ** II and III only

**C. ** III and IV only

**D. ** II and IV only

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

**Explaination / Solution: **

There is no known algorithm to check whether the language accepted by TM is empty. Similarly there is no algorithm to check whether language CFG’s are equivalent.

I. Given NFAs N_{1} and N_{2}, is L(N_{1}) ∩ L(N_{2}) = Φ?

II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ∗, does x ∈ L(G)?

III. Given CFGs G1 and G2, is L(G1) = L(G2)?

IV. Given a TM M, is L(M) = Φ?

There is no known algorithm to check whether the language accepted by TM is empty. Similarly there is no algorithm to check whether language CFG’s are equivalent.

Workspace

Report

Which one of the following regular expressions represents the language: the set of all binary
strings having two consecutive 0s and two consecutive 1s?

**A. ** (0 + 1)∗0011(0 + 1)∗ + (0 + 1)∗1100(0 + 1)∗

**B. ** (0 + 1)∗(00(0 + 1)∗11 + 11(0 + 1)∗00)(0 + 1)∗

**C. ** (0 + 1)∗00(0 + 1)∗ + (0 + 1)∗11(0 + 1)∗

**D. ** 00(0 + 1)∗11 + 11(0 + 1)∗00

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

**Explaination / Solution: **

(a) contains 00 & 11 consecutively which is not the required condition. (c) Doesn’t guaranty that both 00 & 11 will be present in the string. (d) Says string should start with 11 & ends with 00 or vice versa.

(a) contains 00 & 11 consecutively which is not the required condition. (c) Doesn’t guaranty that both 00 & 11 will be present in the string. (d) Says string should start with 11 & ends with 00 or vice versa.

Workspace

Report

Consider the following context-free grammars:

**A. ** {a^{m} bn |m > 0 or n > 0} and {am bn |m > 0 and n > 0}

**B. ** {am bn|m > 0 and n > 0} and {am bn|m > 0 or n ≤ 0}

**C. ** {am bn|m ≥ 0 or n > 0} and {am bn|m > 0 and n > 0}

**D. ** {am bn|m ≥ 0 or n > 0} and {am bn|m > 0 or n > 0}

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

**Explaination / Solution: **

Lagrange’s generated by G1 = a*b+

G1: S → aS|B, B → b|bB

G2: S → aA|bB, A → aA|B|ε , B → bB|ε

Which one of the following pairs of languages is generated by G1 and G2, respectively?

Lagrange’s generated by G1 = a*b+

Lagrange’s generated by G2 = a+b*\b+

Workspace

Report

Consider the transition diagram of a PDA given below with input alphabet Σ = {a, b} and
stack alphabet Γ = {X , Z}. Z is the initial stack symbol. Let L denote the language accepted
by the PDA.**A. ** L = {a^{n} bn|n ≥ 0} and is not accepted by any finite automata

**B. ** L = {an |n ≥ 0} ∪ {an bn|n ≥ 0} and is not accepted by any deterministic PDA

**C. ** L is not accepted by any Turing machine that halts on every input

**D. ** L = {an |n ≥ 0} ∪ {an bn|n ≥ 0} and is deterministic context-free

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

**Explaination / Solution: **

No Explaination.

Which one of the following is TRUE?

No Explaination.

Workspace

Report

Which of the following problems are decidable? **A. ** 1,2,3,4

**B. ** 1,2

**C. ** 2,3,4

**D. ** 3,4

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

**Explaination / Solution: **

CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

1) Does a given program ever produce an output?

2) If L is context-free language, then, is also context-free?

3) If L is regular language, then, is also regular?

4) If L is recursive language, then, is also recursive?

CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

Workspace

Report

Given the language L-{ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

**A. ** 1,2 and 3

**B. ** 2,3 and 4

**C. ** 1,2 and 4

**D. ** 1,3 and 4

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

**Explaination / Solution: **

L ={ab, aa, baa} Let S1 = ab , S2 = aa and S3 =baa abaabaaabaa can be written as S1S2S3S1S2 aaaabaaaa can be written as S1S1S3S1 baaaaabaa can be written as S3S2S1S2

L ={ab, aa, baa} Let S1 = ab , S2 = aa and S3 =baa abaabaaabaa can be written as S1S2S3S1S2 aaaabaaaa can be written as S1S1S3S1 baaaaabaa can be written as S3S2S1S2

Workspace

Report

Consider the following grammar.

**A. ** {R}

**B. ** {w}

**C. ** {w, y}

**D. ** {w, $}

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

**Explaination / Solution: **

FOLLOW(Q) is FIRST(R) hence

What is FOLLOW (Q) ?

FOLLOW(Q) is FIRST(R) hence

FIRST(R) = {w, ϵ}

We add ‘w’ in FOLLOW(Q) and for ϵ we calculate FIRST(S)

FIRST(S) ={y}

FOLLOW(Q) is {w ,y}

Workspace

Report

Consider the following context-free grammar over the alphabet ∑ = {a,b,c} with S as the start
symbol.

**A. **
**B. **

**C. **

**D. **

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

**Explaination / Solution: **

The given Grammar over Σ = {a, b, c} with S as the start symbol is

S → abScT|abcT

T → bT|b

Which one of the following represents the language generated by the above grammar ?

The given Grammar over Σ = {a, b, c} with S as the start symbol is

S → abScT | abcT

T→ bT | b

The minimum length string generated by the grammar is 1:

S→abcT→abcb ; hence all variable greater than 1.

Other cases

S → abScT→ ab abScT cT → ab ab abScT cT cT →........→ (ab)^{n} (cT)^{n}

Here T can generate any number of b’s starting with single b.

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)