Let Σ={1,2,3,4} For x ∈ Σ*, let prod(x) be the product of symbols in x modulo 7. We take prod(ϵ)=1, where ϵ is the null string. For example, prod(124)=(1×2×4) mod 7=1 prod(124)=(1×2×4)mod7=1. Define L={x∈Σ∗ ∣ prod(x)=2}. The number of states in a minimum state DFA for L is ______
Solution :
The correct answer is 6.
We are given the alphabet .
For any string , is defined as the product of the symbols in modulo 7, with .
We want to find the number of states in the minimum state Deterministic Finite Automaton (DFA) that accepts the language:
.
Let's analyze the possible values of . Since the product is taken modulo 7, the possible values of the product modulo 7 are from the set .
However, let's look at the alphabet . None of the symbols in is a multiple of 7, nor can any product of these symbols be a multiple of 7 because 7 is a prime number and none of the prime factors of the numbers in (which are 2 and 3) can multiply to form a multiple of 7. Thus, the modulo 7 product of any string over can never be 0.
Consequently, the only possible values of for any belong to the set .
Let us define the states of our DFA. The state of the DFA after reading a string must keep track of the current product modulo 7. Since there are 6 possible modulo values , we can define 6 states corresponding to each of these values:
State : current product modulo 7 is 1 (this is also the start state because ).
State : current product modulo 7 is 2 (this is the only accepting/final state).
State : current product modulo 7 is 3.
State : current product modulo 7 is 4.
State : current product modulo 7 is 5.
State : current product modulo 7 is 6.
To verify if all these 6 states are necessary and distinct (i.e., that the DFA is minimal and no states can be merged), we can check the transition behavior.
For any state representing a product and an input symbol , the transition goes to state where:
.
Let's check if all states are reachable from the start state :
- From , reading '1' keeps us in .
- From , reading '2' goes to .
- From , reading '3' goes to .
- From , reading '4' goes to .
- From , reading '2' then '3' gives , reaching .
- From , reading '3' then '4' gives , reaching .
Thus, all 6 states are reachable.
Next, we verify that all 6 states are distinguishable (meaning no two states are equivalent):
Two states and (where ) are distinguishable if there exists a string such that starting from and reading leads to the accepting state , while starting from and reading leads to a non-accepting state, or vice versa.
Mathematically, we want to find a string such that:
but .
Since 7 is a prime number, the integers modulo 7 form a field , meaning every non-zero element has a unique multiplicative inverse .
Thus, the equation has a unique solution .
Since , the value of required to reach the accepting state from will be different from the value required from .
Since we can generate any modulo value in using strings over , every pair of states is distinguishable. Therefore, no states can be merged.
Hence, the minimum state DFA requires exactly 6 states.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.