CYK Algorithm

In the Automata theory and formal languages course, we have an algorithm that checks whether a string belongs to the grammar or not.

Input form

In the first line, enter the chosen string that we call w.
In the next line, enter the natural number as known as n. It explains to us the number of grammar production rules.
After all, in the next line(s), enter one of the grammar production rules.
The correct way to input:

Output form

If the string belongs to the grammar, print Yes, otherwise NO.

Rules

• We use '-' instead of epsilon
• It is guaranteed that the input grammar form is normal Chomsky
• It is guaranteed that 'S' is the initial symbol