Help understanding infinity and applications to automaton theory

[Jarvis323]

Relevant Information
A language is a set of strings over an alphabet
A string is a finite set of characters from an alphabet
An alphabet is a finite non-empty set

A DFA is a deterministic finite state machine
A subset of it's states are accept states
A string is accepted by a DFA if the string leads to and ends on an accept state
A language accepted by a DFA if all strings in L, and only those strings are accepted by the DFA

I often have a hard time making sense of infinities.

Example: the language L = { e, 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| <= 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.

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 who's 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?

Also, is the mainstream concept of infinities considered to be the only valid school of thought? What fundamental axioms do our notions of infinities rely on?

 

[Stephen Tashi]

I'm sure people will tell you about the various sizes of Cardinal (and perhaps Ordinal) infinities. However, I think your question concerns the difference between the statements that such-and-such is "True for each finite integer N" vs "True for all integers" (i.e. True for the infinity of integers).

For example, for each integer N, there is an integer M such that M is larger than N. However there is no single integer M such that M is larger than all integers.

This has to do with the distinction between saying "For each thing x, there is a thing T(x)..." vs saying "There is a thing T, such that for each thing x ...". The first claim allows T(x) to depend upon x ("vary with it", so to speak) and the second claim does not.

 

[Jarvis323]

Can you comment on a rewording of the fundamental issue.

If no DFA can represent {e, ab, aabb, ... } then there cannot exist a finite series of cells such that for all natural numbers x, x's digits can fit in the cells, at most one digit for one cell.

So the issue I am having a hard time with is the idea that you need an infinite number of places to store an arbitrary finite number.

At least these are the logical consequences that seam to follow.

 

[Stephen Tashi]

So the issue I am having a hard time with is the idea that you need an infinite number of places to store an arbitrary finite number.

If you think you can store a arbitrary finite number of things in N cells, where N is a finite number, then what value do you have in mind for N? N = 100? N = 10,000 ? Can you set a value for N before someone tells you how many things need to be stored?

 

[Jarvis323]

I guess I am starting to feel better about it. I still cannot grasp it intuitively, but I do grasp the mathematical concepts. One day I would like to complete my understanding by working my way up through these concepts starting from a set of simple axioms.

 

[Stephen Tashi]

Very few people (none I have ever met) have a tidy of understanding of mathematics that begins with a few simple axioms and builds up to advanced subject matter. I would take too long to learn that. As a cultural activity, mathematics begins with simple axioms and builds up to complicated topics, but I don't know any single individuals who have replicated the work of an entire culture.

Understanding mathematics is complicated by the fact that even respectable mathematical texts often don't use precise language. You have to get used to mathematical "slang". For example, the common phrase "an infinite number" suggests that there is some number with the property that it is "infinite". In special contexts, people may introduce a symbol $\infty$ to the number system and define some operations for it. But in the typical context , to say something needs "an infinite number" of things only has the meaning that "no (finite) number" satisfies the requirement. If you say that a set of strings requires a machine with "an infinite number" of states to accept it then you might mean "There is no machine that has only a finite number of states and can accept this language" or you might actually be considering a hypothetical machine that has a state for every integer or a state for every real number etc.