Constructing finite automata for a language

594 Views Asked by At

I've been given an assignment on constructing a deterministic finite automaton (DFA) for a language. I'd say it's a bit hard because it consists of a union, so I'm not really sure if my results are correct.

The language is: $$L =\{w\in\{a,b\}^*:|w|_b < 2\lor|w|_a\bmod 3=1\}$$ ($|w|_s$ means the count of symbol $s$ in $w$.) I decided to create a DFA for both parts of the language. So DFA for $|w|_b<2$ should look like this (3 states, if $|w|_b < 2$ it's accepted):

enter image description here

DFA for $|w|_a\bmod3=1$ should look like this (3 states as $|w|_a\bmod3$ can equal 0, 1 or 2 and only 1 is accepted):

enter image description here

Now the part I'm not sure about. I believe the union of those 2 DFA's (so $|w|_b < 2\lor|w|_a\bmod 3 = 1$) should look like this.

enter image description here

Could anyone confirm whether I merged the DFA's successfully or if I did some sort of mistake?

Edit: My new solution

enter image description here

2

There are 2 best solutions below

4
On BEST ANSWER

Your automaton accepts $abba$, which is not in $L$.

To construct a correct automaton you need nine states and edges between them corresponding to the Cartesian product of the state sets of the two component automata (which you have constructed correctly).

0
On

Well, its not correct since that the states 1 and 2 you cannot control the number of a's.

I'd use the canonical method to construct a DFA from an NDFA which you can immediately obtain from your two DFAs for the partial solutions.