patternMinor
Prove that every CFL is decidable in O(n) space
Viewed 0 times
cflspaceeverydecidableprovethat
Problem
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)$.
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)$.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#102059, answer score: 3
Revisions (0)
No revisions yet.