3
$\begingroup$

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)$.

$\endgroup$
  • 4
    $\begingroup$ Try converting the dynamic programming back to a recursion. $\endgroup$ – Yuval Filmus Dec 26 '18 at 14:15
3
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.