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 regular languages: informal verbal descriptions, set
notation, finite automata, regular expressions, and regular grammars. Only the
last three are sufficiently well defined for use in theorems. We therefore say that
a regular language is given in a standard representation if and only if it is
described by a finite automaton, a regular expression, or a regular grammar.
Theorem 4.5
Given a standard representation of any regular language L on Σ and any w ∈ Σ*,
there exists an algorithm for determining whether or not w is in L.
Proof: We represent the language by some dfa, then test w to see if it is accepted
by this automaton.
Other important questions are whether a language is finite or infinite,
whether two languages are the same, and whether one language is a subset of
another. For regular languages at least, these questions are easily answered.
Theorem 4.6
There exists an algorithm for determining whether a regular language, given in
standard representation, is empty, finite, or infinite.
Proof: The answer is apparent if we represent the language as a transition graph
of a dfa. If there is a simple path from the initial vertex to any final vertex, then
the language is not empty.
To determine whether or not a language is infinite, find all the vertices that
are the base of some cycle. If any of these are on a path from an initial to a final
vertex, the language is infinite. Otherwise, it is finite.
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 regular languages: informal verbal descriptions, set
notation, finite automata, regular expressions, and regular grammars. Only the
last three are sufficiently well defined for use in theorems. We therefore say that
a regular language is given in a standard representation if and only if it is
described by a finite automaton, a regular expression, or a regular grammar.
Theorem 4.5
Given a standard representation of any regular language L on Σ and any w ∈ Σ*,
there exists an algorithm for determining whether or not w is in L.
Proof: We represent the language by some dfa, then test w to see if it is accepted
by this automaton.
Other important questions are whether a language is finite or infinite,
whether two languages are the same, and whether one language is a subset of
another. For regular languages at least, these questions are easily answered.
Theorem 4.6
There exists an algorithm for determining whether a regular language, given in
standard representation, is empty, finite, or infinite.
Proof: The answer is apparent if we represent the language as a transition graph
of a dfa. If there is a simple path from the initial vertex to any final vertex, then
the language is not empty.
To determine whether or not a language is infinite, find all the vertices that
are the base of some cycle. If any of these are on a path from an initial to a final
vertex, the language is infinite. Otherwise, it is finite.