CODEWITHSUNDEEP
computer-sciencefinite-automata
AkshaiShah
AkshaiShah

Reputation: 5939

The union of two determinstic finite automata?

I'm trying to solve a problem where I have to create a DFA for the union of two languages.

These are: {s is {a, b, c}*| every "a" in s is immediately followed by a "b"} and

{ s is {a, b, c}*| every "c" in s is immediately preceeded by a "b"}

I think I am on the right track, but not sure if it is totally correct. Could someone have a look please?

Upvotes: 0

Views: 11301

Answers (2)

Alex Lockwood
Alex Lockwood

Reputation: 83301

Here's a similar post that explains how to find the union of two DFAs.

The key to understand is that you have to run the two DFAs simultanously, or in general you have to maintain the states of both DFAs in the union DFA.

Edit:

The reason you are getting the incorrect result is because your DFAs are not deterministic and because they do not actually decide the languages you described. I think your calculation of the Union is correct, but you should fix your DFAs before proceeding further.

Upvotes: 1

Emil Vikström
Emil Vikström

Reputation: 91983

The intersection of the two languages are given by L1 ∩ L2 = not(not(L1) ∪ not(L2)) (by de Morgans law).

The complement ("not") of a DFA is given by changing all accepting states to non-accepting and vice versa. This will give you a non-deterministic finite automata (NFA).

The union is created by combining your two DFA or NFA into a new NFA which simultaneously accepts both languages. This is done by introducing a start state from which you can go to the start state of both your NFAs without consuming anything (only consuming ε).

When you've done all this you've got an NFA. You can use common methods to reduce this into a DFA.

Upvotes: 0

Related Questions