Compute the CYK-Table!
A context-free grammar is a grammar consisting of rules from one variable to a list of variables and symbols. Every string purely consisting of symbols that can be produced using these rules is said to be accepted by the language. For the purpose of this challenge we're only going to consider grammars in CNF which means that on the right side there's either two variables or one symbol (we're gonna ignore the empty language for this challenge).
The CYK-Algorithm is a method to check whether a given word is recognized by a context-free language in CNF. For doing this it iterates over the word and applies all possible rules on all substrings and writes them down in a nice table. This table can then be used to successively find variables generating larger substrings until you (don't) hit the word.
Your input will be
- A list of strings representing the word
- A list of triples of strings, representing the rules from one variables (the first in the triple) to two variables
- A list of pairs of strings, representing the rules from one variable to a symbol
- A string, representing the starting variable
You may replace the above input format with your favorite input format, as long as you can encode the same amount of information.
The output will be three-dimensional: A list of rows consisting of a list of "candidates" which is a list of strings representing a list of variables. An illustration of this is on Wikipedia.
You may replace the above output format with your favorite output format, as long as you can encode the same amount of information.
This is code-golf so the shortest code in bytes to solve the challenge wins!
Start Symbol: "X"
Rules #1: [("X","X","Y"),("X","Z","Z"),("Y","W","Z"),("Z","X","Y"),("W","Y","W")]
Rules #2: [("X","a"),("Y","a"),("Z","b"),("W","c")]
We're gonna do this step-by-step:
The substrings of length 1 first (this is your first row):
b , a , c , b
Now for the substrings of length 2 (this is your second row):
(because there's no way to get
W -> YW and
Y -> WZ)
Now for the substrings of length 3 (this is your third row):
(because there's no rule to get
X->XY (1+2), Y->WZ (2+1), Z->XY (1+2) where the sum denotes the lengths of of the used substrings)
Finally for the substrings of length 4 (this is your fourth row):
So in total your final table for this example is gonna look like this:
where the first index increases as we go downwards, the second increases as we go to the right an dthe third denotes the variable within the "cell".