Search code examples
finite-automatadfaformal-languages

Building a DFA that accepts a language with an union

I'm trying to figure out how to build a DFA that accepts the language enter image description here with alphabet ∑ = {a, b}. This is part of a homework problem set and I think I have a very basic idea of how to build simple DFA's but I can't wrap my head around the union symbol and more importantly what's the significance of the u?

Solution

  • u represents a string of any length (including 0) containing as and bs in any order. That's what the condition that u is an element of ∑* means.

    In the general case, you'd build a DFA by building an NFA whose start state has more than one out transition, and then doing ε-closure on the NFA. In this case, the two start transitions are mutually exclusive so you can just join the start states of the two DFAs.

    This is probably explained better in your textbook and/or lecture notes.