Determine if the string is in L(G)

[mathmari]

Hey!

I have to write an $O(n^3)$ algorithm to determine whether a given string $w=a_1 a_2 \dots a_n$ is in $L(G)$, where $G=(N,\Sigma ,P, S)$ is a context-free grammar in Chomsky normal form.

Could you give me some hints how to do that?? (Wondering)

 

[mathmari]

Could you explain me how we could use the dynamic programming in this case?? (Wondering)

 

[Evgeny.Makarov]

This is described in Section 3.6 in [1], Theorem 7.16 in [2] and Section 7.4.4 in [3]. Briefly, the idea is the following. Given a word $x_1\dots x_n$, for each $i$ and $s$ such that $1\le i\le i+s\le n$ find the set $N[i,i+s]$ of all symbols that can derive $x_i\dots x_{i+s}$. This computation occurs in a loop where $s$ changes from 1 to $n-1$.

[1] Lewis, Papadimitriou. Elements of the Theory of Computation. 2nd edition.

[2] Sipser. Introduction to the Theory of Computation. 2nd edition.

[3] Hopcroft, Motwani, Ullman. Introduction to Automata Theory, Languages, and Computation. 2nd edition.