International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072
DFA CREATOR AND STRING TESTER
1,2,3,4
Abstract - Machines and their working is one the vital and major concepts to understand and work on. DFA which is Deterministic Finite Automata is a very easy and understandable concept, to learn the workingofdifferent real-life machines. To visualize the working efficiency of DFA models, this web-based platform helps the end user to create various such DFAs using a very user-friendly GUI. To simplify DFA working the project is divided into the following parts: the creation of states, creating transitions, inserting states, and deleting states. After completing the design of the machine the user can test different input strings for understanding the language and working of the machine. The test results are shown simultaneously to the user. This web project focuses on the practical and hands-on implementation of different concepts of DFA including states, transitions, final states, and initial states. To simplify the understanding and working of DFA and its flow control, users can use the drag and move functionality.
Key Words: DFA, Automata, Machine, Web-based
1. INTRODUCTION
DFAwhichisavitalpartof automationtheoryisalmosta theoreticalconcept.Manyofitscontentssuchasstatestheir types,transitionbetweentwostates,finalstates,andtheir symbolic representation can be understood easily by ideating the visuals. This project emphasizes the actual working of a machine. Learning these machines and their workingonpenandpaperbecomestoughwhenthenumber ofstatesandtransitionsincreasesproportionally.Tosoothe thelearningprocessofbuildingDFA,thiswebappgivesGUI basedplatformwheretheadditionofstatesandconnecting thembecomeseasybyjustclickingonbuttons.Theusercan parallelly make a state final, add a new state, or delete an addedstatebyusingtherespectivebuttons.Buildingsuch DFA’swillhelptounderstandtheworkingofreal-timeand real-usage machines and enhance concept building. The projectalsohasateststringfunctionalitywheretheusercan test,whichstringsareacceptedbythedesignedDFA,which furtherlyhelpstoidentifythelanguageacceptedbytheDFA. This type of interaction erases the barriers that stand up whilelearningthefunctionalityofmachines.DFAwhichis popularly used by different compilers explains the mechanism of validation which is used in different fields suchaspasswordchecking.Themainintentoftheprojectis to make a cognizant understanding of the working of machines.
2. LITERATURE REVIEW
[1]Inthisarticle,theauthorsdescribethedevelopmentofa toolforvisualizinganddebuggingdeterministicfinite-state machines(DFAs).ThetoolallowsuserstoconstructDFAsby specifyingthestatesandtransitionsofthemachine,andit providesavisualrepresentationoftheDFAasitprocesses input.Thetoolalsoincludesafeatureforgeneratingcodein thefinitestatemachine(FSM)language,whichallowsusers to execute their edited machines. The authors proposed a mechanism for visualizing and verifying the behavior of formalmachinesduringdebugging,andtheyclaimthattheir toolisuniqueinitsabilitytogeneratecodeforstate-based machines.Thistoolcouldbeusefulforeducators,students, or researchers working with DFAs, as it provides a more intuitive and interactive way of constructing and understandingthesemachines.
[2]AnEfficientProtocolforObliviousDFAEvaluationand Applicationsitdesignsanefficienttoolfortheevaluationof deterministic finite automata (DFA) between one input holderandaDFAsecondholder.Italsodesignsaprotocolto compute the counting number of accepting states for evaluationofDFAonaninput.Tosolvethecountingvariant ofstatesitintroducesa novel modificationforprotocol.It implements a protocol and runs the experiments for the evaluationoftheDFAstring
[3] This article described a tool that allows users to experimentwithfiniteautomataandgeneratelistsofstrings inthelanguagerecognizedbytheautomaton.Thetoolalso has the ability to perform various conversions, such as convertinganNFA(nondeterministicfiniteautomaton)toa DFA(deterministicfiniteautomaton).Inautomatatheory,a finiteautomatonisamathematicalmodelusedtorecognize patternswithintheinput.Itconsistsofafinitesetofstates,a setofinputsymbols,atransitionfunction,astartstate,anda setofacceptingstates.Theautomatonreadsinputsymbols one at a time, transitioning from one state to another accordingtothetransitionfunctionuntiliteitheracceptsor rejectstheinput.
[4] Dynamic testing is a software testing technique that involvestesting a systemwhileitisexecuting.Thegoal of dynamic testing is to evaluate the behavior of a system at runtime and ensure that it is functioning as expected. Automatalearningisatechniqueusedtolearnthebehavior of a system by constructing a finite automaton that represents the system's behavior. This can be useful for testingpurposes,astheautomatoncanbeusedtogenerate
International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072
testcasesthatcoverawiderangeofbehaviorsexhibitedby thesystem.
[5]Inthisarticle,theauthorsdescribedtheusageoffinite stateautomatatodetectsensitivewordsinatextstring.The automataistrainedtorecognizealargenumberofkeywords and can be used to improve the efficiency of the system. Error recognition mechanisms are also implemented to reducetheerrorrateandimprovetheperformanceofthe system.Finitestateautomataisausefultoolforrecognizing patterns in input and can be applied to a wide range of applications, including text processing and language recognition. In this case, the automata is used to identify sensitivewordsinatextstring,whichcouldbeusefulinthe contextofdistanceeducation.
[6] In automata theory, a deterministic finite automaton (DFA)isatypeoffiniteautomatonthatreadsinputsymbols one at a time and transitions from one state to another accordingtoafixedsetofrules.ADFAcanberepresented usingafinitestatemachine,whichconsistsofasetofstates, asetofinputsymbols,atransitionfunction,astartstate,and a set of accepting states. Binary strings can be used to represent the transition function and the set of accepted states of a DFA. Context-free grammars (CFGs) are a formalism used to describe the structure of programming languages.Theyconsistofasetofterminalsymbols,which represent the basic elements of the language, and a set of nonterminal symbols, which represent more complex structures. A CFG can be used to generate the set of all possiblestringsthatbelongtothelanguageitdescribes.
3. METHODOLOGY
A) Proposedsystem
Themainaimofdesigningthisapplicationis,forlearnersto understand the DFA concept. This system allows users to constructordesignaDFAaccordingtoproblemstatement. Userscanaddstatesasperneedandgivetransitionstothe states.Thengiveinputstringsbetweenthestatesandtest thestringwhetheritisvalidornot.Thisapplicationallows userstodeleteastateandmakeafinalstate.Thisapplication is easy to understand and easy to use for learners. This projectisdevelopedusingHTML,CSS,andJavaScript.
B) Flowchart
Thisapplicationconsistsoftwomajorconceptsthatinclude constructinga DFAandtestinga DFA.Toconstructa DFA four major steps are considered including add state, state transition,makefinalstate,anddeletestate.
i) DesignDFA
In DFA (deterministic finite automata) first, add an initial stateforexampleq1andthenaddtheotherstatesfollowing the initial state for example q1,q2,q3, etc. Then add
transitionsbetweentheinitialstateandthefollowingstates intheDFA.In the transition between the statesaddinput stringsforexample1,0,a,b,etc.Fromtheinitialstateand following states make a final state in the DFA. Then the designofDFAiscomplete.
ii) Testing
First,wehavetoentertheinputstringfromtheinitialstate to other states transitions then user enters string to test whetheritisvalidornotfortheconstructedDFA.Intesting iftheinputstringisvalidthenitwillbeacceptedbytheDFA otherwiseitwillberejectedbytheDFA.
iii) StateTransition
After constructing the DFA, add the initial states and the following states then user adds the transition from the currentstatetothenextstateandgivesinputstrings. We havetospecifyvalidinputstringsforgivenstatesandthen connectthestates.
International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072
Algorithm:
Step1:Addinitialstate.
Heretheuseraddsthestartingstate.
Step2:Addthefollowingstates.
Inthisstep,theuseraddstheotherstates.
Step3:Addtransitionbetweenstates.
Heretheuseraddsthetransitionbetweentheaddedstates. Similarly,theusergivestheinputvaluesforthetransitions.
Step4:Makeastatefinal.
Hereusermakesastateasfinal,theusercanmakeoneor morestatesasfinal.
Step5:TestinputstringfordesignedDFA.
Here the user checks which string is accepted by the DFA andwhichisnot
iv) Deleteastate
After the design of DFA deleting a state is possible. Select one of theconstructed states,thenselecta state to delete andclickondeletestatebutton.
4. RESULTS AND DISCUSSIONS
v) MakeAfinalState
SelectoneofthestatestomakeafinalstatefromtheDFA andthenclickonmakefinalstate.Thisfunctionalityallows theusertomakemorethanonestateasafinalstate.
Fig6:ConstructedDFA
Infig6:theuserconstructedDFAbyaddingstatesbyusing Addstatebutton.Thentheuseraddsstatetransitionfromq0 toq1andq1toq2andgivesinputas1,0.Theusermakesa finalstateasQ2.ByusingTeststringbuttontheuserchecks whethertheinputstringenteredisacceptedornot.
International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072
5. SCOPE OF PROJECT
InthisprojectDFACreatorandStringTester,wecanonly designDFAandtestinputstrings.Inthefuture,wecanadd manyoperationsandfunctionslikeanNFAgenerator,and PDA,constructaDFAwithagivenregularexpression,and conversionofDFAtoNFA.
6. CONCLUSION
In this paper, we described the use of a DFA Creator and String Tester for learners. Learners can understand practicallyhowDFAworksbyusingthisapplication.Users canconstructordesignaDFAasperneed,maketransitions, giveinputstring,makeafinalstate,andtesttheDFA.They canpracticallyperformoperationsandgenerateDFA from thissystem.
REFERENCES
[1]VisualDesigningandDebuggingofDeterministicFiniteStateMachinesinFSM[2008.09254]VisualDesigningand Debugging of Deterministic Finite-State Machines in FSM (arxiv.org)
Fig7:Output1
Infig7:theinputstringgivenfromQ0toQ1is1andfrom Q1toQ2is0.Theinputstring10istestedanditisaccepted asshownintheabovefigure
[2]AnEfficientProtocolforObliviousDFAEvaluationand Applications An Efficient Protocol for Oblivious DFA EvaluationandApplications|SpringerLink
[3]ACollectionofToolsforMakingAutomataTheoryand Formal Languages Come Alive A collection of tools for makingautomatatheoryandformallanguagescomealive| ACMSIGCSEBulletin
[4]DynamictestingviaautomatalearningDynamicTesting ViaAutomataLearning|SpringerLink
[5] Application Research of Finite Automaton in Distance Education Application research of finite automaton in distance education | IEEE Conference Publication | IEEE Xplore
[6]AGeneralApproachtoDFAConstruction(PDF)AGeneral ApproachtoDFAConstruction(researchgate.net)
[7] Kuldeep Vayadande,Aditya Bodhankar,Ajinkya Mahajan,Diksha Prasad,Shivani Mahajan,Aishwarya PujariandRiyaDhakalkar,“ClassificationofDepressionon social media using Distant Supervision”, ITM Web Conf. Volume50,2022.
Fig8:Output2
Infig8:theinputstringenteredfromQ0toQ1is1andfrom Q1toQ2is0.Theinputstring1istestedanditisrejectedas Q1isnotafinalstateasshownintheabovefigure.
[8]KuldeepVayadande,RahebarShaikh,SurajRothe,Sangam Patil,Tanuj BarwareandSameer Naik,” Blockchain-Based LandRecordSystem”,ITMWebConf.Volume50,2022.
[9]KuldeepVayadande,KirtiAgarwal,AadeshKabra,Ketan GangwalandAtharvKinage,”CryptographyusingAutomata Theory”,ITMWebConf.Volume50,2022
[10] Samruddhi Mumbare,Kunal Shivam,Priyanka Lokhande,Samruddhi Zaware,Varad DeshpandeandKuldeep Vayadande,” Software Controller usingHandGestures”,ITMWebConf.Volume50,2022
[11]Preetham,H.D.,andKuldeepBabanVayadande."Online CrimeReportingSystemUsingPythonDjango."
[12]Vayadande,KuldeepB.,etal."SimulationandTestingof Deterministic Finite Automata Machine."International JournalofComputerSciencesandEngineering10.1(2022): 13-17.
[13] Vayadande, Kuldeep, et al. "Modulo Calculator Using TkinterLibrary."EasyChairPreprint7578(2022).
[14] VAYADANDE, KULDEEP. "Simulating Derivations of Context-FreeGrammar."(2022).
[15] Vayadande, Kuldeep, Ram Mandhana, Kaustubh Paralkar,DhananjayPawal,SiddhantDeshpande,andVishal Sonkusale."PatternMatchinginFileSystem."International JournalofComputerApplications975:8887.
[16] Vayadande, Kuldeep, Ritesh Pokarne, Mahalakshmi Phaldesai, Tanushri Bhuruk, Tanmay Patil, and Prachi Kumar."SimulationOfConway’sGameOfLifeUsingCellular Automata."SIMULATION9,no.01(2022).
[17] Gurav, Rohit, Sakshi Suryawanshi, Parth Narkhede, Sankalp Patil, Sejal Hukare, and Kuldeep Vayadande. "UniversalTuringmachinesimulator."InternationalJournal ofAdvanceResearch,IdeasandInnovationsinTechnology, ISSN(2022).
[18] Vayadande, Kuldeep B., Parth Sheth, Arvind Shelke, VaishnaviPatil,SrushtiShevate,andChinmayeeSawakare. "Simulation and Testing of Deterministic Finite Automata Machine."International Journal of Computer Sciences and Engineering10,no.1(2022):13-17.
[19] Vayadande, Kuldeep, Ram Mandhana, Kaustubh Paralkar,DhananjayPawal,SiddhantDeshpande,andVishal Sonkusale."PatternMatchinginFileSystem."International JournalofComputerApplications975:8887.
[20]Vayadande,KuldeepB.,andSurendraYadav."AReview paper on Detection of Moving Object in Dynamic Background."International Journal of Computer Sciences andEngineering6,no.9(2018):877-880.
[21] Vayadande, Kuldeep, Neha Bhavar, Sayee Chauhan, SushrutKulkarni,AbhijitThorat,andYashAnnapure.Spell CheckerModelforStringComparisoninAutomata.No.7375. EasyChair,2022.
[22]Vayadande,Kuldeep,HarshwardhanMore,OmkarMore, Shubham Mulay, Atharva Pathak, and Vishwam Talnikar. "PacMan:GameDevelopmentusingPDAandOOP."(2022).
[23]Preetham,H.D.,andKuldeepBabanVayadande."Online CrimeReportingSystemUsingPythonDjango."
[24] Vayadande, Kuldeep. "Harshwardhan More, Omkar More, Shubham Mulay, Atahrv Pathak, Vishwam Talanikar,“Pac Man: Game Development using PDA and OOP”."International Research Journal of Engineering and Technology(IRJET),e-ISSN(2022):2395-0056.
[25] Ingale, Varad, Kuldeep Vayadande, Vivek Verma, Abhishek Yeole, Sahil Zawar, and Zoya Jamadar. "Lexical analyzer using DFA."International Journal of Advance Research, Ideas and Innovations in Technology, www. IJARIIT.com.
[26]Manjramkar,Devang,AdwaitGharpure,AayushGore, IshanGujarathi,andDhananjayDeore."AReviewPaperon Documenttextsearchbasedonnondeterministicautomata." (2022).
[27] Chandra, Arunav, Aashay Bongulwar, Aayush Jadhav, Rishikesh Ahire, Amogh Dumbre, Sumaan Ali, Anveshika Kamble,RohitArole,BijinJiby,andSukhpreetBhatti.Survey on Randomly Generating English Sentences. No. 7655. EasyChair,2022.
International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072 © 2022, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page271