snippetMinor
How do you know if a language accepted by a DFA is $Σ^*$?
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.
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.
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.