Σ={1,2,3,4}. prod(x) = product of symbols in x mod 7; prod(ε)=1. L={x∈Σ* | prod(x)=2}. Number of states in a minimum DFA for L is __________.

Answer: 6Concept — DFA for Modular Product Language: The product of elements from {1,2,3,4} modulo 7 can never equal 0 (since none of 1,2,3,4 is divisible by 7 and their products never introduce factor 7). Possible values mod 7 = {1,2,3,4,5,6}.Each state tracks the current product mod 7. Starting state = 1 (empty string). Transitions: on symbol s, multiply current state value by s mod 7. Accepting state = 2. All 6 states are reachable and distinguishable → minimum DFA has 6 states.

GATE-CS is a competitive examination conducted in India. This question is from the 2025 GATE-CS Theory of Computation paper.

How can I prepare for GATE-CS Theory of Computation?

To prepare for GATE-CS Theory of Computation, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2025 question covers Finite Automata (DFA and NFA) topic.

What is the difficulty level of this question?

This GATE-CS 2025 Theory of Computation question has a medium difficulty level and is marked as an important question.

Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

GATE-CS Theory of Computation 2025 - Σ={1,2,3,4}....

Consider the following two finite automata D1 and D2. Which of the following statements is/are true?

HARD2026GATE-CSTheory of Computation

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of th…

MEDIUM2026GATE-CSTheory of Computation

A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which …

MEDIUM2025GATE-CSTheory of Computation

Consider a DFA defined over the alphabet Σ = {a, b}. Identify which of the following language(s) is/…

MEDIUM2025GATE-CSTheory of Computation

Let Σ={a,b,c}. #ₐ(x) = occurrences of a in x. Which option(s) define regular language(s)?

MEDIUM2025GATE-CSTheory of Computation

Consider a 5-state DFA M accepting language L(M) in {0,1}*. For any string w, n0(w) = number of 0's …

HARD2024GATE-CSTheory of Computation

Σ={1,2,3,4}. prod(x) = product of symbols in x mod 7; prod(ε)=1. L={x∈Σ* | prod(x)=2}. Number of states in a minimum DFA for L is __________.

Master GATE-CS with Our Test Series

More Questions from Finite Automata (DFA and NFA)

Frequently Asked Questions

Σ={1,2,3,4}. prod(x) = product of symbols in x mod 7; prod(ε)=1. L={x∈Σ* | prod(x)=2}. Number of states in a minimum DFA for L is __________.

Master GATE-CS with Our Test Series

More Questions from Finite Automata (DFA and NFA)

Frequently Asked Questions