Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA
Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (Nondeterministic Finite Automaton – NFA) σε ισοδύναμο Ντετερμινιστικό Πεπερασμένο Αυτόματο (Deterministic Finite Automata - DFA). Η μετατροπή ενός NF...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2023
|
| Θέματα: | |
| Διαθέσιμο Online: | https://hdl.handle.net/10889/24346 |
| id |
nemertes-10889-24346 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Πεπερασμένα αυτόματα Θεωρία υπολογισμού Ισοδυναμία NFA-DFA Διαδικτυακές εφαρμογές Finite automata Theory of computation NFA-DFA equivalence Online apps |
| spellingShingle |
Πεπερασμένα αυτόματα Θεωρία υπολογισμού Ισοδυναμία NFA-DFA Διαδικτυακές εφαρμογές Finite automata Theory of computation NFA-DFA equivalence Online apps Παπασταύρου, Χριστίνα Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA |
| description |
Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (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. |
| author2 |
Papastavrou, Christina |
| author_facet |
Papastavrou, Christina Παπασταύρου, Χριστίνα |
| author |
Παπασταύρου, Χριστίνα |
| author_sort |
Παπασταύρου, Χριστίνα |
| title |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA |
| title_short |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA |
| title_full |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA |
| title_fullStr |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA |
| title_full_unstemmed |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA |
| title_sort |
σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή nfa σε dfa |
| publishDate |
2023 |
| url |
https://hdl.handle.net/10889/24346 |
| work_keys_str_mv |
AT papastaurouchristina schediasmoskaiylopoiēsēepharmogēsmegraphikoperiballongiametatropēnfasedfa AT papastaurouchristina designandimplementationofanapplicationwithgraphicalinterfacefornfatodfaconversion |
| _version_ |
1771297364177321984 |
| spelling |
nemertes-10889-243462023-02-01T04:38:57Z Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε DFA Design and implementation of an application with graphical interface for NFA to DFA conversion Παπασταύρου, Χριστίνα Papastavrou, Christina Πεπερασμένα αυτόματα Θεωρία υπολογισμού Ισοδυναμία NFA-DFA Διαδικτυακές εφαρμογές Finite automata Theory of computation NFA-DFA equivalence Online apps Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (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. - In this work, we address the constructive conversion of Nondeterministic Finite Automata (NFAs) to equivalent Deterministic Finite Automata (DFA). Such a conversion is often required in practical scenarios and it is a standard part of the curriculum of courses on Theory of Computation. In fact, for every NFA an equivalent DFA can be constructed via a standard conversion process known as "powerset construction" or "subset construction" which eliminates the NFA ambiguity. We designed and implemented a web application that is easy to use and has a user-friendly interface. The application takes as input a user-designed NFA and calculates the equivalent DFA, and allows the user to view each step of the DFA construction process. Launching the application, the user is presented with tree parts upper, middle and lower. The upper part contains simple syntax rules that the user must follow to provide the initial NFA. The middle part contains the form where the user enters information for the input NFA. The lower part contains visualizations for the initial NFA and the constructed equivalent DFA. If the form is filled in according to the rules, then the NFA information will be correctly entered. With the click of a button, the equivalent DFA is calculated and both the visualization of the NFA and the DFA are displayed in the lower part. At the same time, the user is given the option to download these visualizations as image files to their device. Furthermore, by pressing the corresponding button ("Show detailed process" button), the user can see the overall DFA construction process step by step, thus understanding the algorithm behind the conversion. For the development of the application, we used HTML, CSS, and Javascript. jQuery, Graphviz, viz, d3, and html2canvas libraries were also used. We used Visual Studio as our code editor as well as for writing HTML, CSS, and Javascript scripts, and for debugging purposes. Later on, we will describe these software components. Our application can be of practical usefulness especially due to the graphical design environment; it can also be exploited for student education and training both in real or virtual learning environments, in an online or offline manner. 2023-01-31T06:32:20Z 2023-01-31T06:32:20Z 2023-01-27 https://hdl.handle.net/10889/24346 el Attribution-NonCommercial-NoDerivs 3.0 United States http://creativecommons.org/licenses/by-nc-nd/3.0/us/ application/pdf |
