Paper 2 CS · UNIT 08 · MOCK TEST

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

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. Which of the following is an ε-free grammar?

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

Q2. What are the minimum and maximum numbers of initial, dead, unreachable and final states in a valid n-state finite automaton whose accepted language is not φ?

AMinimum: 1, 1, 1, 1; Maximum: 1, (n−1), (n−1), n BMinimum: 1, 0, 0, 0; Maximum: 1, (n−1), (n−1), n CMinimum: 1, 0, 0, n; Maximum: 1, n, (n−1), (n−1) DMinimum: 1, 0, 0, 1; Maximum: 1, (n−1), (n−1), n

Q3. Which of the following finite automata recognise the language L = {a, b}*?
A. M = ({q0}, {a, b}, δ, q0, {q0}) with δ(q0, a) = {q0}, δ(q0, b) = {q0}
B. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = δ(q0, b) = {q0, q1}, δ(q1, a) = δ(q1, b) = {q1}
C. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = {q0, q1}, δ(q0, b) = {q0}, δ(q1, a) = –, δ(q1, b) = {q1}
D. M = ({q0, q1, q2}, {a, b}, δ, q0, {q0}) with δ(q0, a) = δ(q0, b) = {q0}, δ(q1, a) = {q2}, δ(q1, b) = –, δ(q2, a) = {q0}, δ(q2, b) = {q2}

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

Q4. In the pumping lemma for regular languages, writing the string as xyz, what is the minimum length of y?

An B2 C1 D0

Q5. The item generated by the production A → ε is:

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

Q6. In the ε-NFA M = ({q0, q1, q2, q3}, {a}, δ, q0, {q3}), where δ is given in the transition table below, what is the minimum length of string to reach the final state?

State	ε	a
q0	{q1}	{ }
q1	{q2}	{ }
q2	{ }	{q2, q3}
q3	{ }	{ }

A0 B1 C2 D3

Q7. Which of the following are correct for regular expressions?
a. φ + L = L + φ = L
b. εL = Lε = L
c. φL = Lφ = φ
d. φL = Lφ = L
Choose the correct answer from the options given below:

Aa, b and d only Ba, b and c only Cb and d only Da and d only

Q8. Match the following based on the lengths of strings in the language accepted (using the brute-force method of parsing).
Choose the correct answer from the options given below:

List I	List II
a. S → aSa \| aa	I. ((2n × 3) − 4); n ≥ 1
b. S → aaSaa \| aa	II. 2n; n ≥ 1
c. S → aaaSaaa \| aa	III. ((4 × 2n) − 6); n ≥ 1
d. S → aaaaSaaaa \| aa	IV. 2n − 2; n ≥ 2

Aa-IV, b-III, c-I, d-II Ba-II, b-IV, c-I, d-III Ca-I, b-IV, c-III, d-II Da-II, b-III, c-I, d-IV

Directions (Q96–100): A Turing machine for the language L = {aⁿb^mcⁿd^m | n ≥ 1, m ≥ 1} is designed. The model is M = ({q0, q1, q2, q3, q4, q5, q6, q7, qf}, {a, b, c, d}, {a, b, c, d, X1, X2, Y1, Y2, B}, δ, q0, B, {qf}), and part of δ is given in the transition table below. X1 and X2 are used to mark a's and c's, and Y1 and Y2 to mark b's and d's.

	a	b	c	d	X1	X2	Y1	Y2	B
q0	(q1, X1, R)				M2
q1	(q1, a, R)	(q1, b, R)	M1			(q1, X2, R)
q2	(q2, a, L)	(q2, b, L)			(q2, X1, R)	(q2, X2, L)
q3	M3	(q4, Y1, R)				(q6, X2, R)
q4		(q4, b, R)		(q5, Y2, L)		M5		(q4, Y2, R)
q5		(q5, b, L)				(q5, X2, L)	M4	(q5, Y2, L)
q6						(q6, X2, R)		(q7, Y2, R)
q7								(q7, Y2, R)	(qf, B, R)

Q9. What is the move in the cell numbered M2 of the table?

A(q1, X1, R) B(q1, a, R) C(q2, X1, R) DError entry

Q10. Consider the language L = {aⁿb^m : n ≥ 4, m ≤ 3}. Which regular expression represents L?

Aaaaa*(λ + b + bb + bbb) Baaaaa*(b + bb + bbb) Caaaaa*(λ + b + bb + bbb) Daaaa*(b + bb + bbb)

Q11. Consider the NPDA M = ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with
δ(q0, λ, z) = {(qf, z)}
δ(q0, a, z) = {(q1, 11z)}
δ(q1, a, 1) = {(q1, 111)}
δ(q1, b, 1) = {(q1, λ)}
δ(q1, λ, z) = {(qf, z)}
Which language L is accepted by the NPDA?

AL = {a²ⁿbⁿ : n ≥ 0} BL = {aⁿb²ⁿ : n ≥ 0} CL = {a²ⁿbⁿ : n > 0} DL = {aⁿb²ⁿ : n > 0}

Q12. Mr X designed open source software which must comply with some criteria. Choose the false statement in respect of above.
(A) No restriction on redistribution of the software as part or whole
(B) The integrity of the author's source code must be maintained.
(C) The software can be sold after distribution.

A(A) only B(B) only C(C) only DAll statements are false

Q13. Which of the following statements is incorrect for Parallel Virtual Machine (PVM)?

AThe PVM communication model provides asynchronous blocking send, asynchronous blocking receive, and non-blocking receive functions BMessage buffers are allocated dynamically CThe PVM communication model assumes that any task can send a message to any other PVM task and that there is no limit to the size or number of such messages DIn the PVM model, the message order is not preserved

Q14.

Consider the following DFA

Which of the following NFA is valid for the given DFA ?

Q15.

Consider the following DFA that generates set of Σ = {a, b, c} strings over

Now identify that which of the followings is the best description of the language for the above DFA

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

Directions (Q91–95): A machine is represented by states Q, input alphabet Σ = {a, b}, a transition function δ, initial state q0 and final states F. It accepts all strings over Σ that contain abb as a substring, with any combination of a and b before and after it.

Q16.

For the above mentioned passage which of the following is correct?

Q17.

Which of the following represented the minimum state DFA for the above specified passage?

DAll are NFA

Q18.

For the above specified passage, which of the following is DFA for the language represented/accepeted by machine?

Q19.

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)*

Q20.

For the regular languages and context-free languages which is not correct?

A. both are closed under union operation

B. both are closed under concatenation operation

C. both are closed under intersection operation

D. both are closed under complementation operation

E. both are closed under kleen star operation

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

Q21.

For the given two machines which of the following is correct?

Aboth Machines are DFAs Bboth are non-equivalent Machines Cboth are equivalent Machines Dcannot be determined

Q22.

Let A={a, b} and L=A*. Let X={anbn, n>0}. The languages L U X and X are respectively :

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

Q23.

The sum of minimum and maximum number of final states for a Deterministic Finite Automata (DFA) having ' P ' state is equal to :

AP BP-1 CP+1 DP+2

Q24.

Which of the statement 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.

(D) Moore machine is not a finite state machine.

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

Q25.

Consider the following finite automata F1 that accepts a language L

Let F2 be a finite automata which is obtained by reversal of F1. Then which of the following is correct?

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

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