Question

I have an assignment for University and I am not sure how to go about it. Could anyone help with its and let me know how to do it .

Cheers

Your task is to design a binary finite state automaton (FSA) to accept all strings that represent valid messages (for your particular codes and parity property) and reject all others. This FSA must be DETERMINISTIC, REDUCED and must be in STANDARD FORM PARITY Odd 1 1101 1001 00011 Complete the following table for your answer. It must be a deterministic machine, and state 0 must be the initial state. The form contains sufficient room for up to 30 states This is many more states than you will need if you do the project using the techniques taught in DMTH237. If you do not use a state, leave the entries blank. Type the number for the state for each transition. Check the tick box if the state is accepting. Leave it unchecked if it is not. Note that while this form accepts machines with implicit black holes - also known as dumping states - (simply leave the transition blank) to help you with testing, a machine in reduced standard form must show any required black hole explicitly as one of the numbered states. This means that a machine with implicit black holes can get at most 6 of the 8 marks. STATE 0 TRANSITION 1 TRANSITION ACCEPTING 10 12 13 14 15 16 17 18

Answer 1

I would like tO provide how get started with the assignment.

Let L denote the regular language (A + B + C)*(0 + 1) — make sure you understand what this means! — 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. We can then use the following simple idea:

Suppose that AK is a deterministic finite state automaton that accepts precisely all the strings of a regular language K. Then to obtain a deterministic finite state automaton that accepts precisely all the strings of the regular language (-K), all we need to do is to change AK in the following way: make all accepting states non-accepting and all non-accepting states accepting.

Note, however, that this idea only works for deterministic finite state automata, and make sure not to leave the dumping (black hole) state out if it is needed.

We therefore proceed in the following way:

Describe the regular language L using 0, 1, concatenation, + and *.

Design a deterministic finite state automaton AL that accepts precisely all the strings of the regular language L. To do this, you may need to design a non-deterministic one with null transitions, remove the null transitions and then convert to a deterministic one.

Design a deterministic finite state automaton AM that accepts precisely all the strings of the regular language M.

Using the simple idea described above, obtain a deterministic finite state automaton A-L that accepts precisely all the strings of the regular language (-L), and a deterministic finite state automaton A-M that accepts precisely all the strings of the regular language (-M).

Using the finite state automata A-L and A-M, design a non-deterministic finite state automaton A(-L)+(-M) that accepts precisely all the strings of the regular language (-L)+(-M). Note that a deterministic finite state automaton can be considered a non-deterministic one.

Remove null transitions from your non-deterministic finite state automaton A(-L)+(-M) and convert it to a deterministic finite state automaton. If you follow the conversion process religiously, then your deterministic finite state automaton should be in standard form and have no unreachable states.

Obtain a finite state automaton AL∩M that accepts precisely all the strings of the regular language L ∩ M.

At this point, you may wish to make an online submission to see whether your finite state automaton works, and make appropriate corrections if it does not.

Apply the Minimization process. Be careful to remove unnecessary states in such a way to maintain standard form.

Make an online submission.

That is how you need to proceed through the assignment. I do not have any example how it should look like. But you could always check the answer by submitting it through the link mentioned in the file, I can provide you the login details if possible.