Alphabets and Languages

Hopcroft and Ullman begin their book with the question: What is a language? Their answer starts with a definition of an Alphabet. An Alphabet is any finite set of symbols. They consider only a countably infinite set from which all symbols will be drawn, and they leave open just what these symbols will be: ``any countable number of additional symbols that the reader finds convenient may be added.''

We adopt all the ingredients of this definition without needing to specify a countably infinite set. We simply require that an alphabet, , is a finite type; to say this we first declare Since is open, the definition is open. Then we require that be finite, postulating ). One consequence of finiteness is that the equality relation on is decidable. This is true of any finite set as we noted in section 2.

In Hopcroft and Ullman we read this:

A sentence over an Alphabet is any string of finite length composed of symbols from the abet. Synonyms for sentence are string and word.

This definition is incomplete because they do not define string. We have to learn later what it really means. The lack of a fixed definition allows the authors to switch between equivalent notions of list or array or string depending on their needs. We will note this later. Essentially they are introducing an abstract type without fixing the operations in advance.

They introduce these notations. If is an abet, then is the set of all sentences on . They include the empty sentence. is without . A language is any subset of . We use a concrete definition. A sentence for us is a list of elements from , that is, members of the type . The nil list is what we call the empty sentence. Example: if then

A language is given by some condition for membership, say a predicate that specifies when an element of belongs to the language. So a language is a propositional function over , namely an element of . We use Language() to denote the type of languages over Alph. In the library definitions are called abstractions and have a tag , as in:

languages Language()= =

We define equality of languages in Language() as .

In the library Lang_1 we give many operations on languages:

union
intersection
complement
product
power
closure

Hopcroft and Ullman raise these questions. How do we specify a language? Does there exist a finite representation for any language? They note that is countably infinite and hence Language() is uncountable. So they conclude that there are many more languages than finite representations.

Our views are consistent with these, but we allow other interpretations as well. We say that a language is given by a propositional function, say . (They say by a set but a set is not a finite representation.) One could consistently take the view that every function is given by an algorithm, and every algorithm is finitely representable. Hence all languages are finitely representable. This is the interpretation of so called recursive mathematics. All the work we present is consistent with this interpretation, as well, but as mentioned in the introduction we take the neutral view characteristic of ``Bishop style'' mathematics so all three views of the results are possible.