Skip to content

A program that cross references a context free grammar with a given language

Notifications You must be signed in to change notification settings

mattany/CFGChecker

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

18 Commits
 
 
 
 

Repository files navigation

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).

About

A program that cross references a context free grammar with a given language

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages