Language Definition and Structure

Every language is based on a vocabulary. Its elements are ordinarily called words; in the realm of formal languages, however, they are called281 (basic) symbols. It is characteristic of languages that some sequences of words are recognized as correct, well-formed sentences of the language and that others are said to be incorrect or ill-formed. What is it that determines whether a sequence of words is a correct sentence or not? It is the grammar, syntax, or structure of the language. In fact, we define the syntax as the set of rules or formulas which defines the set of (formally correct) sentences. More importantly, however, such a set of rules not only allows us to decide whether or not a given sequence of words is a sentence, but it also provides the sentences with a structure which is instrumental in the recognition of a sentence’s meaning. Hence, it is clear that syntax and semantics (= meaning) are intimately connected. The structural definitions are therefore always to be considered as auxiliary to a higher purpose. This, however, must not prevent us from initially studying structural aspects exclusively, ignoring the issues of meaning and interpretation.

Take, for example, the sentence, “Cats sleep.” The word “cats” is the subject and “sleep” is the predicate. This sentence belongs to the language that may, for instance, be defined by the following syntax.

A sentence is formed by a subject followed by a predicate.
A subject consists of either the single word “cats” or the word “dogs.” 3. A predicate consists of either the word “sleep” or the word “eat.”

The idea then is that a sentence may be derived from the start symbol <sentence» by repeated application of replacement rules.

The formalism or notation in which these rules are written is called Backus-Naur-Form (BNF). It was first used in the definition of ALGOL 60 [5-7]. The sentential constructs <sentence>, <subject>, and <predicate> are called non-terminal symbols; the words cats, dogs, sleep, and eat are called terminal symbols, and the rules are called productions. The symbols ::= and | are called meta-symbols of the BNF notation. If, for the sake of brevity, we use single capital letters for non-terminal symbols and lower case letters for terminal symbols, then the example can be rewritten as

and the language defined by this syntax consists of the four sentences xz, yz, XW, yw.

282

To be more precise, we present the following mathematical definitions:

The language L(T, N, P, S) is the set of sequences of terminal symbols € that can be generated from S according to rule 3 below.

(we use Greek letters to denote sequences of symbols.) T* denotes the set of all sequences of symbols from T.

A sequence a, can be generated from a sequence a, if and only if there exist sequences ¢,,02,...,0,-, such that every a, can be directly generated from o;_, according to rule 4 below:

A sequence y can be directly generated from a sequence € if and only if there exist sequences «, 8, €’, 7’ such that

Note: We use w@::= 8,|8,|...| 8, as a short form for the set of produc-

For instance, the sequence xz of Example | can be generated by the following sequence of direct generating steps: S — AB-—> xB — xz; hence S > xz, and since xz € 7*, xz is a sentence of the language, i.e., xz € L. Note that the non-terminal symbols A and B occur in non-terminating steps only, whereas the terminating step must lead to a sequence that contains terminal symbols only. The grammatical rules are called productions because they determine how new forms may be generated or produced.

A language is said to be context free if and only if it can be defined in terms of a context free production set. A set of productions is context free if and only if all its members have the form

i.e., if the left side consists of a single non-terminal symbol and can be replaced by € regardless of the context in which A occurs. If a production has the form

then it is said to be context sensitive because the replacement of A by & may283 take place only in the context of a and £. We shall subsequently restrict our attention to context free systems.

Example 2 shows how through recursion an infinity of sentences can be generated by a finite set of productions.