Deterministic finite automaton parity bit question

Question

for a university assignment ive been tasked with creating a DFA that accepts the regular language (00010 + 1101 + 1010)* and must contain a parity bit at the end to make sure there is an even amount of 0's

I understood this as creating a DFA that handles (00010 + 1101 + 1010)*(0+1)

but under further clarification from the teacher this means that the parity bit is only added on once!

My current diagram that i have attached fails this test. Ive spent the last 2 weeks trying to modify this to only add on one parity bit and accept the string but for the life of me i cant work out how.

Can anyone here help me understand how to do parity bits with DFA's? Am I way off the mark with my working out.

Thanks.

Answer 1

You essentially need two copies of the (00010 + 1101 + 1010) automaton to distinguish the parity, i.e., we need to keep track of the overall parity as well as the 0-1-sequence since the last completed $(00010+1101+1010)^\star$ (fortunately, there is always only one way to reach every valid string):

Thus create nodes carrying mnemonic labels: even, odd0, even00, odd000, odd0001; even1, even11, odd110; odd10, odd101; odd, even0, odd00, even000, even0001; odd1, odd11, even110; even10, even101. Create an arrow labelled 0 from $p\alpha$ to $q\beta$ (where $p,q\in\{\text{even},\text{odd}\}$ and $\alpha,\beta\in\{0,1\}^\star$) if

• $p\ne q$ and $\beta=\alpha0$ or
• $p\ne q$, $\beta=\epsilon$, and $\alpha$ is $0001$ or $101$

Similarly, draw an arrow labelled 1 if

• $p=q$ and $\beta=\alpha1$ or
• $p=q$, $\beta=\epsilon$, and $\alpha=110$

The starting node is "even" and the accepting nodes are "even" and "even0".