Question Details

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 ______

Show Answer
Correct Answer
6

Solution :

The correct answer is 6.

We are given the alphabet Σ={1,2,3,4}.
For any string x∈Σ*, prod(x) is defined as the product of the symbols in x modulo 7, with prod(ϵ)=1.
We want to find the number of states in the minimum state Deterministic Finite Automaton (DFA) that accepts the language:
L={x∈Σ*∣prod(x)=2}.

Let's analyze the possible values of prod(x). Since the product is taken modulo 7, the possible values of the product modulo 7 are from the set {0,1,2,3,4,5,6}.
However, let's look at the alphabet Σ={1,2,3,4}. 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 prod(x) for any x∈Σ* belong to the set {1,2,3,4,5,6}.

Let us define the states of our DFA. The state of the DFA after reading a string x must keep track of the current product modulo 7. Since there are 6 possible modulo values {1,2,3,4,5,6}, we can define 6 states corresponding to each of these values:
State q1: current product modulo 7 is 1 (this is also the start state because prod(ϵ)=1).
State q2: current product modulo 7 is 2 (this is the only accepting/final state).
State q3: current product modulo 7 is 3.
State q4: current product modulo 7 is 4.
State q5: current product modulo 7 is 5.
State q6: 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 qi representing a product i��{1,2,3,4,5,6} and an input symbol a∈Σ, the transition goes to state qj where:
j=(i×a)mod7.

Let's check if all states are reachable from the start state q1:
- From q1, reading '1' keeps us in q1.
- From q1, reading '2' goes to q2.
- From q1, reading '3' goes to q3.
- From q1, reading '4' goes to q4.
- From q1, reading '2' then '3' gives (1×2×3)mod7=6, reaching q6.
- From q1, reading '3' then '4' gives (1×3×4)mod7=12mod7=5, reaching q5.
Thus, all 6 states are reachable.

Next, we verify that all 6 states are distinguishable (meaning no two states are equivalent):
Two states qi and qk (where i≠k) are distinguishable if there exists a string w such that starting from qi and reading w leads to the accepting state q2, while starting from qk and reading w leads to a non-accepting state, or vice versa.
Mathematically, we want to find a string w such that:
(i×prod(w))mod7=2 but (k×prod(w))mod7≠2.
Since 7 is a prime number, the integers modulo 7 form a field ℤ7, meaning every non-zero element i∈{1,2,3,4,5,6} has a unique multiplicative inverse i-1mod7.
Thus, the equation (i×P)mod7=2 has a unique solution P=(2×i-1)mod7.
Since i≠k, the value of P required to reach the accepting state from qi will be different from the value required from qk.
Since we can generate any modulo value in {1,2,3,4,5,6} using strings over Σ, every pair of states is distinguishable. Therefore, no states can be merged.

Hence, the minimum state DFA requires exactly 6 states.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

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.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: