What is the intersection of two languages with dif

Question

I did some googling on this and nothing really definitive popped up.

Let's say I have two languages A and B.

A = { w is a subset of {a,b,c}* such that the second to the last character of w is b }

B = { w is a subset of {b,d}* such that the last character is b }

How would one define this? I think the alphabet would be the union of both, making it {a,b,c,d} but aside from that, I wouldn't know how to make a DFA of this.

If anyone could shed some light on this, that would be great.

Answer 1

From a set-theoretic perspective, each language is just a set of strings over some alphabets Σ₁ and Σ₂. If you intersect two languages, the only strings that can possibly be in the resulting set are those strings that are made of characters in Σ₁ ∩ Σ₂, since any characters not in that set must belong to strings purely in one set.

As for how to build a DFA for this - I would suggest starting off by answering this question - given any regular language L over alphabet Σ, how would you modify that DFA to have language Σ ∪ { x }, where x ∉ Σ? One way to do this would be to add in a new "dead state" with a transition to itself on all characters in Σ ∪ { x }, then to add a transition from every state in the DFA to the dead state on character { x }. You can then use this to transform the DFAs for the original languages over Σ₁ and Σ₂ to have alphabets Σ₁ ∪ Σ₂. Once you've done that, you can use the normal algorithm for intersecting two DFAs to compute their intesection and thus get back a DFA for the intersection of the two languages.

Hope this helps!