0

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?

rink.attendant.6
  • 44,500
  • 61
  • 101
  • 156
AkshaiShah
  • 5,739
  • 11
  • 37
  • 45

2 Answers2

1

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.

Community
  • 1
  • 1
Alex Lockwood
  • 83,063
  • 39
  • 206
  • 250
  • Yeah that's what I've done, but I was just wondering does my final answer look ok to you, because with a dfa, don't you need a transition for each label from every state? – AkshaiShah May 20 '12 at 17:01
  • Your second DFA is non-deterministic... what if you are at state `2` and get `c` as input? – Alex Lockwood May 20 '12 at 17:06
  • ok I see, so can I have a transition for c from state 2 going to a dump state? – AkshaiShah May 20 '12 at 17:08
  • You should add a `c`-transition from state `2` to some other state to ensure that the second DFA is deterministic. Which state you point the transition to depends on the desired behavior that you expect from your DFA. – Alex Lockwood May 20 '12 at 17:11
  • So could I create a new non-accepting state, and transition c to it? – AkshaiShah May 20 '12 at 17:12
  • Wait, sorry I didn't see the languages in your post. I have a question... by "every c is followed by a b", do you mean every "c" is followed by a "b", or followed by "ab" – Alex Lockwood May 20 '12 at 17:18
  • I mean every "c" is followed by a "b" – AkshaiShah May 20 '12 at 17:19
  • I think your DFAs are just wrong in general. You should probably start over because it doesn't look like the DFAs you made decide the two languages. For example, if you gave the first DFA the string `ac`, the DFA wouldn't know where to move when it sees the `c`, and a DFA by definition must follow some transition on each character it reads. Do you understand? – Alex Lockwood May 20 '12 at 17:25
  • Yeah ok I'll start again.. So would it have more than 3 states then? – AkshaiShah May 20 '12 at 17:28
  • You should have your DFA detect whenever there is a `c` that is not preceded by a `b`, and if it finds an occurrence it should go to a sink state that will always reject (because you know that it has an instance of `c` that is not preceded by a `b`). – Alex Lockwood May 20 '12 at 17:46
0

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.

Emil Vikström
  • 90,431
  • 16
  • 141
  • 175
  • Actually, I think the problem is that the second DFA is actually an NFA. If at state 2, the DFA will not know what to do when given `c` as input. – Alex Lockwood May 20 '12 at 17:08