Let $ \Sigma = \{1,2,3,4\} $. For $ x \in \Sigma^* $, let $ {prod}(x) $ be the product of symbols in $ x $ modulo 7. We take $ {prod}(\epsilon) = 1 $, where $ \epsilon $ is the null string. For example, \[ {prod}(124) = (1 \times 2 \times 4) \mod 7 = 1. \] Define \[ L = \{ x \in \Sigma^* \mid {prod}(x) = 2 \}. \] The number of states in a minimum state DFA for $ L $ is ___________. (Answer in integer)

Question

Match LIST-I with LIST-II \[\begin{array}{|c|c|c|}\hline \text{ } & \text{LIST-I} & \text{LIST-II} \\ \hline \text{A.} & \text{A Language L can be accepted by a Finite Automata, if and only if, the set of equivalence classes of $L$ is finite.} & \text{III. Myhill-Nerode Theorem} \\ \hline \text{B.} & \text{For every finite automaton M = $(Q, \Sigma, q_0, A, \delta)$, the language L(M) is regular.} & \text{II. Regular Expression Equivalence} \\ \hline \text{C.} & \text{Let, X and Y be two regular expressions over $\Sigma$. If X does not contain null, then the equation $R = Y + RX$ in R, has a unique solution (i.e. one and only one solution) given by $R = YX^*$.} & \text{I. Arden's Theorem} \\ \hline \text{D.} & \text{The regular expressions X and Y are equivalent if the corresponding finite automata are equivalent.} & \text{IV. Kleen's Theorem} \\ \hline \end{array}\]

\[\text{Matching List-I with List-II}\]

Choose the correct answer from the options given below:

Answer 1

Each string over the alphabet $\Sigma=\{1,2,3,4\}$ produces a value obtained by multiplying its symbols and reducing the result modulo $7$. The empty string contributes the value $1$.

While reading a string from left to right, the only information that matters is the current product modulo $7$. Appending a symbol multiplies this value by $1,2,3,$ or $4$ and reduces it modulo $7$.

Since all symbols are non-zero modulo $7$, the value $0$ is never produced. Starting from $1$, repeated multiplication by $\{1,2,3,4\}$ generates all non-zero residues:

$\{1,2,3,4,5,6\}$

Each of these values can occur as the product of some string, and from each value the future behavior differs depending on whether the product can be driven to $2$. Hence, none of these values can be merged without changing the language.

Therefore, the automaton must have one distinct state for each of the six possible non-zero products modulo $7$.

Hence, the number of states in the minimum DFA is:

$\boxed{6}$

Answer 2

Each string over the alphabet $\Sigma=\{1,2,3,4\}$ produces a value obtained by multiplying its symbols and reducing the result modulo $7$. The empty string contributes the value $1$.

While reading a string from left to right, the only information that matters is the current product modulo $7$. Appending a symbol multiplies this value by $1,2,3,$ or $4$ and reduces it modulo $7$.

Since all symbols are non-zero modulo $7$, the value $0$ is never produced. Starting from $1$, repeated multiplication by $\{1,2,3,4\}$ generates all non-zero residues:

$\{1,2,3,4,5,6\}$

Each of these values can occur as the product of some string, and from each value the future behavior differs depending on whether the product can be driven to $2$. Hence, none of these values can be merged without changing the language.

Therefore, the automaton must have one distinct state for each of the six possible non-zero products modulo $7$.

Hence, the number of states in the minimum DFA is:

$\boxed{6}$

Show Hint

Correct Answer: 6

Solution and Explanation

Top Questions on Regular expressions and finite automata

Questions Asked in GATE CS exam