GrammarForge: CFG to GNF Converter and String Validator

A sophisticated tool for working with Context-Free Grammars (CFG) and Greibach Normal Form (GNF).

🚀 Features

• Converts any valid Context-Free Grammar (CFG) to Greibach Normal Form (GNF)
• Validates whether input strings are accepted by the grammar
• Provides step-by-step transformation process
• Efficient implementation in Rust for optimal performance

🛠️ Technical Details

This tool implements the following algorithmic steps:

1. Elimination of ε-productions
2. Removal of unit productions
3. Conversion to Chomsky Normal Form (CNF)
4. Final transformation to Greibach Normal Form (GNF)

📝 Prerequisites

• Rust compiler (rustc)
• Basic understanding of formal languages and grammars

⚡ Quick Start

# Compile the program
rustc grammar_forge.rs

# Run the executable
./grammar_forge

🔍 Usage Example

The program will guide you through:

1. Input your grammar rules
2. View the transformed GNF
3. Test strings against the grammar

💡 Note

This implementation is part of the Theory of Computation course assignment, demonstrating practical applications of formal language theory.