The CYK parsing algorithm entails an efficient algorithm to determine if a string w is accepted by a CNF grammar or not through bottom-up parsing and dynamic programming.

Implement CFG to CNF grammar conversion, and implement the CYK parsing algorithm.

In this section you are given 3 files. We will call them File1, File2, and File3. File1 contains specifications of a CFG, File2 contains specifications of a CNF grammar, and File3 contains a list of strings.

Implement a function named inCNF that takes one string argument, the filename of File1. Each line in File1 is a production rule. Print (to stdout) the given CFG in CNF, one production rule in each line.

Implement a function named algoCYK that takes two string arguments, the filename of File2 and the filename of File3 respectively. Each line in File2 is a production rule in CNF. Your function should determine if each string in File3 is accepted by the grammar specified in File2. For every string in File3, print (to stdout) the input string followed by a colon followed by a 1 if this string is accepted by the given grammar or a 0 otherwise.

Assumptions:

A non-terminal is an uppercase character from the English alphabet followed by 0 or more numeric digits.

A terminal is a lowercase character from the English alphabet.

S is designated as the start symbol.

* is designated as the empty string, as complicates the implementations.

To make things simpler, the production rules will not be in Bachus-Naur Form.

Left and right side of a production rule are separated by a space followed by -> followed by a space (4 characters in total). For the first part of the problem, your output should follow this format as well.

Each line of File3 is exactly one string (without the trailing newline at the end).

Do not insert any extra whitespaces in your outputs.

Problem #2 Example

File1

S -> *

S -> aSb

Output (Part 1)

S -> AB

S -> AC

C -> SB

A -> a

B -> b

File2

S -> AB

S -> AC

C -> SB

A -> a

B -> b

File3

aaa

ab

abb

aabb

Output (Part 2)

aaa:0

ab:1

abb:0

aabb:1