decidability of CFL membership
Given a context-free grammar G and a string w, can an algorithm always decide whether G generates w — does w belong to the language? Yes. This is the membership (or word) problem for context-free languages, and it is DECIDABLE: there is a procedure that always halts and answers YES or NO correctly, for every grammar and every input. Better still, it runs in polynomial time, so parsing programming languages and natural-language grammars rests on a solid algorithmic footing.
The standard method is the CYK algorithm (Cocke-Younger-Kasami). First convert G to Chomsky normal form, where every rule is either A -> B C (two variables) or A -> a (one terminal). Then fill a triangular table by dynamic programming. The bottom row records, for each single symbol of w, which variables can derive it. Each higher cell, covering a substring of w, records which variables can derive that substring by splitting it into two adjacent pieces and combining variables from cells below via the binary rules. After filling the table, w is in the language exactly when the START symbol appears in the top cell, which spans the whole string. For a string of length n this takes about O(n^3) time.
Why does this matter? It shows context-free grammars are genuinely usable: a compiler can decide whether your source code parses, and the answer is guaranteed. The contrast with the bad news to come is the whole drama of the field — membership is easy and decidable, yet other questions about the SAME grammars (are two grammars equivalent? is a grammar ambiguous?) turn out to be undecidable. Decidability is question-by-question, not a blanket property of the model.
To test whether aabb belongs to a grammar for { a^n b^n }, convert to CNF and run CYK on the length-4 string. The table is built bottom-up; if the start symbol reaches the top cell spanning all four letters, the answer is YES. The whole check is guaranteed to finish in roughly O(4^3) steps.
CYK fills an O(n^2)-cell table in O(n^3) time and always answers membership.
Decidable membership does NOT mean every question about CFGs is decidable — equivalence and ambiguity are undecidable. Decidability is per-problem; one good answer does not transfer to the others.