I have to create a Deterministic finite automaton that handles the regular language (0100 + 0001 + 01)* and has a parity bit at the end to make sure 0's are even.
To clarify what I mean by even 0 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 arent, it will add a 0 to the end of the message, else it will add a 1.
E.G. the machine will accept 01000 but not 01001/ 0101001 but not 0101000
I have created an M1 that accepts (0100+0001+01)* HERE
And then created a M2 to accept (0100+0001+01)*(0+1). This expression/machine accounts for the parity bit (0+1) HERE
And then a M3 to accept strings with Even 0s HERE> i.stack.imgur.com/eyPMk.png
My question is, what do I do next? Do I combine M1 and M3? M2 and M3? Do I take the complement of something?
There is a similar question at
math.stackexchange.com/questions/1760909/where-did-i-go-wrong-creating-a-deterministic-finite-automaton
however, the OP did not (to my knowledge) quite explain what they did to solve it. I am hoping you might be able to.
Any help appreciated, thanks.
Let $\alpha$ denote the regular expression $0100 + 0001 + 01$. The language you're actually interested in is that of the regular expression $$(\alpha\alpha)^*1 + \alpha(\alpha\alpha)^*0,$$ so you could just create a DFA for that language.
But, taking your approach, you should combine $M_2$ (for $\alpha^*(0+1)$) and $M_3$. From those two, you need to build a new DFA that accepts words that are accepted by both automata.
Do you know how to do that? Hint: the states of the new DFA are pairs $(t_2, t_3)$ where $t_2$ is a state of $M_2$ and $t_3$ a state of $M_3$.