CYK Parser and String Generator

This repository contains a Python program designed to work with context-free grammars (CFGs) in Chomsky Normal Form (CNF). The program offers two primary functionalities: generating random strings from a given CFG and using the CYK (Cocke-Younger-Kasami) algorithm to check if a given string can be generated by the specified CFG.

Features

1. CYK Parsing: Determine if a given string can be generated by the CFG using the CYK algorithm.
2. Random String Generation: Recursively generate a random string from the CFG.

Dependencies

• Python 3.x
• Pandas

Installation

Clone the repository to your local machine:

git clone https://github.com/your-username/cyk-parser-string-generator.git

Ensure you have Python and Pandas installed. If not, install Pandas using pip:

pip install pandas

Usage

Run the program from the command line:

python CYK_Parser.py

Follow the interactive prompts to input the grammar in CNF and choose the operation (CYK Parsing or String Generation):

Input Grammar Example (Bracket Grammar)

S → SS | AC | AB
C → SB
A → (
B → )

Interactive Input Example

Enter an input of form S or type 'end' to stop: S
Enter an input of form AB or a single terminal: SS
Enter an input of form S or type 'end' to stop: S
Enter an input of form AB or a single terminal: AC
Enter an input of form S or type 'end' to stop: S
Enter an input of form AB or a single terminal: AB
Enter an input of form S or type 'end' to stop: C
Enter an input of form AB or a single terminal: SB
Enter an input of form S or type 'end' to stop: A
Enter an input of form AB or a single terminal: (
Enter an input of form S or type 'end' to stop: B
Enter an input of form AB or a single terminal: )
Enter an input of form S or type 'end' to stop: end

CYK Example

Enter 1 for CYK, 2 for String Generation, and 0 to exit: 1
Enter a string: (())()()
     0    1    2    3    4    5    6    7
0  {A}    0    0  {S}    0  {S}    0  {S}
1    0  {A}  {S}  {C}    0    0    0    0
2    0    0  {B}    0    0    0    0    0
3    0    0    0  {B}    0    0    0    0
4    0    0    0    0  {A}  {S}    0  {S}
5    0    0    0    0    0  {B}    0    0
6    0    0    0    0    0    0  {A}  {S}
7    0    0    0    0    0    0    0  {B}
The string (())()() is in the grammar.

String Generation Example

Enter 1 for CYK, 2 for String Generation, and 0 to exit: 2
This string is generated by the grammar:  ()()((((())())(())(()()())))