# Prove that every CFL is decidable in O(n) space

this question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was:

Prove that every context free language $$A$$ is in $$\mathrm{SPACE}(n)$$. You can assume that $$A$$ is given in CNF (Chomsky Normal Form)

I saw CYK algorithm but it's space complexity is $$O(n^2)$$.

• Try converting the dynamic programming back to a recursion. – Yuval Filmus Dec 26 '18 at 14:15

Let $$G$$ be a context-free grammar in Chomsky normal form. We will show how to determine whether a nonempty word $$w$$ of length $$n$$ is accepted by $$G$$.
Every parse tree for $$w$$ is first of all a full binary tree with $$n$$ leaves. It is known that the number of such trees is $$C_{n-1}$$. Moreover, there is a bijection with words containing $$n-1$$ pairs of balanced parentheses and full binary trees with $$n$$ leaves. We can go over all full binary trees with $$n$$ leaves in space $$O(n)$$ by going over all words of length $$2(n-1)$$ over the alphabet $$\{(,)\}$$, converting each of them which is balanced to a full binary tree.
For each full binary tree $$T$$, we consider all possible labelings of nonterminals to the vertices of the tree in which the root is labeled using the start symbol, which can be done in $$O(n)$$ space (here the constant depends on $$G$$). We check each such parse tree for validity: for each internal vertex labeled $$A$$ with children labeled $$B,C$$, we check that $$A \to BC$$ is a production, and for the $$i$$'th leaf labeled with $$A_i$$, we check that $$A_i \to w_i$$ is a production. If we find a valid parse tree in this process, then $$w \in L(G)$$. Otherwise, $$w \notin L(G)$$.