Theory of Computation Test 1

Question 1
2 / -0.33

Recursive language is not closed under

A
complementation

B
substitution

C
set difference

D
intersection

Question 2
2 / -0.33

Which of the following definitions generates the same languages as L, where L = { xⁿyⁿ, n ≥ 1 }
i. E → xEy | xy
ii. xy | x⁺xyy⁺
iii. x⁺y⁺

A
i) only

B
i) and ii) only

C
ii) and iii) only

D
ii) only

Question 3
2 / -0.33

Let L be a language and L' be its complement. Which one of the following is true?

A
If L is recursively enumerable language then L’ is also recursively enumerable language

B
If L’ is not a recursively enumerable language then L is a recursively enumerable language

C
If L is recursively enumerable language than L’ is recursive

D
If L is recursive language then L’ is recursively enumerable

Question 4
2 / -0.33

Let the number of states in non-deterministic finite automaton be 'N^K' and the number of states in the corresponding deterministic finite automaton be 'D'. N, K, and D are positive integers. What is the correct relation between N^K and D?

A
1 < N^k ≤ D

B
1 ≤ D ≤ NK

C
1 ≤ D < N^K

D
1 ≤ N^k ≤ D

Question 5
2 / -0.33

The grammar G = ({S, X, Y}, {p, q}, S, P) with productions
S → X, X → qY | ϵ, Y → Xp is a _____.

A
G is Regular grammar

B
G is right linear grammar

C
G is left linear grammar

D
G is linear grammar

Question 6
2 / -0.33

The Halting problem of Turing machines is

A
recursive

B
recursively enumerable but not recursive

C
recursive but not recursively enumerable

D
not recursively enumerable

Question 7
2 / -0.33

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 necessarily true?
I L2 – L1 is recursively enumerable.
II L1 – L3 is recursively enumerable
III L2 ∩ L1 is recursively enumerable

A
I and II

B
II and III

C
I and III

D
I, II and III

Question 8
2 / -0.33

Which of the following languages is context free but not regular?
1) {aⁱb^jc^k | i>j>k}
2) {aibjck | j = i+k}
3) {w | w Є {a,b}*, |w| <= 100}
4) {aⁿb²ⁿ | n>=1}

A
Only 3

B
Only 2 and 4

C
Only 1 and 4

D
Only 2

Question 9
2 / -0.33

Which of the following are undecidable?
P1: The language generated by some CFG contains any words of length less than some given number n.
P2: Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements
P3: Any given CFG is ambiguous or not.
P4: For any given CFG G, to determine whether epsilon belongs to L(G

A
P2 only

B
P1 and P2 only

C
P2 and P3 only

D
P3 only

Question 10
2 / -0.33

What is the language generated by the below given grammar?
S → aabbcc/aaAbbcc
Abb → bbA
Acc → Bbbcccc
bbB → Bbb
aaB → aaaa/aaaaA
(let n be natural number in options)

A
L = aⁿbⁿcⁿ where n ≥ 1

B
L = aⁿbⁿcⁿ where n ≥ 2

C
L = a²ⁿb²ⁿ c²ⁿ where n ≥ 2

D
L = a²ⁿb²ⁿ c²ⁿwhere n ≥ 1

Question 11
2 / -0.33

Consider the following language.
L = {w ϵ {0, 1}*| number of 0’s in w is not divisible by 5 but divisible by 7}
What is the minimum number of states in a DFA that accepts L?

A
35-35

B
354-351

C
357-356

D
359-352

Question 12
2 / -0.33

Consider the following problems L(G) denoted the language generated by a grammar G. L(M) denotes the language accepted by a machine M.
Which of the following statements is/are correct?
I. For a context sensitive grammar G, L(G) = ϕ.
II. For a context free grammar G₁ and G₂, L(G₁) ⊆ L(G₂)
III. For a recursive language L(G) and a string x, whether x ϵ L(M).

A
Only I and III is decidable

B
Only II and III is decidable

C
Only I and II are undecidable

D
I, II, III are undecidable

Question 13
2 / -0.33

Consider the following languages:
L₁= pⁿq^5mr¹⁰ⁿ | n ≥ 1 and m ≥ 1
L₂ = p^2m q^a r²ⁿs^b | m = n and a = 2b where m, n, a, b ≥ 0
L₃ = p^a q^b r^cs^x | a = b = c where a, b, c, x ≥ 0
Which of the following is/are incorrect?
I. L₁ can be accepted by deterministic pushdown automaton.
II. L₂ can be accepted by the non-deterministic pushdown automaton
III. L₃ is a context-free language

A
Only II

B
Only I and III

C
Only II and III

D
I, II and III

Question 14
2 / -0.33

In the Given language L = {ab, aa, baaa}, _______ number of strings are in L*.
(1) baaaba
(2) aabaaaa
(3) baaabaaaabaa
(4) baaabaaa

A
1

B
2

C
3

D
4

Question 15
2 / -0.33

Let L₁ be recursive language and L̅₁be its complement. Also, L₂ be the rsively enumerable language which is not recursive and L̅₂ be its complement. Let A and B be two languages such that L̅₂ reduces to A and B reduces to L̅₁ and the reduction is many to one. Which of the following is/are true?
I. B is recursive language
II. B may or may not be recursive language
III. A can be recursively enumerable language
IV. A is not recursively enumerable language

A
I and III

B
II and III

C
I and IV

D
II and IV

Question 16
2 / -0.33

Which of the following is not a deterministic context free language?
I. L₁ = a^mb^m+ncⁿ
II. L₂= aa^r | a ϵ (x, y)^* where a^r is a reversal of string a
III. L₃ = a^mbⁿcⁿd^m
\({\rm{IV}}.{\rm{\;}}{{\rm{L}}_4} = {\rm{\;}}{{\rm{a}}^{\rm{n}}}{{\rm{b}}^{{n^2}}}\)

A
Only II and III

B
Only IV

C
Only III and IV

D
Only II and IV

Submit Test

Theory of Compu...

Question 1

complementation

substitution

set difference

intersection

Question 2

i) only

i) and ii) only

ii) and iii) only

ii) only

Question 3

If L is recursively enumerable language then L’ is also recursively enumerable language

If L’ is not a recursively enumerable language then L is a recursively enumerable language

If L is recursively enumerable language than L’ is recursive

If L is recursive language then L’ is recursively enumerable

Question 4

1 < Nk ≤ D

1 ≤ D ≤ NK

1 ≤ D < NK

1 ≤ Nk ≤ D

Question 5

G is Regular grammar

G is right linear grammar

G is left linear grammar

G is linear grammar

Question 6

recursive

recursively enumerable but not recursive

recursive but not recursively enumerable

not recursively enumerable

Question 7

I and II

II and III

I and III

I, II and III

Question 8

Only 3

Only 2 and 4

Only 1 and 4

Only 2

Question 9

P2 only

P1 and P2 only

P2 and P3 only

P3 only

Question 10

L = anbncn where n ≥ 1

L = anbncn where n ≥ 2

L = a2nb2n c2n where n ≥ 2

L = a2nb2n c2n where n ≥ 1

Question 11

35-35

354-351

357-356

359-352

Question 12

Only I and III is decidable

Only II and III is decidable

Only I and II are undecidable

I, II, III are undecidable

Question 13

Only II

Only I and III

Only II and III

I, II and III

Question 14

1

2

3

4

Question 15

I and III

II and III

I and IV

II and IV

Question 16

Only II and III

Only IV

Only III and IV

1 < N^k ≤ D

1 ≤ D < N^K

1 ≤ N^k ≤ D

L = aⁿbⁿcⁿ where n ≥ 1

L = aⁿbⁿcⁿ where n ≥ 2

L = a²ⁿb²ⁿ c²ⁿ where n ≥ 2

L = a²ⁿb²ⁿ c²ⁿwhere n ≥ 1