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