Kleeneliness is next to Gödeliness
The programming languages we use are not actually CFs, curiously, since we describe their syntax by means of CFGs. While this remains true, they are not strictly CFs because a CFG is not enough to describe them; we must also specify contextual constraints. This is what we do when we specify constraints on function declarations before they can be called (considerably simplifying: the number, type, and order of parameters), operator precedence, rules for variable names, and so on.
Properties of CF languages
- They are closed with respect to:
- Union
- Concatenation
- Kleene closure
- They are not closed with respect to the operations of:
- Intersection
- Complementation
For CF languages, the membership problem is decidable. Specifically, for any CF language $L$, there exists a CFG $G$ in Greibach Normal Form that generates it. If a string $u$ is generated by $G$, it can be derived in exactly $\vert u \vert$ steps.
Therefore, to determine if $u$ belongs to $L$, one only needs to check all possible derivations of length $\vert u \vert$.
The above algorithm has exponential complexity, although more efficient algorithms of complexity $O(\vert u \vert^3)$ and $O(\vert u \vert^{2.8})$ exist.
The value of these algorithms is theoretical in that parsing in practice is performed for particular classes of grammars for which it is feasible in a more efficient manner (for regular languages, the time is linear).