How To - CYK Algorithm
In this quick post I try to explain the basics of the Cock-Younger-Kasami ( CYK ) Algorithm to you. This shouldn't take more than 15min for you to understand, since I am terrible at logic and math related studies - if I could do it so can you :D The CYK is a theoretical construct that can be used to find context free languages by feeding grammar and its production rules into a table and see wether a word from the language you wish to identify, matches up with these rules. To make this process run smooth, the production rules must be formatted in such way that it matches Chomsky Normal Form ( CNF ) standards; on the left hand side of a production rule stands a non-terminal symbol (a variable) on the right hand side of a production rule there can be maximal 2 non-terminals or 1 terminal symbol (a symbol that represents a constant value) but never non-terminals and terminals mixed For my course I worked through an example step by step, we started out with 3 production rules: A...