A utility tool used for validating regular expressions corresponding to a provided word
The tool accepts a regular expression. Afterwards, a ε-NFA(Epsilon Non-Deterministic Finite Automata) is constructed based on the regular expression. The automata has the capability to check whether a certain word is accepted or rejected by traversing from an initial to a final state.
( : Opening bracket
) : Closing bracket
+ : Kleene plus
* : Kleene star
| : Logical or operator
Construct a FiniteAutomation with a regular expresion and flags. The flags specify whether the automata should include an initial and/or a final state.
FiniteAutomation automation("(c|f)*f", true, true);The constructed automata can be printed in the console using the printFromInitialState method. The regular expression (c|f)*f generates the following output:
[start->(1)-#->(2)] [(2)-#->(3)] [(3)-#->(4)] [(4)-#->(5)(4)-#->(6)(4)-#->(7)] [(5)-#->(8)] [(8)-#->(9)] [(9)-#->(10)] [(10)-c->(11)] [(11)-#->(12)] [(12)-#->(13)] [(13)-#->(14)] [(14)-#->(15)] [(15)-#->(7)] [(6)-#->(16)] [(16)-#->(17)] [(17)-#->(18)] [(18)-b->(19)] [(19)-#->(20)] [(20)-#->(21)] [(21)-#->(22)] [(22)-#->(15)] [(7)-#->(23)(7)-#->(4)] [(23)-#->(24)] [(24)-#->(25)] [(25)-f->(26)] [(26)-#->(27)] [(27)-#->(28)] [(28)-#->(29)] [(29)->end]
The # symbol signifies the epsilon or lambda transitions. The visual representaion of the generated output is depicted below:
So as to check if a word is accepted by the automation instance, the isAccepted method is used:
bool isAccepted = automation.isAccepted("cbbcbcbbcf");
cout << isAccepted // '1' would be outputed