HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dfaknowyouacceptedlanguagehow

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#66706, answer score: 5

Revisions (0)

No revisions yet.