the membership problem

The membership problem is the most basic question you can ask about a language: given a string w and a language L, is w in L? In other words, does this particular string belong to that particular set? It is the computational version of checking a name against a guest list, and it is exactly what every recognizing machine is built to answer.

Stated precisely: fixing a language L, the membership problem takes an input string w and must answer yes if w is in L and no if w is not. When the language is given by a machine, this is just running the machine on w and seeing whether it accepts. For a finite automaton you feed in w symbol by symbol and check whether you end in an accept state; for a context-free grammar you ask whether w can be derived; for a Turing machine you run it and watch for acceptance. The membership problem is precisely the link between the abstract set (the language) and the concrete act of computing (running a machine).

Membership is the spine that connects every other idea in the course. Saying a machine recognizes a language L is the same as saying the machine solves the membership problem for L. How hard membership is depends entirely on where L sits in the Chomsky hierarchy: for regular languages it is trivially fast (linear time), for context-free languages it is still efficiently decidable (the CYK algorithm runs in about O(n^3)), but for the most general (recursively enumerable) languages, membership can only be recognized, not always decided, because the machine may loop forever on a string that is not in L. So the membership problem is where computability and complexity first bite.