I. Properties of Language Classes

A language class is a set of languages.

Language classes have two important kinds of properties:

1. Decision properties ⇒ corresponds an algorithm that takes a formal description of a language (e.g., a DFA) and tells whether or not some property holds.
2. Closure properties ⇒ given languages in the class, an operation (e.g., union) produces another language in the same class

II. Decision Properties

1. The Membership Problem

Is string w in regular language L?

1. Assume L is represented by a DFA A.
2. Simulate the action of A on the sequence of input symbols forming w

2. The Emptiness Problem

Does the language contain any string at all?

1. Assume the DFA representation.
2. Compute the set of states reachable from the start state.
3. If at least one final state is reachable, then yes, else no.

3. The Infiniteness Problem

Is a given regular language infinite?