Just learned about DPDA's on my Theory of computation class. Professor gave us a semester task to create a deterministic pushdown automaton state diagram that is able to accept all strings multiples of 3; (Binary notation multiples of 3 of the string of 1's and 0's given) on JFLAP software.
I tried to do it but im confused as if it is even possible, . I created this CFG but im not sure is the appropiate way to solve this issue.
S -> 0A | 1B A -> 0S | 1C B -> 0C | 1S C -> 0B | 1A
Any help is appreciated, thanks in regards.
It is possible to design a DPDA for this language. The important fact about this language is that, it is in fact a regular language, which means that the power of a DPDA is not needed to recognize it. The language can also be recognized by a weaker device, i.e., a DFA or an NFA. You need three states. Each state corresponds to the remainder of dividing a number (in its binary form) by three (0, 1, or 2). Because the multiples of three are supposed to be accepted, the state that corresponds to 0 (which is also the initial state) should be assigned as the final state.
Now, if there is a requirement that you must use a DPDA to describe this language, and not a DFA, just attach a stack to your DFA, but don't use it at all. That is, don't push anything onto the stack, and don't pop anything from it. In this case, you will have a DPDA for this language. I drew this DPDA in JFLAP. As you can see, the stack is not used at all.