Answered: For the coding part you need to write…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

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.

#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++)
{

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;
}

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

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.

Similar questions