4.3 IDENTIFYING NONREGULAR LANGUAGES
Regular languages can be infinite, as most of our examples have demonstrated. The fact that regular languages are associated with automata that have finite memory, however, imposes some limits on the structure of a regular language. Some narrow restrictions must be obeyed if regularity is to hold. Intuition tells us that a language is regular only if, in processing any string, the information that has to be remembered at any stage is strictly limited. This is true, but it has to be shown precisely to be used in any meaningful way. There are several ways in which this can be done.
Using the Pigeonhole Principle
The term “pigeonhole principle” is used by mathematicians to refer to the following simple observation. ...
Get An Introduction to Formal Languages and Automata, 7th 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.
