Skip to content

Latest commit

 

History

History
27 lines (21 loc) · 1.25 KB

README.md

File metadata and controls

27 lines (21 loc) · 1.25 KB

CFG checker

This is a python implementation of Context Ffree Grammar that cross references a given CFG with a given language. The program does not constitute a formal proof since there are infinite words in some CFGs, however it does give good indication of whether the language fits the grammar.

Usage instructions:

There is a usage example in the code

Construct a CFG

Fill in the fields of your CFG in the main function:

  • Variables (Single Characters)
  • Alphabet a.k.a Terminals (Single Characters)
  • The transition function (a dictionary with keys that are variables and values that are a combination of terminals and Variables
  • A starting variable Then construct your CFG.

Create a function for the Language that you wish to check against your CFG

The function should receive a word and return true if the word is in the language, otherwise false

Run the program

call the grammar_check function with the language and grammar that you created.

notes

You can choose up to what length of word you want to check with the parameter SEARCH_DEPTH. For instance if SEARCH_DEPTH is set to 12, the program will check all of the possible words of length of up to 12 that are in L (according to the function that describes the language, as described above).