Is my DFA correct?

Question

I have to construct a DFA with $\Sigma = \{A, C, D, X\}$ such that the DFA accepts the string $w = CA^{177}$ or $w = A^{177}C$ and sticks in the final state. $A^{177}$ means $177$ times $A$. So $CA_{1} \cdots A_{177}$ and $A_{1} \cdots A_{177}C$ should be accepted and else should be rejected.

For that I've constructed the DFA which is shown in the picture.

The state $175A$ is a placeholder for the part of the DFA which counts $175 As$ and is not a single state.

I think we don't have to draw the whole DFA state by state, since it gets very big. Instead I'd draw a DFA like shown and describe what happens in $175A$ "state".

So the description for $175A$ would be like: $175A$ is a sub DFA with $175$ states, which implements $mod$ $175$.

Is my logic and the DFA correct? Is it minimal?

Thanks Asg

See the DFA drawn by JFLAP1

Answer 1

If the language to be recognized is $\{CA^{177}, \ A^{177}C\}$, your DFA is not correct since it accepts also the word $A^{177}XA^{177}C$ (and many others). The problem is that when your DFA read a "wrong" symbol such as '$D$' or '$X$', it goes back to the initial state, but it should be a "local sink".

A correct and minimal DFA recognizing the language $\{CA^{177}, \ A^{177}C\}$ over the alphabet $\Sigma = \{A,C,D,X\}$ is the following:

Disclaimer: The image is obtained using the xy package for $\LaTeX$, which is not supported by MathJax. Its (not minimal and not elegant) $\LaTeX$ source is:

&&*++[o][F-]{q_{C}} \ar[r]^A \ar[drr]_{C,D,X} &*++[o][F-]{q_{\mathit{CA}}} \ar[r]^A \ar[dr]^<<<<<{C,D,X} &\dots \ar[r]^A &*++[o][F-]{q_{\mathit{CA}^{176}}} \ar[dr]^A \ar[dl]^{C,D,X} \\ \ar[r]&*++[o][F-]{q_0} \ar[ur]^C \ar[dr]_A \ar[rrr]^<<<<<<<<<<{D,X} &&&*++[o][F-]{q_1} \ar@(ur,ul)[]|{A,C,\\D,X}&& *++[o][F=]{q_\mathrm{f}} \ar[ll]^<<<<<<<<<<<{A,C,D,X}\\ &&*++[o][F-]{q_{A}} \ar[r]_A \ar[urr]^{C,D,X} &\dots \ar[r]_A &*++[o][F-]{q_{\mathit{A}^{176}}} \ar[r]_A \ar[u]^{C,D,X} &*++[o][F-]{q_{\mathit{A}^{177}}} \ar[ur]_C \ar[ul]_<<<<{A,D,X}