13,086,265 members (65,197 online)
Rate this:
See more:
hi, can anyone help me to give me an example of its output program ... its Cyk Algorithm Implementation ... i'll be thankful very much to help me to understand its code ...

many thanks

~lida

```#include "stdafx.h"
#include <Windows.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cassert>
#include<iomanip>
using namespace std;

#define MAX 100
#define for(i,a,b) for(i=a;i<b;i++)
#define ASSERTMSG(TST,MSG) ((TST) ? (void)0 : (cerr<<MSG<<endl,abort()))

string arr[MAX][MAX]; // to store entered grammar
string dpr[MAX];
int p,np; // np -> number of productions

inline string concat(string a, string b)//concatenates unique non-terminals
{
int i;
string r=a;
for(i,0,b.length())
if(r.find(b[i]) > r.length())
r += b[i];
return (r);

}

inline void deconc(string a)//seprates right hand side of entered grammar
{
int i;
p=0;

while(a.length())
{
i = a.find("|");
if ( i > a.length())
{
dpr[p++] = a;
a=" ";

}
else
{
dpr[p++] = a.substr(0,i);
a = a.substr(i+1,a.length());

}

}

}

inline int lchomsky (string a) //checks if LHS of entered grammar is in CNF
{
if(a.length() == 1 && a[0] >= 'A' && a[0] <= 'Z')
return 1;
return 0;

}

inline int rchomsky (string a)//checks if RHS of grammar is in CNF
{
if( a.length() == 1 && a[0] >= 'a' && a[0] <= 'z')
return 1;
if ( a.length() == 2 && a[0] >= 'A' && a[0] <= 'Z' && a[1] >= 'A' && a[1] <= 'Z')
return 1;
return 0;
}

inline string search_prod(string p)//returns a concatenated string of variables which can produce string p
{
int j,k;
string r= " ";
for(j,0,np)
{
k=1;
while(arr[j][k] != " ")
{
if (arr[j][k] == p)
{
r= concat(r,arr[j][0]);

}
k++;
}

}
return r;
}

inline string gen_comb(string a, string b)//creates every combination of variables from a and b . For eg: BA * AB =
{
int i,j;
string pri=a,re=" ";
for(i,0,a.length())
for(j,0,b.length())
{
pri = " ";
pri = pri + a[i] + b[j];

re = re + search_prod(pri);//searches if the generated productions can be created or not

}
return re;

}

int main()
{
int i,pt,j,l,k;
string a,str,r,pr,start;

cout<<"\n*************************CYK ALGORITHM Implementation**************************\n";
cout<<"\nEnter the set of start variables ";
cin>>start;
cout<<"\nEnter number of productions ";
cin>> np;

for(i,0,np)
{
cin>>a;
pt = a.find( " -> ");
arr[i][0] = a.substr(0,pt);

ASSERTMSG(lchomsky(dpr[j]),"\nGrammar not in Chomsky Form");

a = a.substr(pt+2 , a.length());
deconc(a);

for(j,0,p)
{
arr[i][j+1]=dpr[j];
ASSERTMSG(rchomsky(dpr[j]),"\nnGrammar not in Chomsky Form");

}

}
string matrix[MAX][MAX],st;
cout<<"\nEnter string to be checked : ";
cin>>str;

for(i,0,str.length())
{
r = " ";
st = " ";
st += str[i];

for(j,0,np)
{
k = 1;
while(arr[j][k] != " ")
{
if(arr[j][k] == st)
{
r=concat(r,arr[j][0]);

}
k++;

}

}

matrix[i][i] = r;

}

int ii,kk;
for( k , 1 , str.length())
{
for(j,k,str.length())
{
r = " ";
for (l,j-k,j)
{
pr = gen_comb(matrix[j-k][l],matrix[l+1][j]);
r = concat(r,pr);

}
matrix[j-k][j] = r;

}

}

cout<< " \nMatrix Generated :- " << endl;

for(i,0,str.length())
{
for(j,0,str.length())
cout<< setw(5) << matrix[i][j] << " ";

cout << endl;

}

int f=0;
for(i,0,start.length())
if( matrix[0][str.length()-1].find(start[i]) <= matrix[0][str.length()-1].length())
{
cout << "String can be generated\n";
return 0;

}

cout << "String cannot be generated\n";
return 0;
}```
Posted 5-Jan-13 7:03am
Sandeep Mewara 5-Jan-13 13:38pm

Did you try by yourself? If yes, what was the result?
lida zar 5-Jan-13 14:10pm

yes the result its that

Enter the set of start variables ab
Enter number of productions 3

and after it anything i type given error...

What exactly? Describe your problem in sufficient detail.
—SA

Rate this:

## Solution 1

Little hint did you have a subject called Theoretical Computer Science or(TCS),your code is checking whether ur entered string is in Chomsky Normal form (CNF) or not and does further processing on it depending on the outcome...

Top Experts
Last 24hrsThis month
 Graeme_Grant 205 Jochen Arndt 145 Karthik Bangalore 130 RyanDev 80 Kornfeld Eliyahu Peter 80
 OriginalGriff 3,095 Graeme_Grant 1,519 ProgramFOX 1,367 ppolymorphe 1,217 Jochen Arndt 1,205