Other Decision Algorithms

Decision questions

Let’s consider the following questions for designing decision algorithms:

• Is one regular language a subset of another?
• Is the language of a given DFA empty?
• Is the language of a given DFA infinite?

To show that one regular language is a subset of another, say $X \subseteq Y$, it is sufficient to show that $X$ does not have any strings that $Y$ doesn’t, i.e., we show that $X-Y = \phi$. This answers the first question in the list above.

The second and third questions are easy to answer when given regular expressions. If the regular expression is not $\phi$, then at least one string matches the expression. If the regular expression has a Kleene star, then it describes an infinite language.

One way to determine whether a finite automaton accepts any strings at all is to see if there is a path from the start state to an accepting state. This is often easy to do by inspection, but as always, we seek an algorithm to answer the question; a machine with many states may not easily yield a solution by mere inspection.

To find such a path, we begin by “marking” the start state and then following the procedure below:

1. For every marked state, $s$:

   a. ...