3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 30 '16 at 16:39
  • $\begingroup$ Incidentally, this can be done with a 1-state DFA. $\endgroup$ Dec 1 '16 at 16:53
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh that clears a lot of confusion up for me, thank you! $\endgroup$
    – Ray
    Nov 30 '16 at 20:28
2
$\begingroup$

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

source:https://math.stackexchange.com/questions/773683/decide-whether-dfa-accepts-all-strings

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.