GATE CS Regular Expressions and Finite Automata questions

Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ denote composition on functions. For a string $x=x_1 x_2 \dots x_n \in \Sigma^n, n \geq 0$, let $\pi(x)=x_1 \circ x_2 \circ \dots \circ x_n$. Consider the language …

Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true?

Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $0$'s and two consecutive $1$'s?

Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT?

The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.

Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.

Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ $X_2 = 0 X_1 + \{ \lambda \}$ Which one of the following …

Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)?

Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^*$ $0^*1^*1+11^*0^*1$ $(0+1)^*1$

Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$?

The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______. $$a^*b^*(ba)^*a^*$$

Consider the DFA $A$ given below. Which of the following are FALSE? Complement of $L(A)$ is context-free. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*)$ For the language accepted by $A, A$ is the minimal DFA. $A$ accepts all strings over $\{0, 1\}$ of length at least $2$.

Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are:

What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.

A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below. Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?

Definition of a language $L$ with alphabet $\{a\}$ is given as following.$$L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$$What is the minimum number of states needed in a DFA to recognize $L$?

Which of the following pairs have DIFFERENT expressive power?