GATE CS Regular Expressions and Finite Automata questions

Let $M$ be a nondeterministic finite automaton (NFA) with $6$ states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ?

Consider the following two finite automata $D_{1}$ and $D_{2}$. Which of the following statements is/are true?

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma=\{a, b\}$. Identify which of the following language(s) is/are accepted by the given DFA.

Consider a finite state machine (FSM) with one input $X$ and one output $f$, represented by the given state transition table. The minimum number of states required to realize this FSM is _______. (Answer in integer). …

Let $\Sigma=\{1,2,3,4\}$. For $x \in \Sigma^{*}$, let $\operatorname{prod}(x)$ be the product of symbols in $x$ modulo 7. We take $\operatorname{prod}(\epsilon)=1$, where $\epsilon$ is the null string. For example, $\operatorname{prod}(124)=(1 \times 2 \times 4) \bmod 7=1$. Define …

​Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. Which of the following statements is/are FALSE?

Consider the following two regular expressions over the alphabet $\{0,1\}$ : $r= 0^{*}+1^{*}$ $s = 01^{*} + 10^{*}$ The total number of strings of length less than or equal to $5$, which are neither in $r$ nor in $s$, is ________.

​​​​Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below?

​​Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $\text{M}$?

Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}$, where $|w|$ denotes the length of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.

Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{DFA}$ runs on the alphabet $\{0,1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state. Which one of the following regular expressions correctly describes the language accepted by …

Consider the following definition of a lexical token $\textbf{id}$ for an identifier in a programming language, using extended regular expressions: …

Consider the language $L$ over the alphabet $\{0,1\}$, given below: $$L=\left\{w \in\{0,1\}^{*} \mid w \text{ does not contain three or more consecutive } 1 \text{ 's }\right\} .$$ The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

Consider the following language: $$L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$$ Which one of the following deterministic finite automata accepts $L?$

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

Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________

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. …

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.

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