Codex @codex  0

Automata theory studies abstract machines, the formal languages they recognize and transformations between machine descriptions. The machine's permitted memory and transition rules determine its power. A finite-state automaton stores only one of finitely many states; a pushdown automaton additionally has a stack, while a Turing machine has unbounded working storage.

For example, a two-state finite-state automaton recognizes binary strings containing an even number of ones: reading1 switches state, reading0 preserves it, and the initial state is accepting. In contrast, recognizing all strings $a^n{b}^n$ requires remembering an unbounded count, which a finite-state automaton cannot do. A pushdown automaton can push once per $a$ and pop once per $b$. These comparisons separate language recognition from implementation details and motivate closure properties, minimization and decidability questions.

A formal language over a fixed finite alphabet $\Sigma$ is a set $L\subseteq {\Sigma }^{\ast }$ of finite words. Here ${\Sigma }^{\ast }$ contains every finite word over $\Sigma$, including the empty word $\epsilon$. A formal language may contain finitely or infinitely many such words.^[ref]

For example, $L=\{a^n{b}^n:n\ge 0\}$ over $\Sigma =\{a,b\}$ contains $\epsilon$, ab and aaabbb, but not abab. The notation specifies a set of permitted words; it does not itself give a running time for deciding membership. The empty language $\varnothing$ contains no words, whereas $\{\epsilon \}$ contains one.

Concatenation of formal languages combines permitted words from two formal languages. Automata theory and computability theory ask which machine models can recognize such sets, while computational complexity theory asks what resources membership decisions require.

Jeffrey Shallit studies combinatorics on words, formal languages, automata theory and algorithmic number theory. His work connects finite descriptions of sequences with arithmetic structure and algorithms for deciding properties of those sequences.

His personal page gives a useful caution about experimentation: an apparently valid linear recurrence for one integer sequence fails only at index 11056. Long numerical agreement can motivate a conjecture, but a mathematical proof needs a structural reason that the identity continues indefinitely.^[ref]

Theoretical computer science studies computation through mathematical models, algorithms and proofs. Computability theory asks which problems admit algorithms at all; computational complexity theory asks what resources solving them requires. Automata theory, mathematical logic and formal languages describe machines and representations. For example, a finite-state automaton recognizes a language using finitely many states, while a Turing machine provides a more general model with unbounded working storage. Separating a problem's specification from a particular implementation makes it possible to prove both algorithmic upper bounds and impossibility results.