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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
