Automata Questions with Answers Set-1

This post contains a computer network related to 20 multiple-choice questions (Automata SET-1) that help you to go through the subject and prepare you for Automata-related questions in competitive exams.

Automata MCQ Test Series Set-1

Total Number of Questions: 20
Each question carries equal marks i.e 1
No Negative Marking

Page 1 of 2

1. DFSA and NDFSA stand for ____________ and ________________ FSA respectively.

A.Deterministic, non-deterministic

B.Declarative, non-declarative

C.Directional, non-directional

D.Distinguishable, non-distinguishable

E.None of these

2. Suppose that is a regular language and is a context-free language. Which one of the following languages is NOT necessarily context-free?

A.$L_{1} \cap L_{2}$

B.$L_{1}.L_{2}$

C.$L_{1} - L_{2}$

D.$L_{1} \cup L_{2}$

3. Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

A.$((0+1)^{*}1(0+1)^{*}1)^{*}10^{*}$

B.$(0^{*}10^{*}10^{*})^{*}0^{*}1$

C.$10^{*}(0^{*}10^{*}10^{*})^{*}$

D.none

4. if L is a regular language over which one of the following languages is NOT regular?

A.$L,L^{R} = \left\{ x \ in \Sigma^{*}|\exists y \in \Sigma^{*}\text{such that xy} \subset L \right\}$

B.$\left\{ ww^{R} |w\in L \right\}$

C.Prefix (L) - $\left\{ x \in \Sigma^{*}|\exists y \in \Sigma^{*}\text{such that xy} \subset L \right\} $

D.Suffix (L) = $\left\{ y \in \Sigma^{*}|\exists x \in \Sigma^{*}\text{such that xy} \in L \right\}$

5. Which of the following is not context-free grammar components?

A.Terminal Symbols

B.Non-terminal Symbols

C.Production Line

D.List

E.None of these

6. Consider the following statements.

If $L_1 U L_2$ is regular, then both $L_1 and L_2$ must be regular.
The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?

A.1 only

B.2 only

C.Both 1 and 2

D.Neither 1 nor 2

Let $\subseteq\left \{ 0,1 \right \}^*$ be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?

A.$L-\left \{ 01 \right \}$

B.$L \cup \left \{ 01 \right \}$

C.$\left \{ 0,1\right \}^{\ast}-L$

D.$L \cdot L$

Consider the language $L={a^{n}|N\ge 0}\cup{a^{n}b^{n}|N\ge 0}$ and the following statements.

L is deterministic and context-free.
L is context-free but not deterministic context-free.
L is not LL(k) for any k.

Which of the above statements is/are TRUE?

A.1 only

B.2 only

C.1 and 3 only

D.3 only

Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1’s by a 0. Consider the following example.
Input sequence : 00100011000011100
Output sequence : 00000001000001100
A mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above-mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.
Assume the initial state of the Mealy machine is 0.
What are the Boolean expressions corresponding to t and y in terms of s and b?

A.t=s+b y=sb

B.t=b y=sb

C.t=b y=$s{b}'$

D.t=s+b y=$s{b}'$

10.

Which of the following languages are undecidable? Note that (M) indicates the encoding of the Turing machine M.

$L_{1} = \left\{\lt M \gt |L{M}=\emptyset\right\}$

$L_{2} = \left\{\lt M,w,q \gt | \text{M on input w reaches state q in exactly 100 steps}\right\} $

$L_{3} = \left\{ \lt M \gt |\text{L(M) is recursive} \right\}$

$L_{4}=\left\{ \lt M \gt |\text{L(M) Contains at least 21 members} \right\}$

A.$L_{1}, L_{3} \text{ and} L_{4} \text{ only}$

B.$L_{1} \text{ and} L_{3} \text{ only}$

C.$L_{2} \text{ and} L_{3} \text{ only}$

D.$L_{2}, L_{3} \text{ and} L_{4} \text{ only}$

Page 2 of 2

11.

Consider the following two statements about regular languages:
$S_1$: Every infinite regular language contains an undecidable language as a subset.
$S_2$: Every finite language is regular.
Which one of the following choices is correct?

A.Only $S_1$is true.

B.Only $S_2$ is true.

C.Both $S_1$ and $S_2$ are true.

D.Neither $S_1$ and $S_2$ are true.

12. Consider the following languages.

$L_{1}=\left\{ wxyx|w, x, y \in (0+1)^{+} \right\}$

$L_{2}= \left\{ xy|x, y \in (a+b)^{*},\left| x \right|= \left| y \right|, x \# y \right\} $

Which one of the following is TRUE?

A.$L_{1}$ is regular and $L_{2}$ is context-free.

B.$L_{1}$ is context-Free but not regular and $L_{2}$ is context-free.

C.Neither $L_{1}$ nor $L_{2}$ is context-free.

D.$L_{1}$ is context-free but $L_{2}$ is not context-free.

13. Consider the following sets, where n≥2:
$S_1$: Set of all n x n matrices with entries from the set{a, b, c}
$S_2$: Set of all functions the set ${0,1,2,…,n^2-1}$ to the set {0, 1, 2}
Which of the following choice(s) is/are correct?

A.There does not exist a bijection from $S_1 to S_2$.

B.There exists a surjection from $S_1 to S_2$

C.There exists a bijection from $S_1 to S_2$.

D.There does not exist an injection from $S_1 to S_2$.

14. Let $L_1$be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?

A.$L_{1}\cap {L_{2}}'$

B.${({L_{1}}'\cup{L_{2}}')}'$

C.$L_{1}\cup (L_{2}\cup {L_{2}}')$

D.$(L_{1}\cap L_{2}) \cup ({L_{1}}'\cap L_{2})$

15. For a string w, we define $w^{R}$ to be the reverse of w. For example, if w=01101 then $w^{R}$=10110.

Which of the following languages is/are context-free?

A.$\left \{ wxw^{R}x^{R}|w,x,\epsilon \left \{0,1 \right \}\ast \right \}$

B.$\left \{ ww^{R}xx^{R}|w,x,\epsilon \left \{0,1 \right \}\ast \right \}$

C.$\left \{ wxw^{R}|w,x,\epsilon \left \{0,1 \right \}\ast \right \}$

D.$\left \{ wxw^{R}w^{R}|w,x,\epsilon \left \{0,1 \right \}\ast \right \}$

16. Let (M) denote an encoding of an automaton M. Suppose that $\sum = \left \{ 0,1 \right \}$ Which of the following languages is/are NOT recursive?

A.$L={(M)|M is a DFA such that L(M)= \oint}$

B.$L={(M)|M is a DFA such that L(M)=\sum ^{0}}$

C.$L={(M)|M is a PDA such that L(M)=\oint}$

D.$L={(M)|M is a PDA such that L(M)=\sum ^{0}}$

17. Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three.

A.$(0+1(01^{\ast} 0^{\ast })^{\ast }1)^{\ast }$

B.$(0+11+10(1+00)^{\ast}01)^{\ast }$

C.$(0^{\ast}(1(01^{\ast}0)^{\ast}1)^{\ast })^{\ast }$

D.${(0+11+11{(1+00)}'00)}'$

18.

Consider the following deterministic finite automaton (DFA).

The number of strings of length 8 accepted by the above automaton is_

A.226

B.246

C.256

D.512

19. In a pushdown automaton, ${P=(Q,\sum,\ \Gamma\delta,q}_0,F)$ a transition of the form,

Where p,q $\in Q,\ a\in\sum\cup{\ \varepsilon}$, and $X,Y\in\Gamma\cup{\varepsilon}$ represents
$\left(q,Y\right)\in\delta\left(p,a,X\right)$.
Consider the following pushdown automaton over the input alphabet $\sum={a,b}$ and stack alphabet $\Gamma$={#,A}.

The number of strings of length 100 accepted by the above pushdown automaton is

A.49

B.51

C.50

D.47

20. Consider the following language.

$L = \left\{ x \in {a,b}*|\text{number of a's in x is divisible by 2 but not divisible by 3} \right\}$

A.4

B.6

C.8

D.10

Automata MCQ Test Series Set-1

Total Number of Questions: 20

Each question carries equal marks i.e 1

No Negative Marking

Related