Giter Club home page Giter Club logo

dfa-sim's Introduction

The program that I engineered for this course emulates a deterministic finite automaton by simply implementing the mathematical definition for the DFA using tools provided by the C++ standard library.

The architecture of my simulator revolves around a DFA class that encapsulated the essential elements of a deterministic finite automaton. States were represented as a set of strings, allowing for flexible definition of DFAs with varying numbers of states. The alphabet is represented as a set of characters, accommodating different input symbols. The program supports an arbitrary number of states and alphabet sizes, allowing users to define and simulate any DFA. Additionally, as detailed in the course textbook, each DFA has some start state, and a set of accept states. The transition function was implemented using maps, and associates states and symbols with a corresponding next state. One final aspect of the DFA class that is not outlined in the textbook is the way the current state is stored, which I do using a member string which stores what the current state is.

In terms of program structure, the main driver was separated from the DFA functionality. The main driver is responsible for user interaction and instantiates a DFA object passing user-defined inputs in the form of .dfa files to the DFA object which parses the file and populates the object. The executable, by default named dfa-sim, follows the same functionality as outlined in the assignment instructions document. It’s functionality can be queried using ./dfa-sim -h.

Sample machines are provided, with a .dfa machine definition file, a .in sample input file, and a .out expected output sample. The program is written in C++ and supports both Windows and Linux. Building the program can be done via this command:

~/dfa-sim-submission$ mkdir build && cd build && cmake ../ && cmake --build .

Ideas to improve:

  • Set up CI/CD to automatically build when new changes are pushed/merged into master
  • Set up CI/CD to automatically publish binaries on master
  • Flesh out this README file
  • Provide more input machines
  • Support for NFAs
  • Better support for different machine input types (json...)
  • Decouple DFA and parsing logic
  • DFA object should be able to verify if the machine is valid (all transitions accounted for)
  • Implement a lenient mode allowing a machine to be described with just a certain set of transitions rather than a full description of states/alphabet etc.
  • Better command line interfacing
  • Optimize for larger, more complex machines
  • Convert regex to a machine
  • Interactive mode
  • Proper user interface
  • Either update getopt.c/h to come in as a separate library or properly attribute them

dfa-sim's People

Contributors

gavinsadler avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    πŸ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. πŸ“ŠπŸ“ˆπŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❀️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.