Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA

Thumbnail Image
Date
2023-01-27
Authors
Παπασταύρου, Χριστίνα
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (Nondeterministic Finite Automaton – NFA) σε ισοδύναμο Ντετερμινιστικό Πεπερασμένο Αυτόματο (Deterministic Finite Automata - DFA). Η μετατροπή ενός NFA σε DFA είναι πάντοτε εφικτή και πραγματοποιείται μέσω μίας τυπικής διαδικασίας γνωστή και ως “powerset construction” ή “subset construction”. Η διαδικασία αυτή αποτελεί κομμάτι της ύλης της Θεωρίας Υπολογισμού, αλλά ανακύπτει συχνά στην πράξη και σε πραγματικές περιστάσεις. Σκοπός της εφαρμογής είναι να υποστηρίξει τόσο πρακτικές εφαρμογές που απαιτούν τη μετατροπή NFA σε ισοδύναμο DFA όσο και κάθε εκπαιδευτική διαδικασία που περιλαμβάνει τη διδασκαλία και εκπαίδευση στη μέθοδο μετατροπής NFA σε ισοδύναμο DFA. Η εφαρμογή (N2D) δέχεται σαν είσοδο ένα μη ντετερμινιστικό πεπερασμένο αυτόματο και επιστρέφει το ισοδύναμο ντετερμινιστικό πεπερασμένο αυτόματο δίνοντας επιπλέον τη δυνατότητα για παρακολούθηση της διαδικασίας μετατροπής. Η εισαγωγή του αρχικού αυτομάτου, γίνεται μέσω μίας εύχρηστης φόρμας. Εκτός από τον άμεσο υπολογισμό του ισοδύναμου DFA, η εφαρμογή που αναπτύχθηκε δίνει τη δυνατότητα στο χρήστη να παρατηρήσει όλα τα ενδιάμεσα βήματα της κατασκευής του ισοδύναμου DFA. Η εφαρμογή υλοποιήθηκε με τη χρήση των γλωσσών HTML, CSS και Javascript. Μέσω της HTML δημιουργήσαμε το περιεχόμενο της εφαρμογής μας, ενώ η CSS μας βοήθησε να μορφοποιήσουμε αυτό το περιεχόμενο όπως θέλαμε. Τέλος μέσω της Javascript και κάποιων open source βιβλιοθηκών της προσδώσαμε στην εφαρμογή μας την επιθυμητή λειτουργικότητα. Πιο συγκεκριμένα χρησιμοποιήθηκαν η βιβλιοθήκες jQuery, Graphviz (μαζί με τις d3 και viz) και html2canvas. Η συγγραφή του κώδικα έγινε στην πλατφόρμα Visual Studio.
Description
Keywords
Πεπερασμένα αυτόματα, Θεωρία υπολογισμού, Ισοδυναμία NFA-DFA, Διαδικτυακές εφαρμογές
Citation