10

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.

10.1 LANGUAGES AND REGULAR EXPRESSIONS

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 O’Reilly online learning.

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