[Math] Creating a deterministic Finite state machine that accepts even 1s parity

automatadiscrete mathematicsfinite-state machine

Ive been working on this project for over a week now and its coming due soon, and im in no way going to finish it soon. the project is essentially where we have been assigned 3 "Codes" which form a language, mine are "1111", "101" and "10" and we need to create a finite state acceptor that will accept all strings from this language, with a parity bit on the end (mine is EVEN 1 parity), where if the string has an even number of 1s, the last bit will be 0, and if it has an odd number of 1s the last bit will be 1. i have created 2 Deterministic finite state machines, one to detect even 1 parity, and one to accept all the combinations of those strings. my drawings for both are below (any states that do not have 0 or 1 transitions are, those transitions are to a black hole state.)
(i dont have reputation 10 on the maths version of the site so i cant post images)
two automatons

The 0 transition from state A in the main FSA is so that the FSA will accept the empty string, as the empty string will be assigned a parity bit of 0)

now i need to figure out a way to combine these two together so that i get one FSA which will accept all strings and the parity bit.

the final submission is also in table form, ie:

State 0 transition 1 transition

A … …

B … …

i know that what i need to do is find the intersection of the two languages but im not too sure how to do that.
the guideline also gives this clue but if anything it confuses me more:

"Let L denote the regular language (A + B + C)*(0 + 1) and let M denote the collection of all strings that satisfy the parity property. We then need to design a finite state automaton that accepts precisely all the strings of L ∩ M. However, we cannot handle the intersection directly.

The idea is to use De Morgan's law, that L ∩ M = -((-L)+(-M)), where we have used + to denote union. "

any help would be much appreciated, im really stuck on this, and im sure its either gaps in my knowledge or me completely missing something i have to do, but any help would be greatly appreciated.

Best Answer

we have been assigned 3 "Codes" which form a language, mine are "1111", "101" and "10" and we need to create a finite state acceptor that will accept all strings from this language, with a parity bit on the end (mine is EVEN 1 parity), where if the string has an even number of 1s, the last bit will be 0, and if it has an odd number of 1s the last bit will be 1

So you need to accept the language $\{11110, 1010, 101\}$. This basically consists of two chains of states and a dump state for completeness.

Related Question