This is a basic regular expression to DFA converter based on the coursework of theory of computation.Implemented *,+,Seq,OR as we weren't taught about (.,[],-,^,?) in that course.

Features

- It takes an input as expression and parse it.
- Then from the abstract syntax tree it makes NFA and from NFA.
- it is converted into DFA using the epsilon closure propery....
- Then moore minimization algorithm is used to minimize the DFA.
- An additional string check is used also(Whether the input belongs to the expression)
- worked with OR/UNION,STAR,SEQ/AND,PLUS and literals

Screenshots

- abstract syntax tree for a+b*(c+de)*f

- nfa and min dfa

- CYK simulation for the CFG
- S -> A B | B C
- A -> B A | a
- B -> C C | b
- C -> A B | a

Will try to implement

- CFG To CNF
- CFG to PDA
- CFG to LL(K)
- Left factoring and Left recursion elimination
- Computing first and follow sets

Usage

- To run the NFA-DFA-Regex tests   =  ./regex_test <regex> <input1> <input2> ...

- To run the CFG-CYK tests = ./cfg_draw <cfg_file> <string1> 

- To create images for dfa-nfa     = ./dfa_draw