O'Reilly logo

Discrete Mathematics by Babu Ram

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

 

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required