Tuesday, July 24, 2018

Program to convert an NFA to DFA

The NFA is given as text file in a specific format to make parsing easy.The corresponding DFA is written to an output text file.
Click THIS to go the GitHub program.

Algorithm

nfa.txt
//states
q0 q1 q2
//input_symbols
0 1
//start_state
q0
//final_state
q2
//transitions of the form : intial_state  input  final_state
q0 0 q2
q1 1 q0,q2
q2 0 q0,q1
q2 1 q0


output.txt
Start states:{q0}

({q0},0) = q2
({q2},0) = q0 q1
({q0,q1},0) = q2
({q0,q1},1) = q0 q2
({q0,q2},0) = q0 q1 q2
({q0,q1,q2},0) = q0 q1 q2
({q0,q1,q2},1) = q0 q2
({q0,q2},1) = q0
({q2},1) = q0
({q0},1) =

States : {q0} {q2} {q0,q1} {q0,q2} {q0,q1,q2}

Final States : {q2} {q0,q2} {q0,q1,q2}

NOTE : The states of the NFA can be represented as numbers only. Alphabets won't work.

program.c


Tuesday, July 17, 2018

Program to convert an epsilon-NFA to NFA

This program takes an epsilon-NFA and converts it to an NFA without espilon transitions. The output is written to a file named "output.txt". The input text file musn't contain any unecessary whitespace/space character. Otherwise it may result in segmentation fault. Also the text files behave differently in Linux and Windows. Line ending is the one I'm talking about. In the output BLANK means phi(Φ).
Click  NEELAN to go to the program.

nfa.txt

//states
q0 q1 q2
//input_symbols
0 1
//start_state
q0
//final_state
q2
//transitions of the form : intial_state  input  final_state
q0 0 q0
q0 e q1
q1 1 q1
q1 e q2
q2 2 q2

output.txt

Final states:q1 q2 q0
(q0,1) =  q3,q4,
(q1,1) =  q3,
(q2,1) =  q4,
(q3,1) =  q1,
(q4,1) =  q6,
(q5,1) =
(q6,1) =  q2,q5,

program.c


Over 'https' the program won't be viewable. Please use 'http' or the GitHub link above.

Tuesday, July 10, 2018

Program to find the Epsilon closure of all states of an NFA

This program takes the NFA as input and outputs the epsilon-closure of all the states. NFA is described in a text file.The comments in the are important. It plays a role during parsing. This format should be adhered strictly. Please feel free to point out any bugs.

Click  Program to go to the GitHub link.
nfa.txt
//states
q0 q1 q2
//input_symbols
0 1
//start_state
q0
//final_state
q2
//transitions of the form : intial_state  input  final_state
q0 0 q0
q0 e q1
q1 1 q1
q1 e q2
q2 2 q2

program.c


Over 'https' the program won't be viewable. Please use 'http' or the GitHub link above.