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*, *ab*^{2}, …} is a language over *A*. This consists of all words beginning with *a* and followed by zero or more *b*’s.

Let *L*_{1} and *L*_{2} be languages over an alphabet *A*. Then the concatenation of *L*_{1} and *L*_{2}, denoted by *L*_{1}*L*_{2}, is the language defined by

Start Free Trial

No credit card required