Languages and Grammars

The formal languages discussed in this chapter are used to model natural languages and to communicate with computers. These languages are completely determined by specified rules.


Definition 10.1

Let A be a finite set of symbols. A (formal) language L over A is a subset of A*, the set of all strings over A.

For example, let A {a, b}. Then the set L of all strings over A containing an odd number of a’s is a language over A.

Similarly, {a, ab, ab2, …} is a language over A. This consists of all words beginning with a and followed by zero or more b’s.

Let L1 and L2 be languages over an alphabet A. Then the concatenation of L1 and L2, denoted by L1L2, is the language defined by


Get Discrete Mathematics now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.