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)
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.
firstly create a state diagram for the regular expression derived from your language given to you for your FSA, not including the parity bits. for me, my codes were 1111,101,10, and my regular expression then became (1111+101+10)* you can take this and use this website to generate a deterministic finite state acceptor for you to get an idea how its done. http://ivanzuzak.info/noam/webapps/fsm_simulator/
once you have created your deterministic fsa (ie. one without null transitions, as a more basic form ) then you need to check for the parity. to do this, as dtldarek put so well, you need to duplicate your current machine, and have them connect to one another. what i mean by this, is that you have your original machine, with the initial state, that stays the same, but now you have the duplicated one right next to it. (when you are drawing this, only draw the state circles not the transitions between them, we will add this later.) now go through the drawing and rename each state in the original machine from A-Z, and name each state on the new machine A1-z1, so that its easy to see which state you need to transition to. (it also helps if you draw out your duplicated machine right next to it, keeping all the state circles in the same relative positions as the original one.) now what you need to do is draw your transitions based on your parity bit. for me, i had even 1 parity, which meant i needed to track how many 1s i had. now here is the bit i had a bit of trouble getting my head around. what you need to do is let the state transitions help you keep track of your important bits (in my case the 1s). what you need to do is for every 1 transition you go to the same state you would have before, but in the new diagram. for example if you had a 1 transition from A to C, then go from state A, to state C1. and for every 0 transition, stay within the same diagram. when you do this, every time you are in the new diagram on the right, there will be an odd number of 1s, and every time you are in the original diagram there will be an even number of 1s. now we use this to our advantage, and from the accepting states we had before, add a new transition (1 or 0 depending on which side youre on) from the accepting state, to a new accepting state. this means that any string that was accepted previously needs to now have an extra 1 or 0 to be accepted. this will be the parity bit. this needs to be fiddled with a bit, because sometimes you will have used 1 or 0 transitions already for those original accepting states and you wont have any left, which means youll have to find another accepting state to go to.
so for example state C and C1 are accepting states. since state C is in the original diagram, any string that was accepted by C will have an even number of 1s, which satisfies our even 1 parity condition. so now we make C no longer accepting and 0 transition from there to an accepting state, to add the parity bit. its the opposite for C1, where since its in the duplicate, it has an odd number of 1s, so we 1 transition from there to a new accepting state, and remove C1's acceptance
i hope that helps a bit !