Paper 2 CS · UNIT 08 · MOCK TEST

Mock 1 – Finite Automata & Regular Languages (Part 1)

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

All 10 topic-wise mocks in this unit

0 / 25 answered 00:00

Q1. If L₁ is a regular language and L₂ is a context free language, which of the following statement is correct?

AAny subset of L₁∪L₂ is context free. BL₁∩L₂ is a context free language. CL₁∩L₂ is a regular language. DL₁∩L₂ is accepted by a deterministic push down automaton.

Q2. The minimum state DFA of the following would be the following: (a DFA with states q0 (start), q1, q2, q3 and q4 (accepting) is given, with transitions q0→0 q1, q0→1 q3, q1→0 q1 (self-loop), q1→1 q4, q3→0 q2, q3→1 q4, q2→1 q4, over the alphabet {0,1})

AA –(0,1)→ B, B has a self-loop on 0, B –1→ C BA –(0,1)→ B, B has a self-loop on 1, B –0→ C CA –(0,1)→ B, B has a self-loop on (0,1), B –1→ C DA –(0,1)→ B, B –1→ C (no self-loop shown)

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. Find the Follow (A) & Follow (C).

AFollow (A) = { ], $ }; Follow (C) = { +, ], $ } BFollow (A) = { +, ], $ }; Follow (C) = { *, +, ], $ } CFollow (A) = { *, $, [ }; Follow (C) = { *, [, $ } DFollow (A) = { *, ], $ }; Follow (C) = { +, ], $ }

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. What will be the FIRST(S) & FIRST(D)?

AFIRST (S) = { +, [, x }; FIRST (D) = { +, * } BFIRST (S) = { [, ], x }; FIRST (D) = { +, ε } CFIRST (S) = { [, x }; FIRST (D) = { *, ε } DFIRST (S) = { [, x, ε }; FIRST (D) = { *, ε }

Q5. Consider the following DFA over Σ = {a, b, c}. Start state q0; final states q2, q3, q4, q5. Transitions (any missing transition goes to a dead state):

State	a	b	c
→ q0	q1	–	–
q1	q2	q3	q4
* q2	q2	q3	q4
* q3	q5	–	q3
* q4	q0	–	–
* q5	q1	–	–

Which of the following NFAs is valid (equivalent) for the given DFA?

ANFA-A: states q0–q4, start q0, final {q2, q3}. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3, q2 –a→ q4; q4 –c→ q3; q3 –a→ q0 BNFA-B: same as NFA-A but final states {q2, q3, q4} CNFA-C: states q0–q3, start q0, final {q3} only. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3; q3 –a→ q0 DNFA-D: states q0–q3, start q0, final {q2, q3}. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3; q3 –a→ q0

Q6. Consider the following DFA over Σ = {a, b, c}. Start state q0, which is also the only final state. Transitions:

State	a	b	c
→* q0	q1	q0	q0
q1	q1	q2	q0
q2	q1	q0	q3
q3	q4	q3	q3
q4	q4	q5	q3
q5	q4	q3	q0

Which of the following is the best description of the language of this DFA?

AL = (a* + b* + c*)⁺ BL = (a + b + c)* (abc)⁺ (a + b + c)* CL = {set of strings all starting with 'a, b, c' but ending with 'c'} DL = {set of strings having an even count (including 0) of substring 'abc'}

Q7. Which of the following is TRUE about the Pumping Lemma for regular languages?

AIt is a property used to prove that languages are not regular BIt applies only to infinite regular languages CIt applies to all context-free languages DIt applies to all recursively enumerable languages

Q8. Which of the following represents the language accepted by the Turing machine with the transition function (δ):
δ(q0, a) = (q1, x, R)
δ(q1, a) = (q1, a, R)
δ(q1, y) = (q1, y, R)
δ(q1, b) = (q2, y, L)
δ(q2, y) = (q2, y, L)
δ(q2, a) = (q2, a, L)
δ(q2, x) = (q0, x, R)
δ(q0, y) = (q3, y, R)
δ(q3, y) = (q3, y, R)
δ(q3, □) = (qf, □, R)

AL = {aⁿbⁿ | n ≥ 0} BL = {aⁿbⁿ | n ≥ 1} CL = {aⁿbⁿ | n > 0} DL = {aⁿbⁿ | n > 1}

Directions (Q91–95): A machine is represented by states Q, input alphabet Σ, transition function δ, initial state q0 and final states F. The machine accepts all strings over Σ = {a, b} which start and end with any combination of the alphabet symbols, and in which abb occurs as a substring (i.e. the language of all strings over {a, b} containing abb).

Q9. For the above-mentioned passage, which of the following automata is correct? Each option is described by its transitions (start state 1).

AStates 1–4, final {4}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 4 BStates 1–4, final {4}: 1 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4 CStates 1–4, final {4}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4 DStates 1–3, start and final {1}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 1

Q10. For the above specified passage, which of the following represents the grammar for the language accepted by the machine?

AS → AabbB, A → aA | ε, B → bB | ε BS → abbA, A → aA | ε | bA CS → AabbA, A → aA | bA | ε DS → Aabb, A → aA | bA | ε

Q11. Which of the following represents the minimum-state DFA for the above specified passage?

AStates 1–5, final {4, 5}: 1 –a→ 1, 1 –a→ 2, 2 –a→ 2, 2 –a→ 3, 3 –b→ 2, 3 –b→ 4, 4 –a→ 4, 4 –b→ 5, 5 –a→ 4 BStates 1–4, final {4}: 1 –b→ 1, 1 –a→ 2, 2 –a→ 2, 2 –a→ 3, 3 –b→ 2, 3 –b→ 4, 4 –a,b→ 4 CStates 1–6, final {4, 5, 6}: 1 –a→ 2, 2 –a→ 2, 2 –b→ 3, 3 –a→ 2, 3 –b→ 4, 4 –b→ 4, 4 –a→ 5, 5 –b→ 6, 6 –a→ 6, 6 –a→ 5 DAll are NFA

Q12. For the above specified passage, which of the following is a DFA for the language accepted by the machine?

AStates 1–4, final {4}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4 BStates 1–4, final {4}: 1 –b→ 1, 1 –a→ 2, 2 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4 CStates 1–6, final {4, 5, 6}: 1 –b→ 1, 1 –a→ 2, 2 –a→ 2, 2 –b→ 3, 3 –a→ 2, 3 –b→ 4, 4 –b→ 4, 4 –a→ 5, 5 –a→ 5, 5 –b→ 6, 6 –a→ 5, 6 –b→ 4 DStates 1–6, final {4, 5, 6}: 1 –a→ 1, 1 –b→ 2, 2 –a→ 2, 2 –b→ 3, 3 –a→ 2, 3 –b→ 4, 4 –a→ 4, 4 –b→ 5, 5 –b→ 5, 5 –a→ 6, 6 –b→ 5

Q13. For the above specified passage, which of the following represents the regular expression?

A(a + b)* aab Baba (a + b)* Cb (a + b)* b (a + b)* a (a + b)* D(a + b)* abb (a + b)*

Q14. Arrange the following stages of a Turing Machine (TM) operation in the correct order as they occur during computation.
(A) Writing a symbol on the tape
(B) Moving the tape head left or right
(C) Reading a symbol from the tape
(D) Transitioning to a new state based on the current state and symbol read
(E) Halting and accepting or rejecting the input
Choose the correct answer from the options given below:

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

Q15. Which of the following languages can be recognized by a Non-Deterministic Finite Automaton (NFA) but cannot be recognized by a Deterministic Finite Automaton (DFA)?
(A) L₁ = {w ∈ {0,1}* | the length of w is even}
(B) L₂ = {w ∈ {0,1}* | the length of w is odd}
(C) L₃ = {w ∈ {0,1}* | all 0's come before all 1's in w}
(D) L₄ = {w ∈ {0,1}* | w contains an equal number of 0's and 1's}
(E) L₅ = {w ∈ {0,1}* | all 1's come before all 0's in w}

A(A) and (B) Only B(B) and (C) Only C(C) and (D) Only DNone of the above

Q16. Let A = {a, b} and L = A*. Let X = {aⁿbⁿ | n > 0}. The languages L ∪ X and X are respectively:

ANot regular, Regular BRegular, Regular CRegular, Not regular DNot regular, Not regular

Q17. The sum of the minimum and maximum number of final states for a DFA having P states is equal to:

AP BP − 1 CP + 1 DP + 2

Q18. Which of the statements is/are CORRECT?
(A) Moore and Mealy machines are finite state machines with output capabilities.
(B) Any given Moore machine has an equivalent Mealy machine.
(C) Any given Mealy machine has an equivalent Moore machine.
(D) A Moore machine is not a finite state machine.
Choose the correct answer from the options given below:

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

Q19. Consider a finite automaton F1 with three states C (start), S and E (final), in which there are transitions in both directions between every pair of states (C ⇄ S, S ⇄ E, C ⇄ E). Let F2 be the finite automaton obtained by reversal of F1. Which of the following is correct?

AL(F1) ≠ L(F2) BL(F1) = L(F2) CL(F1) ≤ L(F2) DL(F1) ≥ L(F2)

Q20. Which of the following statements is correct?

AAckermann's function is primitive recursive. BL = {aⁿbᵏcⁿ⁺ᵏ : n ≥ 0, k ≥ 0} is a regular language. CL = {aⁿbʲ : n = j²} is not a context-free language. DFor every context-sensitive language L not including λ, there exists some linear bounded automaton M such that L ≠ L(M).

Q21. For regular languages and context-free languages, which is NOT correct?
A. Both are closed under union
B. Both are closed under concatenation
C. Both are closed under intersection
D. Both are closed under complementation
E. Both are closed under Kleene star
Choose the most appropriate answer from the options given below:

AA and B Only BB and C Only CC and D Only DD and E Only

Q22. Arrange in appropriate order the construction of a finite automaton:
A. Minimum-state DFA
B. Regular expression
C. NFA-ε
D. Problem statement
E. DFA
Choose the correct answer from the options given below:

AB, C, E, A, D BD, B, C, E, A CC, E, B, A, D DA, D, C, B, E

Q23. The language of the following PDA would be:
δ(q0, a, z0) = (q0, aaaz0)
δ(q0, a, a) = (q0, aaaa)
δ(q0, b, a) = (q1, λ)
δ(q1, b, a) = (q1, λ)
δ(q1, ε, z0) = (qf, z0), where qf is the final state.

A{aⁿbⁿ | n > 0} B{aⁿb²ⁿ | n > 0} C{aⁿb³ⁿ | n > 0} D{aⁿb⁴ⁿ | n > 0}

Q24. For the given two machines over {a, b}, which of the following is correct?
Machine 1: states A (start), B (final); A –a→ A, A –a→ B, B –b→ B, B –b→ A.
Machine 2: states A (start), B (final), C (final); A –a→ B, B –a→ B, B –b→ C, C –b→ C, C –a→ B.

ABoth machines are DFAs BBoth are non-equivalent machines CBoth are equivalent machines DCannot be determined

Q25. In the pumping lemma for context-free languages, for a string uvwxy, what is the minimum length of vx together?

A0 B1 C2 Dn

Next: Mock 2 – Finite Automata & Regular Languages (Part 2) →