Paper 2 CS · UNIT 08 · MOCK TEST

Mock 4 – Context-Free Grammars & PDA (Part 1)

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. Match the LIST-I with LIST-II.

LIST-I (Language)	LIST-II (Type of Language)
A. L₁ = {aⁿbᵐ \| n, m ≥ 0}	I. Unrestricted
B. L₂ = {aⁿbᵐ \| (n − m) ≥ 0}	II. Context Sensitive
C. L₃ = {aⁿbⁿcⁿdⁿ \| n ≥ 1}	III. Regular
D. L₄ = {aⁿbᵐcᵐdⁿ \| n, m ≥ 0}	IV. Context Free

Choose the correct answer from the options given below:

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

Q2. Which of the following statements is incorrect?

AGiven a context free grammar G and a string x, an algorithm can be designed to decide whether x∈L(G) in polynomial time. BGiven a context free language L, its complement is also context free. CThe language {aⁿ bᵐ cᵖ : m, n, p ≥ 0, m≠n or m≠p} is not deterministic context free. DClass of deterministic context free languages is closed under intersection.

Consider the following Context Free Grammar (G):

S → A B
B → + A B | ε
A → C D
D → * C D | ε
C → [ S ] | x

Variable = { S, A, B, C, D }

Terminals = { +, *, [, ], x }

Q3. Identify the correct statement from the following.

AThe given CFG(G) is Left recursive BThe given CFG(G) needs Left factorization C[[x * x] + x] is a valid sentence of this grammar DThe given CFG(G) has an SLR(o) Parser as well

Consider the following Context Free Grammar (G):

S → A B
B → + A B | ε
A → C D
D → * C D | ε
C → [ S ] | x

Variable = { S, A, B, C, D }

Terminals = { +, *, [, ], x }

Q4. The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?

A3 B4 C5 D6

Q5. Which of the following Grammars is/are only Context Free (i.e. context-free but not regular grammars)?

Grammar	Productions
A	S → Ab aS → aA A → a
B	S → Ab A → Sa A → a
C	S → AS S → aA A → a
D	S → Ab S → aA A → a
E	S → Sb A → Aa A → ε

AA, B Only BC, D Only CC, E Only DA, B, D, E Only

AA & B only BB only CC only DB & D only

Q7. Consider the grammar:
S → A
A → $B$ | id
B → B, A | A
If I₀ = CLOSURE({[S → ·A]}), then how many items will be in the set GOTO(I₀, $)?

A3 B4 C5 D6

Q8. Consider the grammar:
T → Qx
Q → RS
R → y | ε
S → z | ε
Here x, y, z are terminals and T, Q, R, S are non-terminals. What will be the FOLLOW set of the non-terminal R?

A{x, y} B{y, z} C{z, x} D{ε}

Q9. Which of the following properties correctly describe a Regular Grammar?
(A) All production rules are of the form A → xB or A → x, where A and B are non-terminal symbols and x is a terminal symbol.
(B) Regular grammars are more powerful than context-free grammars and can express any type of language.
(C) There is a direct correspondence between regular grammars and finite automata.
(D) Regular grammars can generate languages that are not recognised by any type of automata.
Choose the correct answer from the options given below:

A(A) and (B) Only B(B) and (C) Only C(C) and (D) Only D(A) and (C) Only

Q10. Which of the following are context-free languages?
(A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, where i, j, k, l ≥ 0}
(B) {wⁱ xʲ yᵏ zˡ | i = j, k = l, where i, j, k, l ≥ 0}
(C) {wⁱ xʲ yᵏ zˡ | i = j = k and k ≠ l, where i, j, k, l ≥ 0}
(D) {wⁱ xʲ yᵏ zˡ | i = j = k + l, where i, j, k, l ≥ 0}
(E) {wⁱ xʲ yᵏ zˡ | i = j = l and k ≠ l, where i, j, k, l ≥ 0}

A(A) and (B) Only B(B) and (C) Only C(C) and (D) Only D(D) and (E) Only

Q11. The maximum yield length of the following CNF CFG is
S → AB
A → CD
B → e
C → a
D → b

A8 B7 C4 D5

Q12. Consider the language L = {w ∈ {a, b, c}* : nₐ(w) + n_b(w) = n_c(w)}. L is

AContext free but not linear BNot context free CContext free and linear DLinear

Q13. Consider the following statements:
A. A context-free language is generated by an LR(0) grammar if and only if it is accepted by a deterministic pushdown automaton and has the prefix property.
B. If M1 is a single-tape TM simulating a multitape TM M, then the time taken by M1 to simulate n moves is O(n³).
C. A pushdown automaton behaves like a Turing machine when it has one auxiliary memory.
D. L = {aⁿbⁿcⁿ : n ≥ 1} is not context-free but is context-sensitive.
Choose the correct answer from the options given below:

AA, B and C only BA, B only CD only DB, C only

Q14. An ambiguous grammar is one which has:
A. More than one derivation
B. More than one leftmost derivation
C. More than one rightmost derivation
D. More than one parse tree
E. More than one syntax tree
Choose the correct answer from the options given below:

AA and D Only BB and C Only CD and E Only DA and E Only

Q15. The grammar
stmt → if expr then stmt else stmt | if expr then stmt
suffers from:

AAmbiguity BLeft factoring CLeft recursion Dλ-moves

Q16. Consider the following statements:
A. For every regular language, we can design a Turing machine.
B. For every context-free language, we can design a Turing machine.
Which of the following is correct?

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

Q17. Which of the following is (are) correct about the regular expression a a* b b* c c* d d*?
1. The language for the given expression is L = {aⁿbⁿc^md^m | n ≥ 1, m ≥ 1} ∪ {aⁿb^mc^mdⁿ | n ≥ 1, m ≥ 1}
2. The context-free grammar for the given expression is:
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
3. The language generated by this expression is an equal number of a's, followed by an equal number of b's, followed by an equal number of c's, followed by an equal number of d's.
Choose the correct answer from the options given below:

AOnly 1 is correct BOnly 2 is correct CBoth 1 and 2 are correct DAll the three 1, 2 and 3 are correct

Q18. What is the safest order for simplifying a context-free grammar?

AElimination of ε-productions, unit productions, and then useless symbols and productions BElimination of useless symbols and 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

Q19. The reduced grammar equivalent to the grammar whose production rules are given below is
S → AB | CA
B → BC | AB
A → a
C → aB | b

Q20. Consider the production rules of grammar G:
S → AbB
A → aAb | λ
B → bB | λ
Which language L is generated by G?

AL = {aⁿb^m : n ≥ 0, m > n} BL = {aⁿb^m : n ≥ 0, m ≥ 0} CL = {aⁿb^m : n ≥ m} DL = {aⁿb^m : n ≥ m, m > 0}

Q21. Consider the grammar S → SbS | a and the string abababa. Consider the statements: the string has
(A) two parse trees
(B) two leftmost derivations
(C) two rightmost derivations
Which of the following is correct?

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

Q22. Consider the following statements about context-free languages (CFL):
Statement I: CFLs are closed under homomorphism.
Statement II: CFLs are closed under complement.
Which of the following 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

Q23.

Which of the following Grammars is/are only Context Free?

AA, B Only BC, D Only CC, E Only DA, B, D, E Only

Q24.

Match List I with List II. List I: A. Type 3 Grammar, B. Type 2 Grammar, C. Type 1 Grammar, D. Type 0 Grammar. List II: I. V → (V ∪ Σ)*; II. λVβ → λ(V ∪ Σ)*β, where λ, β ∈ (V ∪ Σ)*; III. (V ∪ Σ)* → (V ∪ Σ)*; 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

Q25.

Match List I with List II. List I: A. Type-0 grammar, B. Type-1 grammar, C. Type-2 grammar, D. Type-3 grammar. List II: I. Linear grammar; II. GNF; III. x → y, |x| ≤ |y|, x, y ∈ (V ∪ T)*; 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

Q26.

Consider the Grammar:

T → Qx

Q → RS

R → y ∣ ϵ

S → z ∣ ϵ Here x, y, z are terminals and T, Q, R, S are non- terminals. What will be the follow set of the non-terminal R?

A{x,y} B{y,z} C{z,x} D{ϵ}

Q27.

Which of the following is a context-free language? (A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, i, j, k, l ≥ 0} (B) {wⁱ xʲ yᵏ zˡ | i = j, k = l} (C) {wⁱ xʲ yᵏ zˡ | i = j = k and k ≠ l} (D) {wⁱ xʲ yᵏ zˡ | i = j = k + l} (E) {wⁱ xʲ yᵏ zˡ | i = j = l and k ≠ l}

A(A) and (B) Only B(B) and (C) Only C(C) and (D) Only D(D) and (E) Only

Q28.

Which of the following is -free grammar?

AType-0 BType-1 CType-2 DType-3

Q29.

The item generated by the production is :

AA → . BA → ε. CA → .ε DA → ε

Q30.

Which of the following is (are) correct? 1. The language for the given expression is L = {aⁿbⁿcᵐdᵐ | n ≥ 1, m ≥ 1} ∪ {aⁿbᵐcᵐdⁿ | n ≥ 1, m ≥ 1}. 2. A context-free grammar for it is S → AB | C, A → aAb | ab, B → cBd | cd, C → aCd | aDd, D → bDc | bc. 3. The language has equal numbers of a's, b's, c's and d's in that order.

AOnly 1 is correct BOnly 2 is correct CBoth 1 and 2 are correct DAll the three 1, 2 and 3 are correct

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