Paper 2 CS · UNIT 08 · MOCK TEST

Mock 5 – Context-Free Grammars & PDA (Part 2)

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

All 10 topic-wise mocks in this unit

0 / 30 answered 00:00

Q1.

What is the safest order while simplifying Context Free Grammar? ∈

AElimination of -productions, Unit productions, and then Useless symbols & productions. ∈ BElimination of useless symbols productions, -productions, and then Unit productions. ∈ CElimination of Unit productions, - productions and then Useless symbols and productions. ∈ DElimination of -productions, Useless symbols and productions, and then Unit productions.

Q2.

The reduced grammar equivalent to S → AB | CA, B → BC | AB, A → a, C → aB | b is

Q3.

Consider the grammar G: S → AbB, A → aAb | λ, B → bB | λ. Which language does G generate?

A{aⁿbᵐ : n ≥ 0, m > n} B{aⁿbᵐ : n ≥ 0, m ≥ 0} C{aⁿbᵐ : n ≥ m} D{aⁿbᵐ : n ≥ m, m > 0}

Q4.

Consider the grammar S → SbS | a. The string abababa has (A) two parse trees (B) two leftmost derivations (C) two rightmost derivations. Which is correct?

AAll (A), (B) and (C) are true BOnly (B) is true COnly (C) is true DOnly (A) is true

Q5.

Any string of terminals generated by the CFG S → XY, X → 0X | 1X | 0, Y → Y0 | Y1 | 0 (S is the start symbol)

Ahas at least one 1 Bshould end with 0 Chas no consecutive 0's or 1's Dhas at least two 0's

Q6.

Let L1 = {0ⁿ1ⁿ0ᵐ | n ≥ 1, m ≥ 1}, L2 = {0ⁿ1ᵐ0ᵐ | n ≥ 1, m ≥ 1}, L3 = {0ⁿ1ⁿ0ⁿ | n ≥ 1}. Which are correct? A. L3 = L1 ∩ L2. B. L1 and L2 are context free but L3 is not. C. L1 and L2 are not context free but L3 is. D. L1 is a subset of L3.

AA and B only BA and C only CA and D only DA only

Q7.

Given below are two statements

Statement I: The family of context free languages is closed under homomorphism

Statement II: The family of context free languages is closed under reversal In 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 true but Statement II is false DStatement I is false but Statement II is true

Q8.

Match List I (production rules) with List II (grammar). List I: A. S → XY, X → 0, Y → 1. B. S → aS | bSS | c. C. S → AB, A → 0A | 1A | 0, B → 0A. D. S → aAbc, Ab → bA, Ac → Bbcc, bB → Bb, aB → aa | aaA. List II: I. Greibach normal form, II. Context-sensitive grammar, III. Chomsky normal form, IV. S-grammar.

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

Q9.

Let L = L₁ ∩ L₂, where L₁ = {0ᵐ1ᵐ2 0ⁿ1ⁿ | m, n ≥ 0} and L₂ = {0ᵐ1ⁿ2ᵏ | m, n, k ≥ 0}. Then L is

ARecursively enumerable but not context free BRegular CContext free but not regular DNot recursive L L ∑ = {a, b}

Q10.

Which of the following statements is true?

AThe union of two context free languages is context free. BThe intersection of two context free languages is context free. CThe complement of a context free language is context free. DIf a language is context free, it can always be accepted by a deterministic pushdown automaton.

Q11.

Let G1 and G2 be arbitrary context-free grammars and R an arbitrary regular language. Which problems are undecidable? (A) Is L(G1) = L(G2)? (B) Is L(G2) ⊆ L(G1)? (C) Is L(G1) = R?

A(A) only B(B) only C(A) and (B) only D(A), (B) and (C)

Q12.

A(A) and (C) only B(B) only C(B) and (C) only D(A) and (B) only

Q13.

Consider the following grammars : G : S → aSb|bSa|aa 1 G : S → aSb|bSa|SS ∣ λ 2 G : S → aSb|bSa|SS ∣ a 3 G : S → aSb|bSa|SS|SSS|λ 4 Which of the following is correct w.r.t. the above grammars? G G

A1 and 3 are equivalent G G B2 and 3 are equivalent G G C2 and 4 are equivalent G G D3 and 4 are equivalent L = {anbn−3 ∣ n > 2}

Q14.

Which grammar generates L = {aⁿbⁿ⁻³ | n > 2} over Σ = {a, b}?

Q15.

Consider the following grammar :

S → 0A ∣ 0BB

A → 00A ∣ λ

B → 1B ∣ 11C

C → B Which language does this grammar generate?

AL((00)*0 + (11)*1) BL(0(11)* + 1(00)*) CL((00)*0) DL(0(11)*1)

Q16.

Consider the following statements with respect L = {anbn ∣ n ≥ 0} to the language

S : L2 1 is context free language

S : Lk 2 is conext-free language for any given k ≥ 1 ¯¯¯

S : L L∗ 3 and are context free languages Which one of the following is correct? S S

Aonly 1 and 2 S S Bonly 1 and 3 S S Conly 2 and 3 S , S S D1 2 and 3

Q17.

Consider the following languages : L = {anbncm} ∪ {anbmcm}, n, m ≥ 0 1 L = {wwR ∣ w ∈ {a, b}*} 2 Where R represents reversible operation. Which one of the following is (are) inherently ambiguous language(s)? L

Aonly 1 L Bonly 2 L L Cboth 1 and 2 L L Dneither 1 nor 2

Q18.

Let G=(V, T, S, P) be any context-free grammar λ without any -productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by: 1 − I Where denotes the cardinality of the set.

A(K − 1)|P| + |T| − 1 B(K − 1)|P| + |T| CK|P| + |T| − 1 DK|P| + |T|

Q19.

Match List I with List II, where L1 is regular, L2 context-free, L3 recursive and L4 recursively enumerable. List I: (a) complement(L3) ∪ L4, (b) complement(L2) ∪ L3, (c) L1* ∩ L2. List II: (i) Context-free language, (ii) Recursively enumerable language, (iii) Recursive language.

A(a)-(ii); (b)-(i); (c)-(iii) B(a)-(ii); (b)-(iii); (c)-(i) C(a)-(iii); (b)-(i); (c)-(ii) D(a)-(i); (b)-(ii); (c)-(iii)

Q20.

How can the decision algorithm be constructed L for deciding whether context-free language is finite? CFGG

(a) By constructing redundant in CNF L generating language −−

(b) By constructing non-redundant CFG G in CNF L generating language CFGG

(c) By constructing non-redundant in CNF L − {∧}(∧ generating language stands for null) Which of the following is correct?

A(a) only B(b) only C(c) only DNone of (a), (b) and (c)

Q21.

Consider the following grammar :

S → XY

X → Y aY ∣ a and Y → bbX Which of the following statements is/are true about the above grammar?

(a) Strings produced by the grammar can have a consecutive three 's.

(b) Every string produced by the grammar have a b alternate and .

(d) Every string produced by the grammar have 's in multiple of 2.

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

Q22.

Consider L₁ = {a^(n+m) bⁿ aᵐ | n, m ≥ 0} and L₂ = {a^(n+m) b^(n+m) a^(n+m) | n, m ≥ 0}. Which one is correct?

AOnly L₁ is context free BOnly L₂ is context free CBoth L₁ and L₂ are context free DBoth L₁ and L₂ are not context free

Q23.

Consider to be any regular language and L , L 1 2 be any two context-free languages. Which one of the following is correct?

AL̄₁ is context free Bcomplement of (L₁ ∪ L₂) − R is context free CL₁ ∩ L₂ is context free DL₁ − R is context free

Q24.

Consider the grammar G: S → A | B, A → a | c, B → b | c, with non-terminals {S, A, B} and terminals {a, b, c}. S₁: LR(1) can parse all strings generated by G. S₂: LL(1) can parse all strings generated by G.

AOnly 1 S BOnly 2 S S CBoth 1 and 2 S S DNeither 1 nor 2 S → (S)|SS|ε

Q25.

The grammar S → (S) | SS | ε is not suitable for predictive parsing because the grammar is

ARight recursive BLeft recursive CAmbiguous DAn operator grammar

Q26.

A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :

A0 B1 C1 or more D2 or more

Q27.

Pushdown automata can recognize language generated by_________.

AOnly context free grammar BOnly regular grammar CContext free grammar or regular grammar DOnly context sensitive grammar

Q28.

To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :

A2n − 1 B2n Cn + 1 Dn²

Q29.

Consider the two grammars: G₁: S → SbS | a G₂: S → aB | ab, A → AAB | a, B → ABb | b Which of the following options is correct?

AOnly G₁ is ambiguous BOnly G₂ is ambiguous CBoth G₁ and G₂ are ambiguous DBoth G₁ and G₂ are not ambiguous

Q30.

The set A= { 0n1n2n | n= 1, 2, 3,..............} is an example of a grammar that is :

AContext-sensitive BContext-free CRegular DNone of the above

Next: Mock 6 – Turing Machines, Decidability & Chomsky Hierarchy →