4.2 ELEMENTARY QUESTIONS ABOUT REGULAR LANGUAGES
We now come to a very fundamental issue: Given a language L and a string w, can we determine whether or not w is an element of L? This is the membership question, and a method for answering it is called a membership algorithm.* Very little can be done with languages for which we cannot find efficient membership algorithms. The question of the existence and nature of membership algorithms will be of great concern in later discussions; it is an issue that is often difficult. For regular languages, though, it is an easy matter.
We first consider what exactly we mean when we say “given a language….” In many arguments, it is important that this be unambiguous. We have used several ways of describing ...
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.
