0
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 9 '14 at 6:43

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 2
    $\begingroup$ DFA is a description of a language. Language is an infinite set of strings. It is perfectly natural that to describe infinitely many strings you should need an infinitely long description. Instead, the curious part is that sometimes you don't. $\endgroup$ – Karolis Juodelė Apr 9 '14 at 6:55
  • 1
    $\begingroup$ I suggest you check out our reference question for showing that a language is not regular. Note that finite automata can accept infinite languages! $\endgroup$ – Raphael Apr 9 '14 at 7:15
  • 4
    $\begingroup$ The question is essentially the same as "How is the set of natural numbers infinite when every individual natural number is finite?" It's perfectly possible to have an infinite set where each element is finite. $\endgroup$ – David Richerby Apr 9 '14 at 7:37
  • $\begingroup$ I couldn't clearly understand your question: Do you want to proof that "For a language like $0^n1^n \mid n >= 0$ DFA is not possible?" (yes we can proof that DFA not possible) OR you don't understand "why are languages like $0^n1^n$ not regular". If you have second doubt read answers here. $\endgroup$ – Grijesh Chauhan Apr 9 '14 at 8:02
3
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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 \}$.

$\endgroup$
  • $\begingroup$ @David No, but a variable containing an integer is "potentially infinite". $\endgroup$ – Yuval Filmus Apr 9 '14 at 18:59
  • $\begingroup$ @David Ok, you win. $\endgroup$ – Yuval Filmus Apr 9 '14 at 19:07

Your Answer

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