DFA for Conjuntions/Adverbs/Adjectives

This repository is a university assignment solution for detecting conjunctions, adverbs, and adjectives with Deterministic Finite Automata (DFA).

How it works

The program will work by generating DFA states. For this to work, the user will need to pass in a list of words that is in the DFA. For example, in this repository the list of words for adjectives are big, small, blue. The user will need to have the list of words beforehand in order to generate the DFA.

Once the user have generated the DFA based on the list, the user can easily call the run() function within the DFA class to let the DFA detect the language defined. The run() function will return a list of detected words based on a given input by the user.

The DFA will be able to detect phrases that have more than one word. This is capable because the DFA uses a greedy method to detect words.

It is also worth noting that the DFA in this program is basically a map of characters to their possible next states. Example below.

{
    // Current state available options and their respective possible next states.
    0: {
        'a': 1,
        'b': 2,
        'c': 3
    },
    1: {
        't': 4,
    },
    2: {
        ...
    }
}

The example above will be able to match the word "at" because the starting state (index 0) can start with the character "a". "a" then have the option to go to state number 1 which it can transition with the character "t".

If "t" is a final state, then there will be no state number 4. Which the program will raise a KeyError, and from there will determine if the word will be accepted or not.

Files and Folders

The list of words for conjunctions, adverbs, and adjectives are defined in the language folder.

Words for conjunctions, adverbs, adjectives are generated by ChatGPT as there are no comprehensive list of words found online. The list of words have been cleaned to remove duplicate words.

The demo text folder contain two text files where the DFA will be tested against.

The dfa.py file defines the DFA class which have functions to generate the finite states and perform detection based on the finite states generated.