Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language

Question

I have always had a hard time making sense of infinities.

Example: the language $L = \{ \epsilon , 01, 0011, 000111, 00001111, ... \}$ is not DFA acceptable because a machine capable of accepting it would require an infinite amount of states.

I can draw a DFA with ellipses in the middle to represent it's expansion. I can prove that:

For all strings x in L, using a machine M = mentioned DFA, under some finite expansion, I can accept all strings y in L, such that $|y| \leq |x|$ and such that M has $|x| + 2$ states and such that all strings in compliment(L) are not accepted by M.

All of those machines are finite.

The problem that prevents me from making the leap to claim that L is then DFA acceptable, is that I need to prove that there exists a largest string in L, but there is no largest string in L.

Anyways, I know this sounds stupid because knowing what is proven about convergence and divergence, I should be able to make mathematical sense of this. The problem is that no matter how much I know about infinity, I still do not think that what is said about convergence and divergence seems logical. I always have this feeling that something is wrong.

So I guess I just wonder how I can look at it so that it makes more sense.

In short, when a DFA needs a state for each character of a string in order to accept the string, and the language is an infinite set of strings whose enumeration could be represented as a sequence of strings increasing in length, how is it that a DFA needs an infinite amount of states to accept all of those strings, given each string is finite?

Answer 1

Look at your general procedure: given a language $L$ and integer $n$ build a DFA that properly recognizes any string $x \in L$ with $|x| \leq n$. Note that the language you selected is not special, any language can be represented by a sequences of DFAs with one for each $n$. To see this, just build a tree DFA with $|\Sigma|^{n + 1}$ states with a state for every possible string of length $\leq n$ marking the ones in $L$ as accept states and the ones not in $L$ as reject states and then minimizing. (If you want an even simpler example, then note than for any $L = \cup_{x \in L} \{x\}$ and every $\{x\}$ is recognized by a DFA with $|x| + 1$ states)

The whole point of DFAs is that it is a finite object that recognizes an infinite object. In fact, this is the whole point of computer science in general: Turing Machines are a different kind of finite object that recognizes (or encode) a different (larger) set of infinite objects. This means that for a language to be recognized, you need a single machine that works for all strings in that language.

What you have shown is that $L_n = L \cap \Sigma^{ \leq n}$ is recognized by a DFA, but these are just finite languages and every finite language is recognized by some DFA. However, regular languages are not closed under infinite union (in fact, very few things of interest to computer scientists are closed under arbitrary infinite unions), so the simple fact that $L = \cup_{n = 1}^{\infty} L_n$ does not imply anything about $L$.

Answer 2

You are confusing potential infinity and actual infinity. An "arbitrary" natural number (that is, a variable storing a natural number) is unbounded, since while being finite, it could be arbitrarily large. The set of natural numbers itself is infinite.

As another example, consider the set of prime numbers. Each prime number is finite and you can just write it down, but can you give me a list of all prime numbers? The description $\{2,3,5,7,11,13,17,19,23,\ldots\}$ isn't good enough for me, since I don't know what the dots signify. In need a rule that tells me when a number is prime or not.

Regular languages are the same: they specify a rule of a special kind that tells you what binary strings are in the language. If you don't like binary strings, you can always think of them as numbers: given any positive integer, take its binary notation and remove the leading 1. Using this encoding, the set of prime numbers is $$ \{ 0, 1, 01, 11, 011, 101, 111, 0111, \ldots \} $$ Can you see the pattern? The pattern is apparent from the meaning of the strings, once I point out that all the numbers encoded by these strings are prime. But this description is complicated – a child might not be able to follow it. But a child could understand "a string with two $0$s". You can think of a DFA as instructions for a child. The instructions have to be very simple, so simple indeed that they aren't fancy enough even to describe the set $\{ 0^n 1^n : n \geq 0 \}$.