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)
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)
Show Hint
Solution and Explanation
The function \( {prod}(x) \) maps strings over \( \Sigma \) to values in the set \( \{0,1,2,3,4,5,6\} \) modulo 7. Since this function tracks the product of elements modulo 7, it defines a residue class system of at most 7 possible values.
Step 1: Compute the transition function for modulo 7 residues Each input character \( c \in \Sigma \) modifies the current residue \( r \) via multiplication \( (r \times c) \mod 7 \). Since all values map to one of 7 possible residues, the DFA must have at most 7 states.
Step 2: Identify the minimum number of states - The DFA needs one state for each residue \( 0,1,2,3,4,5,6 \) modulo 7. - The accepting state is the one corresponding to residue 2. - Since multiplication modulo 7 never produces 0 for any sequence of nonzero values, state 0 is unreachable. Thus, the minimal DFA requires 6 states (corresponding to residues \( 1,2,3,4,5,6 \)).
Top Questions on Regular expressions and finite automata
- Given a Context-Free Grammar \( G \) as follows: \[ S \to A a \ |\ b A c \ |\ d c \ |\ b d a \] \[ A \to d \] Which ONE of the following statements is TRUE?
- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
- 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)
- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
- Consider two grammars \( G_1 \) and \( G_2 \) with the production rules given below:
\[ G_1: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, \text{if } E \text{ then } S \text{ else } S \,|\, a \\ E &\to b \end{aligned} \] \[ G_2: \begin{aligned} S &\to \text{if } E \text{ then } S \,|\, M \\ M &\to \text{if } E \text{ then } M \text{ else } S \,|\, c \\ E &\to b \end{aligned} \] whereif,then,else,a,b,care the terminals.
Which of the following option(s) is/are CORRECT?- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
- Let \( G_1, G_2 \) be Context-Free Grammars (CFGs) and \( R \) be a regular expression. For a grammar \( G \), let \( L(G) \) denote the language generated by \( G \). Which ONE among the following questions is decidable?
- GATE CS - 2025
- Theory of Computation
- Regular expressions and finite automata
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:
- CUET (PG) - 2025
- Data Science
- Regular expressions and finite automata
Questions Asked in GATE CS exam
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______________. {(Answer in integer)}
- GATE CS - 2025
- Flip-Flop
Consider the following C code segment:
int x = 126, y = 105; do { if (x > y) x = x - y; else y = y - x; } while (x != y); printf("%d", x);The output of the given C code segment is ____________. (Answer in integer)
- GATE CS - 2025
- Programming in C
The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm:
Multiplicand (\( M \)) Multiplier (\( Q \)) 1100 1101 1110 1101 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is __________. (Answer in integer)
- GATE CS - 2025
- Complementation
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures
Consider the following C program
The value printed by the given C program is __________ (Answer in integer).- GATE CS - 2025
- Programming in C