Skip to content

Python program to convert a Context Free Grammar to Chomsky Normal Form.

License

Notifications You must be signed in to change notification settings

BaseMax/CFG2CNF

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

22 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CFG2CNF

Python tool able to convert a Context Free Grammar in Chomsky Normal Form

Convert a Context Free Grammar to Chomsky Normal Form

Python program to convert a Context Free Grammar to Chomsky Normal Form.

I read 7 chapters of the book and the result of my study was writing this program.

References: Formal Languages and Automata

Context Free Grammar Book

An Introduction to Formal Languages and Automata by Peter Linz

What is Chomsky Normal Form

Chomsky Normal Form is a context-free grammar that has been put into a specific format. It was developed by Noam Chomsky in 1978 and is part of formal language theory.

https://en.wikipedia.org/wiki/Chomsky_normal_form

What is Context Free Grammar

https://en.wikipedia.org/wiki/Context-free_grammar

Using

git clone https://github.com/BaseMax/CFG2CNF
cd CFG2CNF
python main.py

Input

S -> SaB | aB
B -> bB | $
*

The above grammar is equivalent to the following grammar:

S -> SaB
S -> aB
B -> bB
B -> $
*

Automata is useful?

The image below will change your think of the Automata:

Grammer sample image

Sure, We are need this subject all of the day, Also programming languages!

Follow this way by reading following book.

If you find a problem or bugs in program, please send Issue or PR, i'm a new member in this study...

Automata Videos

Learn in some videos:

Thanks to Khalilian for providing these videos and the great help he did.

Good for start to check Mini Calculator Interpreter project.


Max Base

My nickname is Max, Programming language developer, Full-stack programmer. I love computer scientists, researchers, and compilers. (Max Base)

Asrez Team

A team includes some programmer, developer, designer, researcher(s) especially Max Base.

Asrez Team

Releases

No releases published

Packages

No packages published

Languages