Project Proposal: String Generator from CFG Using Derivation Method in C
1. Project Overview
• Project Title: String Generator from CFG and Regular Expressions Using Derivation
Method in C
• Course: Theory of Automata (EE-3009)
• Instructor: [Bakthawar abbasi]
2. Group Members
• Group Member 1: [Arfeen, 23K-0808]
• Group Member 2: [Muneeb Ul Haq, 23K-0578]
3. Project Description
This project aims to build a program that takes Context-Free Grammars (CFGs) or Regular
Expressions (Regex) as input and generates valid strings accepted by them. For CFGs,
derivation rules will be applied recursively to create strings, while for Regex, an NFA will be
constructed and simulated. The program will allow users to specify the depth or maximum
length of generated strings, making it a helpful tool in understanding language generation in
formal systems.
Objectives
• Objective 1: Develop a recursive derivation system to generate strings from CFGs.
• Objective 2: Implement the project entirely in C for deeper understanding of algorithm
and memory management.
Scope of the Project
• Concepts Covered: Context-Free Grammars (CFGs), Derivations, Epsilon Transitions,
Recursive Descent Parsing.
• Expected Outcomes: A functional C program capable of parsing CFGs and generating valid
strings using formal derivation.
Functional Features
• Feature 1: Parse user-defined CFGs and handle multiple production rules per non-
terminal.
• Feature 2: Recursively derive strings using depth-bound derivation from CFGs.
4. Methodology
The program will be developed from scratch using C. CFG rules will be parsed and stored in
structured formats. For each non-terminal, its production possibilities will be generated and
applied recursively to simulate derivation.
Tools and Technologies Used
• C Programming Language
• GCC Compiler
• Standard C Libraries (stdio.h, stdlib.h, string.h)
5. Team Contributions
Group Member 1:
• Design of CFG structure, recursive derivation algorithm, and null production handling.
Group Member 2:
• Testing with sample CFGs, documentation, and debugging.
6. Challenges and Risks
Possible difficulties include complex recursion for CFGs, handling nullable variables, and
ensuring no infinite loops during derivation. These will be mitigated by limiting derivation
depth.
7. References
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, "Introduction to Automata Theory,
Languages, and Computation"
• Online resources: GeeksforGeeks, Stack Overflow, C programming tutorials
8. Conclusion
This project will provide a practical application of automata theory by converting abstract
grammar definitions into real outputs. It enhances understanding of derivations and
recursive algorithms. In the future, the project can be extended to support PFA,PDA and
Turing Machine-based generation as well.
