# Algorithm to reduce string via rules?

This topic is 2211 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I forgot to mention that you need a rule-preprocessing step that turns every rule into the form "AB -> C". Read about Chomsky normal form to learn about it.

##### Share on other sites
OK, here it is:

#include <string>
#include <vector>
#include <iostream>

struct Rule {

Rule(char i1, char i2, char o)
: i1(1ul<<(i1-'A')),
i2(1ul<<(i2-'A')),
o(1ul<<(o-'A')) {
}
};

std::vector<Rule> rules = {
Rule{'A','A','A'},
Rule{'A','A','C'},
Rule{'C','A','B'},
Rule{'A','B','B'}
};

void parse(std::string s) {
int n = s.length();

for (int i=0; i<n; ++i)
conversions[i][i+1] = 1ul << (s[i]-'A');

for (int l=2; l<=n; ++l) {
for (int i=0; i<=n-l; ++i) {
int j = i+l;
conversions[i][j] = 0ul;
for (int k = i+1; k < j; ++k) {
for (Rule rule : rules) {
if ((rule.i1 & conversions[i][k])
&& (rule.i2 & conversions[k][j]))
conversions[i][j] |= rule.o;
}
}
}
}

for (mask m = conversions[0][n], i=0; m; i++, m >>= 1){
if (m & 1ul)
std::cout << char('A'+i) << ' ';
}
std::cout << '\n';
}

int main() {
parse("AAAB");
}

And now I have some babies to feed. ;)

EDIT: I found the name of the algorithm: CYK. Edited by Álvaro

• 11
• 13
• 9
• 12
• 15