-1
$\begingroup$

Design a DFA that accepts language $$L = \left\{ x \in \{ 0, 1, 2 \} : \text{ sum of digits in } x \text{ is } 2 \mod 3 \right\}$$


How to make a DFA for this? I have no idea how to solve this dfa problem. I have a solution by someone but I am not getting concept to start this solution.

$\endgroup$
1
$\begingroup$

A good first step for designing automata is to think about what states you will need. Here, you would need to remember the sum – which is not possible with a DFA – but thankfully, we only need to remember the sum in mod3 arithmetic, which means it can only have three distinct values: 0, 1 or 2. Therefore, we can keep track of the sum mod 3 with a finite number of states.

Then you need to devise the state transitions between the states representing these values. A convenient fact of modular arithmetic to remember is that $a + b \equiv a - (n-b) \mod n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.