Creating a Deterministic Finite Automata with Odd 0 Parity - Combining DFA

Question

I've been working on this project for almost a week now, however it's honestly above my understanding and I just cannot find help elsewhere.

My problem now is that, I just don't know how to combine FSA's. To what I understand I have to combine my 2 FSA's which is the main FSA and the Odd 0 Parity FSA.

This is the main FSA:

This is the Odd 0 Parity FSA:

I've been confused about this project of almost a week now, and it was already due awhile ago so it's too late to submit it, but I have still been stuck on it and I really want closure on it.

Also can anyone explain why this expression didn't work? (Rejects 0100)

((00100|00011|010)(00100|00011|010))*0|((00100|00011|010)(00100|00011|010))*(00100|00011|010)1

Answer 1

I don't know of a general way of merging FSAs like this, but here's an approach for your specific problem.

Make two copies of your original FSA, call them 'Even' and 'Odd'. The invariant is that whenever you're in a state of one of the sub-FSAs, the parity is as indicated by its name. To achieve this, every 0 transition must jump to the corresponding node in the other FSA; 1 transitions continue in the same FSA.

The start state is in Even. The corresponding node in Odd is unreachable, and can be deleted.

All of your original accepting states are no longer valid, as you haven't verified the parity bit yet. In Odd, each of those states needs a 1 transition to the new accepting state. In Even, a 0 from a former accepting state needs to be an accepting state; all of those transitions exist already, so their target (node #1) becomes the new accepting state.

As for why your regexp solution didn't work, consider the first subgroup within it: (00100|00011|010). That includes subpatterns with both even and odd numbers of 0s; you have no way to tell which one matched, so you've ALREADY permanently lost track of what the final parity will be. You'd have to somehow arrange for each individual part of the overall regex to match only things with the same parity - I'm not entirely sure that this is even possible in a traditional regex. (If I was solving this using a modern computer implementation of regular expressions, I'd use a lookahead assertion to verify the overall parity as an entirely separate process from verifying the concatenation of your three patterns.)

EDIT: Illustrated!

We start by making two copies of your original FSA, labelled for even or odd parity. You could also think of this as making a copy of the nodes in your 2nd FSA for each node in your first FSA. The start state is in Even, since you initially have zero 0s. State o0 is unreachable, and will be omitted in further diagrams. The labels aren't valid yet, since every time there's a 0 transition, the parity changes - those transitions need to go to the other copy of the FSA. I couldn't get graphviz to produce anything that's even slightly comprehensible with all of these crossovers, so I'm going to have to drop the boxes around the even/odd states. Here's the diagram with crossovers applied: This FSA matches exactly the same sentences your original one did, except that you always know whether you have odd or even parity at each state. The accepting states are still the same as the original ones: to handle your final parity bit, we need to add one final transition from each of those states to a new accepting state. From all three Odd accepting states, there is a 1 transition to the new state labelled "o". From all four Even accepting states, the final parity bit would be a 0 transition - which happens to correspond to the existing "o1" state. Here is the final diagram, with the updated accepting states:

Answer 2

Okay so, here are my thoughts jason pointed quite well the problems you will encounter, first I would create a table with my codes, and create a set of strings that can be accepted

A = 00100
B = 00011
c = 010

and a set of acceptable strings according to your guidelines would be 000110 001000100001110

Give your letter codes expressions like 001000 won't be acceptable with an even 0 parity property. Please notices that that's just an A so A or C messages won't be accepted. I would encourage you to redo your letter codes, a 3 digits code will be easier, because you'll have a larger set of accepted strings and your DFA will be probably smaller.

Give your codes, it is hard to implement a DFA only solution, or a simple DFA only solution. Also remember that codes between letters shouldn't be prefixes of other codes, this will simplify your problem.

Let's say our codes are

A = 101
B = 001
C = 110

then we have the following set of acceptable messages with an even 0 pairing property:

1010
1011010
1100
0011100

Notices that in human language you'll have an amount of A's followed by a 0 any amount of BC's followed by a 0 and so on. You can start forming your regex from there. I hope this is clear enough.

Answer 3

What you want is a DFA that accepts what is called the intersection of two languages:

1. The language (00100 + 00011 + 010)*(0+1)
2. The language of strings with an odd number of 0s

(Note: I add (0+1) to stand for the extra bit you intend to add to the end. If this is not what you meant, please ignore).

I posted a well-reviewed answer to the question of how to combine DFAs in this manner: see here. A brief summary:

1. Create DFAs M1 and M2 for both of your languages
2. Create a new DFA M3 as follows:
   • Q3 = Q1 x Q2 (states of M3 are ordered pairs of states from M1 and M2)
   • S3 = (S1, S2) (the initial state is the ordered pair of initial states of M1, M2)
   • A3 = {(q1, q2) | q1 in A1, q2 in A2} (accepting states are ordered pairs of states where both elements are accepting states in their respective machines. This gives you intersection. For union, at least one must be accepting. For difference, q1 must be accepting and q2 must not be. Etc.)
   • f3 : Q3 x E -> Q3 is defined such that f3((q1, q2)) = (q1', q2') wherever f1(q1) = q1' and f2(q2) = q2'.

In your case, you will get a DFA with twice as many states as the first DFA. The first "copy" of that DFA will represent even parity and the second "copy" will represent odd parity. Your machine will work the same as before but will bounce back and forth between "copies" whenever you see a 0. Only the odd-parity copy will keep its accepting states.