# How do you know if a language accepted by a DFA is $Σ^*$?

I know that a language that is input into a DFA (call it $X$) is regular just by being accepted by it, but given that it is accepted, how can one figure out that $L = Σ^*$? In other words, what does a DFA that accepts anything from $Σ^*$ even look like? When I learnt about DFAs, it was always under the context that $L(X)⊆ Σ^*$.

I get that this must be a DFA that accepts any input from $Σ^*$, but I have trouble wrapping my head around it. This is all of course assuming that $Σ$ is any finite set.

• Sounds like you need separate concepts between a language and a DFA. What you learned, is that you know how to define a DFA; and you also know a particular map from DFA to languages called "The language accepted by". What you need is learn how to define a language on its own. Nov 30, 2016 at 16:39
• Incidentally, this can be done with a 1-state DFA. Dec 1, 2016 at 16:53

You don't input a language to a DFA. Each time you run the machine, the input is just a string. The language accepted by the DFA is the set of inputs that cause it to end in an accepting state (called a final state by some authors). Therefore, the automaton accepts $\Sigma^*$ if every possible input leads to an accepting state.

So, to decide if an automaton accepts $\Sigma^*$, you need to check if every input does indeed lead to an accepting state.

• Oh that clears a lot of confusion up for me, thank you!
– Ray
Nov 30, 2016 at 20:28

if a language accepted by a DFA is Σ∗ then every state of dfa is accepting

if all states of a dfa are accepting then they are equivalent to each other so we can use the state minimisation algorithm to minimise the automata

if the minimised automata consist of just 1 state it either accepts every string or rejects every string