Course contentsShow
← Computer Science
Lesson 1811 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Decision Properties of Regular Languages

Emptiness, finiteness, and membership are decidable for regular languages via DFA algorithms.

Decision Properties of Regular Languages

You'll learn: How to algorithmically determine whether a regular language is empty, finite, or contains a specific string.

What Are Decision Properties?

A decision property is a yes/no question about a language that can be answered algorithmically. For regular languages, three fundamental questions are decidable (always answerable):

  1. Emptiness: Does the language contain any strings at all?
  2. Finiteness: Does the language contain infinitely many strings?
  3. Membership: Is a specific string w in the language?

Because every regular language has a DFA, we can answer these questions by analyzing the DFA's structure.

How the Algorithms Work

Emptiness: Run a graph search (BFS or DFS) from the start state. If any accepting state is reachable, the language is non-empty. Otherwise, it's empty. Think of it like checking if there's a path to treasure in a maze.

Finiteness: A DFA accepts infinitely many strings if and only if there's a cycle (loop) on some path from the start state to an accepting state. Use cycle detection on the reachable portion of the graph. If you can loop back while still reaching acceptance, you can "pump" strings infinitely.

Membership: Simulate the DFA on input string w. Start at the initial state and follow transitions for each symbol. Accept if you end in an accepting state after reading all of w. This is the basic DFA computation you've already seen.

All three algorithms run in polynomial time relative to the DFA size and input length.

Why This Matters

Decidability means these properties are computable—you can write programs that always halt with correct answers. This isn't true for all language classes (spoiler: context-free and recursively enumerable languages have undecidable properties).

Key Takeaway: Emptiness, finiteness, and membership are decidable for regular languages using efficient DFA-based algorithms: reachability for emptiness, cycle detection for finiteness, and direct simulation for membership.