Hi,
I am trying to understand the intersection of 2 DFA's. I got the following link:
Intersection of DFA

I can't understand why they have not used the symbol 'b':
For M', we have...

1. E' = {a}//Here
2. Q' = {s0, s1}
3. q0' = s0
4. A' = {s0}
5. f'(s0, a) = s1, f'(s1, a) = s0

Similarly in the following:
For M''', we get...

1. E''' = {a}
2. Q''' = {(s0, t0), (s0, t1), (s0, t2), (s1, t0), (s1, t1), (s1, t2)}
3. q0''' = (s0, t0)
4. A''' = {(s0, t0)} for intersection, {(s0, t0), (s0, t1), (s0, t2), (s1, t0)} for union, {(s0, t1), (s0, t2)} for difference.
5. f'''((s0, t0), a) = (s1, t1), f'''((s1, t1), a) = (s0, t2), f'''((s0, t2), a) = (s1, t0), f'''((s1, t0), a) = (s0, t1), f'''((s0, t1), a) = (s1, t2), f'''((s1, t2), a) = (s0, t0).

//in f''', there is no 'b' transition.

Somebody please guide me.

Zulfi.

 

Uh, did you look at the statement immediately before the definition of M'?

"There you go! Let's now consider two machines: one which accepts a^2n, and one which accepts a^3n (the intersection should be a machine accepting a^6n... right?)."

 

Hi,
Are you talking about the following one:

A DFA is a 5-tuple (E, Q, q0, A, f) where

1. E is the input alphabet, a non-empty finite set of symbols

Do we have to consider all the symbols one by one?
Somebody please guide me.
Zulfi.

 

No, I'm talking about the statement IMMEDIATELY before they give you definition of M' -- namely the one that I QUOTED in my response.

Let's try it again:

There you go! Let's now consider two machines: one which accepts a^2n, and one which accepts a^3n (the intersection should be a machine accepting a^6n... right?).

For M', we have...

1. E' = {a}
2. Q' = {s0, s1}
3. q0' = s0
4. A' = {s0}
5. f'(s0, a) = s1, f'(s1, a) = s0

The define the language that M' accepts. "one which accepts a^2n".

Why do you think the alphabet have 'b' in it?

If it should have 'b' in it, why are you okay with it not having 'p', 't', or 'z' in it?

 

Hi,
First of all in their question 1.4 (b) and part (d) , there is no such thing like a^2n. But both the DFA's show the inputs 'a' and 'b'. If we are not able to under stand each other, lets talk about in general terms. I have two machines and I want to find their intersection. Machines have both 'a's and 'b's as inputs. How we would go for finding the intersection. Lets suppose 3 cases: (1) both have equal number of states (2) both have different number of states i.e. Machine one has 2 states and Machine 2 has 3 states (3) Machine 1 has 3 states and Machine 2 has 2 states.

How will we find the intersection? Both the machines have symbols 'a' and 'b'.

Zulfi.

 

Hi,
First of all in their question 1.4 (b) and part (d) , there is no such thing like a^2n. But both the DFA's show the inputs 'a' and 'b'.

So what?

Read what the person that responded wrote! They used two machines as an example. These machines are NOT the machines in the question because they weren't going to just provide a solution to the person's homework. They very explicitly stated the two languages that M' and M'' accept and neither of those languages has a 'b' in it -- both languages only have 'a' in their alphabet.

If we are not able to under stand each other, lets talk about in general terms. I have two machines and I want to find their intersection. Machines have both 'a's and 'b's as inputs. How we would go for finding the intersection. Lets suppose 3 cases: (1) both have equal number of states (2) both have different number of states i.e. Machine one has 2 states and Machine 2 has 3 states (3) Machine 1 has 3 states and Machine 2 has 2 states.

How will we find the intersection? Both the machines have symbols 'a' and 'b'.

The algorithm is right there.

A DFA is a 5-tuple (E, Q, q0, A, f) where

1. E is the input alphabet, a non-empty finite set of symbols
2. Q is the set of states, non-empty and finite
3. q0 is the start state, an element of Q
4. A is the set of accepting or final states, a subset of Q
5. f is the transition function, taking pairs from Q x E to Q

Say we have two machines M' = (E', Q', q0', A', f') and M'' = (E'', Q'', q0'', A'', f''). To make the discussion easier, we assume E' = E''. We will now construct M''' so that L(M''') = L(M') intersect (or union or difference) L(M'').

1. Take E''' = E'' = E'
2. Take Q''' = Q' x Q''
3. Take q0''' = (q0', q0'')
4. Take A''' = (x, y) where x in A' and y in A'' (for union, x in A' or y in A''; for difference, x in A' but not y in A'').
5. Take f'''((x, y), e) = (f'(x, e), f''(y, e)).

The number of states in each machine is immaterial.

If one machine has N states and the other machine has M states, then the new machine has up to N·M states (not all of them are reachable and so can be pruned).

 

Hi,
<Read what the person that responded wrote! They used two machines as an example. These machines are NOT the machines in the question because they weren't going to just provide a solution to the person's homework. They very explicitly stated the two languages that M' and M'' accept and neither of those languages has a 'b' in it -- both languages only have 'a' in their alphabet. >

That is the problem, I can't understand. Can you please provide me an example of intersection 2 DFAs over 'a' and 'b' symbols?
Thanks a lot for clearing my concerns.

Zulfi.