Recent questions tagged goclasses-toc-practice-questions

Which of the following is true?A language $L$ is accepted by DFA iff it is accepted by some $\epsilon$-NFA. A language $L$ is accepted by $\epsilon$-NFA iff it is accepte...

This $\epsilon$-NFA accepts which language?$1(01)^*$  $1(01)^* + 1(0+1)^*1$  $1(01)^* + 1(0+1)^*$ None of these

What is $\epsilon$-closure of $q_1$ in the given $\epsilon$-NFA?$\{q_0\}$ $\{q_0,q_1,q_2\}$ $\{q_0,q_2\}$ $\{q_0,q_1\}$

Which of the following strings will not be accepted by the given $\epsilon$-NFA?$\text{abababa}$ $\text{aaaaaaa}$ $\text{ababab}$ $\text{baaa}$

The domain and codomain for the transition function for $\epsilon$-NFA is given by $\_\_\_\_\_\_\_\_$, where $Q$ is a finite set of states and $\Sigma$ is a finite input ...

Which of the following does the given NFA represent? $(11 + 101)^*01$ $(110 + 01)^*11$ $(11 + 110)^*0$ $(00 + 110)^*1$

Given NFA in the first figure is equivalent to the given DFA in the second figure. Is the given statement true?True False

Which of the following statements are correct?There is a $2^k$-state DFA for every $k$-state NFA. There is a $k$-state DFA for every $2^k$-state NFA. There is a $k$-state...

What should be the accepting state(s) in order to accept $1^*00$?$\{Y\}$ $\{Z\}$ Any one of $Y$ and $Z$ can be accepting state $\{X,Y\}$

Which of the following best describes the language accepted by the non-deterministic automaton below?$(a+b)^*a(a+b)^*b(a+b)^*$  $(a+b)^*$  $(a+b)^*a(a+b)b$  $(abb)^*$

The set of reachable state(s) for the string $1101$ for the below NFA is:$\{q_0, q_1\}$ $\{q_1, q_3\}$ $\{q_3\}$ $\{q_2, q_1, q_3\}$

Consider the following two NFAs $A_1$ and $A_2$. Which one of the following is true?Any string accepted by $A_1$ is also accepted by $A_2$ Any string accepted by $A_2$ is...

The cardinality of the language recognized by the below NFA is:Infinite $8$ $9$ $10$

What is the language accepted by the following NFA?The set of strings containing $baba$ as substring The set of strings ending with $abab$ The set of strings beginning wi...

What is the set of final states in the following NFA?$\{q_2, q_4\}$ $\{q_1, q_2, q_3, q_4\}$ $\{q_0,q_1,q_2, q_3, q_4\}$ $\{q_1, q_3, q_4\}$

Consider the DFA over $\Sigma = \{a,b\}$ with states $q_0,q_1,q_2,q_3,q_4$. The start state is $q_0$, and the final states are $q_2$ and $q_4$. The transition function is...

Consider the following finite state machine $A$Which modification makes it a DFA for $L = \{w \in \{a,b\}^* \mid w$ starts with $a$ and has exactly two $a$'s$\}$?Replace ...

Consider a DFA with three states: $I$, $F$, and $D$. $I$ is the initial state, $F$ is the only final state, and $D$ is a dead state. The transitions are: $$\begin{array}{...

The following DFA accepts all those strings in which number of $1$'s and $0$'s areDivisible by $3$ and $2$ respectively. Odd and Even respectively. Even and Odd respectiv...

Two finite state machines are said to be equivalent if they:Have the same number of edges Have the same number of states Recognize the same set of strings Have the same n...

Which state in the following DFA should be made the initial state to make it accept the language $L = \{w \in \{0,1\}^* \mid w$ has even number of $1$s and odd number of ...

Which of the following is the correct description of language recognized by the DFA below?Binary strings not divisible by $4$ Binary strings divisible by $4$ Binary strin...

The node $q_2$ is best defined as $\dots$ $\dots$Final state Dead state Both final and dead state Neither final nor dead state

Which of the following states would be notated as the final state/acceptance state for $L = \{x \in \Sigma^* : \text{length of } x \text{ is } 2\},\ \Sigma = \{a,b\}$?$q...

Is the given figure a DFA?(If your answer is No, enter $\textit{0}$, if Yes, enter $\textit{1}$)

Let $A = \{a, ab, aba, b, ba\}$ and $\operatorname{NOPREFIX}(A) = \{w \in A \mid$ no proper prefix of $w$ is a member of $A\}$. Which of the following strings belong to $...

Let $L = \{a, aa, aaa\}$. Find the number of distinct strings in $L^2$.

Let $\Sigma = \{a,b\}$ and $L = \Sigma^*a\Sigma^*b\Sigma^*a\Sigma^*$. Which of the following strings belong to $L$?$aba$$aaba$$aaab$$baba$$baab$$\epsilon$$aabbaa$

Let $\Sigma = \{0,1\}$ and $L = \{w \in \Sigma^* \mid |w| \le 5\}$. Find the number of strings in $L$.

Let $\Sigma = \{0,1\}$. Which of the following statements are correct?$\Sigma^* = \{\epsilon\} \cup \Sigma^+$ $\epsilon \in \Sigma^+$ $101 \in \Sigma^+$ $\Sigma^+ = \Sigm...