/sci/ - Science & Math

>>14860124
okay, so think of it this way: you have the string and you know the DFA rejects it
problem: the string is long
however, you know this means that the string must be causing the automation to return to a previous state
so just split the string, remove the substring 'detour' that caused transition to all of the states seen in between visits to the previously visited state
keep doing this until there are no transitions to previous states
by construction the string never causes the automaton to visit a previously visited state, and one state must be the reject state, so the length of the string is strictly less than the number of states
note that in this case arbitrarily long strings will be rejected, but nevertheless there is at least one string with a number of symbols less than the number of DFA states
check out the pumping lemma
pic related is where I learned about it
https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
one line proof: 'unpump' the long string to get a string with the desired property