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 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.