Paper 2 CS · UNIT 08 · MOCK TEST

Mock 6 – Turing Machines, Decidability & Chomsky Hierarchy

Unit 8: Theory of Computation and Compilers · 29 questions · about 34 minutes. Press End Mock any time to see your score and the correct answers.

All 10 topic-wise mocks in this unit

0 / 29 answered 00:00

Q1. Arrange the following families of languages from specialization to generalization, defined over alphabet Σ:
A. Family of all regular languages
B. Family of all Turing acceptable languages
C. Family of all Turing decidable languages
D. Family of all context free languages
Choose the correct answer from the options given below:

AA, B, C, D BA, C, B, D CA, D, C, B DA, D, B, C

Q2. Match List I with List II

List I	List II
A. Type 3 Grammar	I. V → (V ∪ Σ)*
B. Type 2 Grammar	II. αVβ → α(V ∪ Σ)⁺β, where α, β ∈ (V ∪ Σ)*
C. Type 1 Grammar	III. (V ∪ Σ)* → (V ∪ Σ)*
D. Type 0 Grammar	IV. V → VΣ \| Σ

AA → II, B → III, C → IV, D → I BA → III, B → I, C → IV, D → II CA → IV, B → I, C → II, D → III DA → III, B → II, C → I, D → IV

Q3. Match List I with List II

List I	List II
A. Type-0 Grammar	I. Linear Grammar
B. Type-1 Grammar	II. GNF
C. Type-2 Grammar	III. x → y, \|x\| ≤ \|y\|; x, y ∈ (V ∪ T)*
D. Type-3 Grammar	IV. Recursively Enumerable

AA-I, B-II, C-III, D-IV BA-II, B-I, C-III, D-IV CA-III, B-II, C-IV, D-I DA-IV, B-III, C-I, D-II

Q4. If L₁ and L₂ are context-free languages, which one of the following is true about L₁ ∩ L₂?

AL₁ ∩ L₂ is context free BL₁ ∩ L₂ is regular CL₁ ∩ L₂ is recursively enumerable DL₁ ∩ L₂ is context sensitive

Q5. Arrange the following language classes in ascending order of their expressive power, as defined by the Chomsky hierarchy:
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted grammars (recursively enumerable)
Choose the correct answer from the options given below:

A(C), (A), (B), (D) B(C), (A), (D), (B) C(A), (C), (B), (D) D(A), (D), (B), (C)

Q6. Consider the following statements:
A. The set of Turing machine codes for TMs that accept all inputs that are palindromes (possibly along with other inputs) is decidable.
B. The language of codes for TMs M that, when started with blank tape, eventually write a 1 somewhere on the tape is undecidable.
C. The language accepted by a TM M, L(M), is always recursive.
D. Post's correspondence problem is undecidable.
Choose the correct answer from the options given below:

AA, B and C only BB, C and D only CA and C only DB and D only

Q7. The transition function δ in a multi-tape Turing machine (k tapes) is defined as:

Aδ : 2^Q × Γ^k → 2^Q × Γ^k × {L, R, S}^k Bδ : Q × Q × Γ^k → Q × Q × Γ^k × {L, R, S}^k Cδ : Q × Γ^k → Q × Γ^k × {L, R, S}^k Dδ : Q × Γ^k × 2^Q → Q × Γ^k × 2^Q × {L, R, S}^k

Q8. Consider two instances X and Y of the Post Correspondence Problem, each with lists A and B of three strings over {0, 1}. Which of the following is true?

i	List A	List B
1	1	111
2	10111	10
3	10	0

i	List A	List B
1	10	101
2	011	11
3	101	011

AOnly PCP in X has a solution BOnly PCP in Y has a solution CPCP in both X and Y has a solution DPCP in neither X nor Y has a solution

Q9. Consider the following properties of recursively enumerable sets:
(A) Finiteness
(B) Context-freedom
(C) Emptiness
Which of the following is true?

AOnly (A) and (B) are not decidable BOnly (B) and (C) are not decidable COnly (C) and (A) are not decidable DAll of (A), (B) and (C) are not decidable

Q10. Match List I with List II.
Choose the correct answer from the options given below:

List I	List II
A. Type 0	I. Finite automata
B. Type 1	II. Turing machine
C. Type 2	III. Linear bounded automata
D. Type 3	IV. Pushdown automata

AA-III, B-IV, C-II, D-I BA-II, B-III, C-IV, D-I CA-III, B-IV, C-I, D-II DA-II, B-III, C-II, D-IV

Q11.

Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy:

(A) Context-free languages

(B) Context-sensitive languages

(D) Unrestricted Grammars

A(C), (A), (B), (D) B(C), (A), (D), (B) C(A), (C), (B), (D) D(A), (D), (B), (C)

Q12.

A. The set of turning machine codes for TM's that accept all inputs that are palindromes (possible along with some other inputs) is decidable

B. The language of codes for TM's M that when started with blank tape, eventually write a 1 somewhere on the tape is undecidable

C. The language accepted by a TMM is LM is always recursive

D. Post's correspondence problem is undecidable

AA, B and C only BB, C and D only CA and C only DB and D only G = R H = {−1, 1}

Q13.

Consider the following statements:

(A) For every regular language, we can design Turing Machine

(B) For every context free language, we can design Turing Machine Which of the following is correct?

AStatement-A is false and Statement-B is true. BStatement-A and Statement-B both are false. B CStatement-A is true and Statement- is false. DStatement-A and Statement-B both are true.

Q14.

The transition function ' ' in multi-tape Turing machine is defined as:

Aδ : 2Q × Γᵏ → 2^Q × Γᵏ × {L, R, S}ᵏ Bδ : Q × Q × Γᵏ → Q × Q × Γᵏ × {L, R, S}ᵏ Cδ : Q × Γᵏ → Q × Γᵏ × {L, R, S}ᵏ Dδ : Q × Γᵏ × 2^Q → Q × Γᵏ × 2^Q × {L, R, S}ᵏ

Q15.

Consider two PCP instances over {0, 1}, each with lists A and B of three strings. X: A = (1, 10111, 10), B = (111, 10, 0). Y: A = (10, 011, 101), B = (101, 11, 011). Which is true?

AOnly PCP in X has a solution BOnly PCP in Y has a solution CPCP in both X and Y has a solution DPCP in neither X nor Y has a solution

Q16.

Match List I with List II. List I: (A) Type 0, (B) Type 1, (C) Type 2, (D) Type 3. List II: (I) Finite automata, (II) Turing machine, (III) Linear bounded automata, (IV) Pushdown automata.

A(A)-(III), (B)-(IV), (C)-(II), (D)-(I) B(A)-(II), (B)-(III), (C)-(IV), (D)-(I) C(A)-(III), (B)-(IV), (C)-(I), (D)-(II) D(A)-(II), (B)-(III), (C)-(II), (D)-(IV)

Q17.

Statement I: CFLs are closed under homomorphism. Statement II: CFLs are closed under complement. Which is correct?

AStatement I is true and Statement II is false BStatement II is true and Statement I is false CBoth Statement I and Statement II are true DNeither Statement I nor Statement II is true

Q18.

Which of the following concepts can be used to identify loops?

A. Depth first ordering

B. Dominators

C. Reducible graphs

AA and B only BA and C only CB and C only DA, B and C

Q19.

Match List I with List II (L_R regular, L_CF context-free, L_REC recursive, L_RE recursively enumerable). List I: A. Recursively enumerable language, B. Recursive language, C. Context-free language. List II: I. complement(L_REC) ∪ L_RE, II. complement(L_CF) ∪ L_REC, III. L_R* ∩ L_CF.

AA-II, B-III, C-I BA-III, B-I, C-II CA-I, B-II, C-III DA-II, B-I, C-III

Q20.

Given below are two statements: L ∧ L = ϕ

Statement I : The problem "Is 1 2 ? " is L undecidable for context sensitive languages 1 L and 2. ∈

Statement II : The problem "Is W L?" is decidable W for context sensitive language L, (where is a string). In the light of the above statements, choose the correct answer from the options given below

ABoth Statement I and Statement II are true BBoth Statement I and Statement II are false CStatement I is correct but Statement II is false DStatement I is incorrect but Statement II is true.

Q21.

Consider the following language families : L ≡ The context - free languages 1 L ≡ The context - sensitive languages 2 L 3 ≡ The recursively enumerable languages L ≡ The recursive languages 4 Which one of the following options is correct? L ⊆ L ⊆ L ⊆ L

A1 2 3 4 L ⊆ L ⊆ L ⊆ L B2 1 3 4 L ⊆ L ⊆ L ⊆ L C1 2 4 3 L ⊆ L ⊆ L ⊆ L D2 1 4 3

Q22.

Consider the following statements : S

1 : These exists no algorithm for deciding if any M M two Turing machines 1 and 2 accept the same language. S M M

2 : Let 1 and 2 be arbitrary Turing ⊆ L (M ) machines. The problem to determine 2 is undecidable. Which of the statements is (are) correct? S

AOnly 1 S BOnly 2 S S CBoth 1 and 2 S S DNeither 1 nor 2 A = {001, 0011, 11, 101}

Q23.

Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}; C = {00, 001, 1000} and D = {0, 11, 011}. Which pairs have a Post correspondence solution?

AOnly pair (C, D) BOnly pair (A, B) CBoth (A, B) and (C, D) DNeither (A, B) nor (C, D)

Q24.

Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing M machine ? G L(G) = ϕ

(a) is a CFG with M M

(b) There exist two TMs 1 and 2 such that L(M) ⊆ {L (M ) ∪ L (M )} = 1 2 language of TMs all ω 2|ω|

A(a) and (b) only B(a) only C(a), (b) and (c) D(c) only

Q25.

For a statement L ⊆ Σ∗ A language is recursive if there exists M some turing machine . Which of the following conditions is satisfied for ω any string ? ω ∈ L M ω M

AIf , then accepts and will not halt ω ∉ L M ω M BIf , then accepts and will halt by reaching at final state ω ∉ L M CIf , then halts without reaching to acceptable state ω ∈ L M DIf , then halts without reaching to an acceptable state

Q26.

Consider the following problems :

(i) Whether a finite state automaton halts on all inputs ?

(ii) Whether a given context free language is regular?

(iii) Whether a Turing machine computes the product of two numbers? Which one of the following is correct?

AOnly (i) and (iii) are undecidable problems BOnly (ii) and (iii) are undecidable problems COnly (i) and (ii) are undecidable problems D(i), (ii) and (iii) are undecidable problems

Q27.

Which of the following problems is decidable for recursive languages L?

AIs L = ϕ? BIs w ∈ L, where w is a string? CIs L = Σ*? DIs L = R, where R is a given regular set?

Q28.

Context-sensitive language can be recognized by a :

AFinite state machine BDeterministic finite automata CNon-deterministic finite automata DLinear bounded automata

Q29.

Consider the statements: S₁: There exists no algorithm for deciding whether any two Turing machines M₁ and M₂ accept the same language. S₂: The problem of determining whether a Turing machine halts on any input is undecidable. Which of the following options is correct?

ABoth S₁ and S₂ are correct BBoth S₁ and S₂ are not correct COnly S₁ is correct DOnly S₂ is correct

Next: Mock 7 – Lexical & Syntax Analysis (Parsing) →