A French-language dictionary can be viewed as a finite set of words made up of letters (uppercase, lowercase and accented). The instructions in a programming language are specified in its user manual and are finite in number. By contrast, a computer program can potentially handle infinitely many variable or function names. Genetic sequences are words (often very long ones) made up of characters from the set {A, C, G, T}, representing the four nucleotides. What all these fields have in common is the notion of language.
The alphabet: the basics
-----------------------
To write words, we need an alphabet (a finite set of characters). A word is a finite sequence of characters from a given alphabet. For example, using the alphabet {a, b, c}, we can form the words bbca, aaa, bcbcbc, acbc…
An (abstract) language L over an alphabet A is simply a set (finite or infinite) of words made up of characters from A. For example, we can work with the (infinite) language of all words over the alphabet {a, b} containing an odd number of a's: {a, aaa, aaaaa… ba, ab, abaa, baaa, babbaa…}. This abstract definition captures the features of the computing, biological and linguistic contexts mentioned above, as well as many others.
To process a language L automatically, we need a mechanism that takes a word as input and "says" whether or not it belongs to L. Deterministic finite automata (DFAs) were designed for precisely this purpose! Such an object M is defined by several components. First, an alphabet A. Next, a finite set of states, Q = {q0, q1… *qk}. Within this set, q*0 is singled out as the initial state of M. It is the "gateway" into M. A subset F of Q is also singled out; its elements are the accepting states of M. A word w = x1 x2… *xn to be processed by M is initially written on M's tape (its read-only input memory). Each character xi of w occupies one cell of the tape. At the outset, the automaton's read head points to the first character, x*1, of w.
