, .
, ...
(I) n, 2d- (A) dim nxn.
A [i, j] G, (i, j).
, A [1, n] (S), , S, .
def decide (string s,grammar G):
//base case
for i=1 to n:
N[i,i]=I[i] //as the substring of length one can be generated by only a
terminal.
//end base case
//induction
for s=1 to n: //length of substring
for i=1 to n-s-1: //start index of substring
for j=i to i+s-1: //something else
if there exists a rule A->BC such that B belongs to N[i,j] and C
belongs to N[j+1,i+s-1] then add A to N[i,i+s-1]
//endInduction
if S belongs to N[1,n] then accept else reject.
I know that indexes seem pretty crazy. But basically what is happening here.
- The base case is pretty clear. I think
- at the inductive stage, we construct a solution for a substring of length s from all solutions with a length less than s.
- you find a solution for a substring of length 5 ( sub), starting at index 1. Then you start a loop (something else part) ..... that checks if a rule exists (A-> BC), so B and C displays two adjacent and disjoint substrings sub and, if so, add all such A to N [1,6].
-Finally, if you have a start symbol in N [1, n], you accept!