Java Implementation of an algorithm for CFG in Chomsky form

Question

The goal is to convert pseudo code into actual working code. I thought I had it mostly figured out but there's something not quite right.

The Rule I'm using is

S -> RT|empty
T -> TR|a
R => TR|b

Here's the pseudo code:

D == "On input W == WI . ..Wn :
1. If W == e and S -> e is a rule, accept. [handle w == empty case]
2. For i == 1 to n: [examine each substring of length 1] 
3.     For each variable A:
4.         Test whether A -> b is a rule, where b == Wi. 
5.         If so,place A in table(i,i). 
6. For l == 2 to n:
7.     For i == 1 to n -l + 1:
8.         Let j == i + l - 1,
9.         For k == i to j -1:
10.            For each rule A \037 BC:
11.            If table(i,k)contains B and table(k + 1,j)contains
               C,put A in table(i,j).
12.If S is in table(l,n), accept.Otherwise, reject.

Here's the actual code:

public class algorithm {

public static void main(String[] args){
    String w = " abab";
    String table[][] = new String[w.length()][w.length()];
    if (w.isEmpty()){
        System.out.println("Accept\n");
    }

    for(int i=1; i<w.length();i++){
        if(w.charAt(i)=='a')
            table[i][i]="R";
        else if(w.charAt(i)=='b')
            table[i][i]="T";
    }
    for(int l=2; l<=w.length();l++){
        for(int i=1; i<w.length()-l+1;i++){
            int j = i+l-1;
            for(int k=i; k<=j-1;k++){
                if(table[i][k].contains("T") && table[k+1][j].contains("R"))
                    table[i][j]="T,R"; //Not sure how to do this part?
                else if(table[i][k].contains("R") && table[k+1][j].contains("T"))
                    table[i][j]="S";

            }
        }

    }
    System.out.println("Finished");
    System.out.println(w);
    for(int i=1;i<w.length();i++){
        for(int j=1;j<w.length();j++){
        System.out.print(table[i][j]+"\t");}
        System.out.println("");

    }
    //System.out.println((table[1][w.length()-1]));
    //if (table[1][w.length()-1].equals("S"))
    //  System.out.println("Accept");
}

}

I get:

 abab
   R    S   S   null    
   null T   T,R S   
   null null    R   S   
   null null    null    T

However as you can tell, baba CAN be derived from that grammar.

Answer 1

Figured out what I did wrong. First off I had <= rather than < Secondly I didn't initialize my array entirely so I would get null references at some points.