Where did I go wrong creating a Deterministic finite automaton?

Question

My goal was to create a Deterministic finite automaton that handled the regular language (00010 + 1101 + 1010)* and had a parity bit at the end to make sure 0's where even.

To clarify what I mean by even parity bit, once the finite automaton loops through all possible choices, it determines if the DFA has an even amount of 0's, if there is it will add a 0 to the end of the message, else it will add a 1.

E.G. the machine will accept 000101 but not 00010/ 10110 but not 1011

I designed an M1 that's a bit complicated so i have a picture

And my M2 of the language I also drew for the purpose of this question, which is meant to add a 0 if there is an odd amount of 0's and a 1 if there is an even amount of 0's at the end of every message.

I have combined the two, but I'm still getting the wrong acceptance of binary strings. I believe M2 too be my problem but I'm not sure.

Please give advice as to where I'm going wrong.

Thank you.

Answer 1

DFAs do not add symbols to the input string. You clearly want to read an input string and determine whether it is composed of a string from your given regular language plus a single parity bit at the end.

To do so, you first need to construct a new DFA that accepts strings that satisfy the above requirements, except that the last bit need not be a parity bit. But the new DFA must still enforce exactly one extra bit. Then you construct a second DFA that accepts only binary strings that have correct parity. Then from both DFAs you construct a DFA that accepts the intersection of both languages, and you're done.

Answer 2

The other answer does not require any thinking. Here is another approach which requires some thought but is actually easier to get right (once you understand it). The idea is always to pretend to be a DFA and determine exactly what you need to keep track of.

In this problem the string without the parity bit breaks into chunks of 3 types. You want to keep track of which of the 3 types the current chunk is and how far along the chunk you have read, and also the parity of the number of zeros you have seen so far, at least until the very end. Instead of parity up to the current point it is simpler to remember parity up to before the current chunk.

In other words, you have two main states $S_0,S_1$, one for each parity between each chunk. You then build a sequence of states to recognize the chunk "00010". Since it has an even number of zeros, you need such a sequence from $S_0$ to $S_0$ and a separate such sequence from $S_1$ to $S_1$. Then you do chunk "1101" in the same way, but since it has an odd number of zeros, the sequences go to the opposite main state instead, namely from $S_0$ to $S_1$ and from $S_1$ to $S_0$. Lastly you do chunk "1010", but to keep it a DFA you reuse the part that recognizes the first bit. Finally, to settle the parity bit is easy, because the final state must come immediately after $S_0$ or $S_1$, and of course you expect a zero after $S_0$ and a one after $S_1$. Again, you may need to reuse some existing states to keep it a DFA.

Answer 3

@user2820

So if i understand you correctly i should be joining together

AND