# Theory of Computation (Test 3)

## 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
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
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
Which of the following languages is generated by the given grammar? S → aS|bS|ε
A. {an bm | 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}∗
Explaination / Solution:

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

Workspace
Report
Q.3
Which of the following decision problems are undecidable?
I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ?
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) = Φ?
A. I and IV only
B. II and III only
C. III and IV only
D. II and IV only
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.

Workspace
Report
Q.4
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
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.

Workspace
Report
Q.5
Consider the following context-free grammars:
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?
A.  {am 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}
Explaination / Solution:

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

Workspace
Report
Q.6
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. Which one of the following is TRUE?

A. L = {an 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
Explaination / Solution:
No Explaination.

Workspace
Report
Q.7
Which of the following problems are decidable?
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?
A. 1,2,3,4
B. 1,2
C. 2,3,4
D. 3,4
Explaination / Solution:

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

Workspace
Report
Q.8
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
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

Workspace
Report
Q.9
Consider the following grammar. A. {R}
B. {w}
C. {w, y}
D. {w, \$}
Explaination / Solution:

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
Q.10
Consider the following context-free grammar over the alphabet ∑ = {a,b,c} with S as the start symbol.
S → abScT|abcT
T → bT|b
Which one of the following represents the language generated by the above grammar ?
A. B. C. D. Explaination / Solution:

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