| << Prev | - Up - | Next >> |
We will now leave the topic of transducers and rewrite rules and come back to regular languages. This class of languages has a number of interesting properties, of which the following will concern us in this section:
- Closure properties
If we apply the operations of concatenation and Kleene closure, as well as the basic set theoretic operations of union, intersection and complementation to any (pair of) regular languages, the result will always be a regular language, too. We will discuss why this is so, and see how we can construct automata for the languages resulting from these operations based on the one(s) for the respective input language(s). In Section 3.3 we will implement some of these construction rules.
- Pumping Lemma
It can be proven that if a regular language contains any word exceding a minimum length, the language must also contain all words that are related to that word in a certain way. This result is interesting because it allows us to conclude that a language that does not have this property cannot be a regular language. We will make use of this kind of argument in the next chapter.
| << Prev | - Up - | Next >> |