CHAPTER 4

PROPERTIES OF REGULAR LANGUAGES

CHAPTER SUMMARY

We now look at what properties all regular languages have, what happens when regular languages are combined (for example, when we form the union or intersection of two regular languages), and how we can tell whether a language is or is not regular. The so-called pumping lemma allows us to show that there are still simple, but not regular, languages. This will establish the need for studying more complicated language classes.

We have defined regular languages, studied some ways in which they can be represented, and have seen a few examples of their usefulness. We now raise the question of how general regular languages are. Could it be that every formal language is regular? Perhaps any ...

Get An Introduction to Formal Languages and Automata, 6th Edition now with O’Reilly online learning.

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