GATE CS 2014 Set 1 Q16 — Regular Expressions and Finite Automata

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?