For the coding part you need to write down a Chomsky normal form context free grammar that will solve the balanced parentheses problem. For this problem you are provided with a cyk code, and you just need to modify the rules, n_rules, states, and input string. #include using namespace std; int s2i(string states, char state) { for(int i=0; i
For the coding part you need to write down a Chomsky normal form context free grammar that will solve the balanced parentheses problem. For this problem you are provided with a cyk code, and you just need to modify the rules, n_rules, states, and input string. #include using namespace std; int s2i(string states, char state) { for(int i=0; i
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter15: Recursion
Section: Chapter Questions
Problem 6PE
Related questions
Question
For the coding part you need to write down a Chomsky normal form context free
grammar that will solve the balanced parentheses problem.
For this problem you are provided with a cyk code, and you just need to modify the rules, n_rules,
states, and input string.
grammar that will solve the balanced parentheses problem.
For this problem you are provided with a cyk code, and you just need to modify the rules, n_rules,
states, and input string.
#include <iostream>
using namespace std;
int s2i(string states, char state)
{
for(int i=0; i<states.size(); i++)
if(states[i] == state)
return i;
return -1;
}
bool cyk(string input, char** rules, int n_rules, string states)
{
int loi=input.size();
int los=states.size();
bool*** table=new bool**[loi];
for(int i=0; i<loi; i++)
{
table[i]=new bool*[loi];
for(int j=0; j<loi; j++)
{
table[i][j]=new bool[los];
for(int k=0; k<los; k++)
table[i][j][k]=false;
}
}
for(int i=0; i<loi; i++)
for(int j=0; j<n_rules; j++)
if(rules[j][2]==input[i])
{
int state_id=s2i(states,rules[j][0]);
table[0][i][state_id]=true;
}
for(int i=1; i<loi; i++)
for(int j=0; j<(loi-i); j++)
for(int p=0; p<i; p++)
for(int k=0; k<n_rules; k++)
{
int state_id1=s2i(states,rules[k][0]);
int state_id2=s2i(states,rules[k][2]);
int state_id3=s2i(states,rules[k][3]);
if(state_id3==-1)
continue;
if(table[p][j][state_id2] and table[i-p-1][j+p+1][state_id3])
table[i][j][state_id1]=true;
}
for(int i=0; i<loi; i++)
{
cout<<"length "<<i<<":"<<endl;
for(int j=0; j<loi; j++)
{
cout<<"start "<<j<<":";
for(int k=0; k<los; k++)
{
using namespace std;
int s2i(string states, char state)
{
for(int i=0; i<states.size(); i++)
if(states[i] == state)
return i;
return -1;
}
bool cyk(string input, char** rules, int n_rules, string states)
{
int loi=input.size();
int los=states.size();
bool*** table=new bool**[loi];
for(int i=0; i<loi; i++)
{
table[i]=new bool*[loi];
for(int j=0; j<loi; j++)
{
table[i][j]=new bool[los];
for(int k=0; k<los; k++)
table[i][j][k]=false;
}
}
for(int i=0; i<loi; i++)
for(int j=0; j<n_rules; j++)
if(rules[j][2]==input[i])
{
int state_id=s2i(states,rules[j][0]);
table[0][i][state_id]=true;
}
for(int i=1; i<loi; i++)
for(int j=0; j<(loi-i); j++)
for(int p=0; p<i; p++)
for(int k=0; k<n_rules; k++)
{
int state_id1=s2i(states,rules[k][0]);
int state_id2=s2i(states,rules[k][2]);
int state_id3=s2i(states,rules[k][3]);
if(state_id3==-1)
continue;
if(table[p][j][state_id2] and table[i-p-1][j+p+1][state_id3])
table[i][j][state_id1]=true;
}
for(int i=0; i<loi; i++)
{
cout<<"length "<<i<<":"<<endl;
for(int j=0; j<loi; j++)
{
cout<<"start "<<j<<":";
for(int k=0; k<los; k++)
{
if(table[i][j][k])
cout<<states[k]<<',';
}
cout<<" ";
}
cout<<endl;
}
if(table[loi-1][0][0])
return true;
else
return false;
}
int main()
{
string input = "ababa";
char* rules[7]={"S=AB","A=BC","A=a ","B=AC","B=b ","C=a ","C=b "};
int n_rules=7;
string states="SABC";
cout<<cyk(input,rules,n_rules,states);
return 0;
}
cout<<states[k]<<',';
}
cout<<" ";
}
cout<<endl;
}
if(table[loi-1][0][0])
return true;
else
return false;
}
int main()
{
string input = "ababa";
char* rules[7]={"S=AB","A=BC","A=a ","B=AC","B=b ","C=a ","C=b "};
int n_rules=7;
string states="SABC";
cout<<cyk(input,rules,n_rules,states);
return 0;
}
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning