Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση
Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (Non-deterministic Finite Automaton – NFA) σε ισοδύναμη κανονική έκφραση (Regular expression). Η μετατροπή πεπερασμένου αυτομάτου σε ισοδύναμη κανονικ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2022
|
| Θέματα: | |
| Διαθέσιμο Online: | https://hdl.handle.net/10889/23569 |
| id |
nemertes-10889-23569 |
|---|---|
| record_format |
dspace |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Κανονικές εκφράσεις Μετατροπή Ψηφιακές εφαρμογές NFA Regular expressions Conversion Digital applications |
| spellingShingle |
Κανονικές εκφράσεις Μετατροπή Ψηφιακές εφαρμογές NFA Regular expressions Conversion Digital applications Τράμπαρης, Ζήσης-Στυλιανός Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση |
| description |
Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (Non-deterministic Finite Automaton – NFA) σε ισοδύναμη κανονική έκφραση (Regular expression). Η μετατροπή πεπερασμένου αυτομάτου σε ισοδύναμη κανονική έκφραση είναι πάντα εφικτή. Η σχετική κατασκευαστική διαδικασία-απόδειξη αποτελεί μέρος της ύλης μαθημάτων στην περιοχή της Θεωρίας Υπολογισμού αλλά ανακύπτει συχνά στην πράξη και σε πραγματικές περιστάσεις. Σκοπός της εφαρμογής είναι να υποστηρίξει τόσο πρακτικές εφαρμογές που απαιτούν τη μετατροπή NFA σε ισοδύναμη κανονική έκφραση όσο και κάθε εκπαιδευτική διαδικασία που περιλαμβάνει τη διδασκαλία και εκπαίδευση στη μέθοδο μετατροπής NFA σε ισοδύναμη κανονική έκφραση. Η εφαρμογή δέχεται σαν είσοδο ένα πεπερασμένο αυτόματο και επιστρέφει μια ισοδύναμη κανονική έκφραση δίνοντας επιπλέον τη δυνατότητα για παρακολούθηση της διαδικασίας μετατροπής. Η εισαγωγή του αρχικού αυτομάτου, που αποτελεί την είσοδο στην εφαρμογή, γίνεται με γραφικό τρόπο. Εκτός από τον άμεσο υπολογισμό κανονικής έκφρασης ισοδύναμης με το δοσμένο Μη Ντετερμινιστικό Πεπερασμένο Αυτόματο (Non-deterministic Finite Automaton – NFA), η εφαρμογή που αναπτύχθηκε παρέχει επιπλέον τη δυνατότητα παρακολούθησης της διαδικασίας σταδιακής μετατροπής του αρχικού NFA σε ισοδύναμη κανονική έκφραση. Η εφαρμογή υλοποιήθηκε στη δημοφιλή πλατφόρμα ανάπτυξης γραφικών εφαρμογών Unity με συμπληρωματική χρήση της γλώσσας προγραμματισμού C# για τη διαχείριση των λειτουργιών των γραφικών αντικειμένων και την υλοποίηση των επιμέρους λειτουργιών της εφαρμογής. Τα γραφικά υποστηρίχτηκαν από τις βιβλιοθήκες γραφικών DirectX 11 που ενσωματώνει η Unity. Η συγγραφή του κώδικα έγινε στην πλατφόρμα Visual Studio. Για την σχεδίαση εικονιδίων και γραφικών αντικειμένων χρησιμοποιήθηκε το πρόγραμμα επεξεργασίας γραφικών Gimp. |
| author2 |
Tramparis, Zisis-Stylianos |
| author_facet |
Tramparis, Zisis-Stylianos Τράμπαρης, Ζήσης-Στυλιανός |
| author |
Τράμπαρης, Ζήσης-Στυλιανός |
| author_sort |
Τράμπαρης, Ζήσης-Στυλιανός |
| title |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση |
| title_short |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση |
| title_full |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση |
| title_fullStr |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση |
| title_full_unstemmed |
Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση |
| title_sort |
σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή nfa σε κανονική έκφραση |
| publishDate |
2022 |
| url |
https://hdl.handle.net/10889/23569 |
| work_keys_str_mv |
AT tramparēszēsēsstylianos schediasmoskaiylopoiēsēepharmogēsmegraphikoperiballongiametatropēnfasekanonikēekphrasē AT tramparēszēsēsstylianos designandimplementationofdigitalapplicationwithgraphicalenviromentfortheconversionofnfatoregularexpression |
| _version_ |
1771297235083984896 |
| spelling |
nemertes-10889-235692022-11-01T04:35:45Z Σχεδιασμός και υλοποίηση εφαρμογής με γραφικό περιβάλλον για μετατροπή NFA σε κανονική έκφραση Design and implementation of digital application with graphical enviroment for the conversion of NFA to regular expression Τράμπαρης, Ζήσης-Στυλιανός Tramparis, Zisis-Stylianos Κανονικές εκφράσεις Μετατροπή Ψηφιακές εφαρμογές NFA Regular expressions Conversion Digital applications Στο πλαίσιο της παρούσας διπλωματικής αναπτύχθηκε εφαρμογή με γραφικό περιβάλλον για τη μετατροπή δοσμένου Μη Ντετερμινιστικού Πεπερασμένου Αυτομάτου (Non-deterministic Finite Automaton – NFA) σε ισοδύναμη κανονική έκφραση (Regular expression). Η μετατροπή πεπερασμένου αυτομάτου σε ισοδύναμη κανονική έκφραση είναι πάντα εφικτή. Η σχετική κατασκευαστική διαδικασία-απόδειξη αποτελεί μέρος της ύλης μαθημάτων στην περιοχή της Θεωρίας Υπολογισμού αλλά ανακύπτει συχνά στην πράξη και σε πραγματικές περιστάσεις. Σκοπός της εφαρμογής είναι να υποστηρίξει τόσο πρακτικές εφαρμογές που απαιτούν τη μετατροπή NFA σε ισοδύναμη κανονική έκφραση όσο και κάθε εκπαιδευτική διαδικασία που περιλαμβάνει τη διδασκαλία και εκπαίδευση στη μέθοδο μετατροπής NFA σε ισοδύναμη κανονική έκφραση. Η εφαρμογή δέχεται σαν είσοδο ένα πεπερασμένο αυτόματο και επιστρέφει μια ισοδύναμη κανονική έκφραση δίνοντας επιπλέον τη δυνατότητα για παρακολούθηση της διαδικασίας μετατροπής. Η εισαγωγή του αρχικού αυτομάτου, που αποτελεί την είσοδο στην εφαρμογή, γίνεται με γραφικό τρόπο. Εκτός από τον άμεσο υπολογισμό κανονικής έκφρασης ισοδύναμης με το δοσμένο Μη Ντετερμινιστικό Πεπερασμένο Αυτόματο (Non-deterministic Finite Automaton – NFA), η εφαρμογή που αναπτύχθηκε παρέχει επιπλέον τη δυνατότητα παρακολούθησης της διαδικασίας σταδιακής μετατροπής του αρχικού NFA σε ισοδύναμη κανονική έκφραση. Η εφαρμογή υλοποιήθηκε στη δημοφιλή πλατφόρμα ανάπτυξης γραφικών εφαρμογών Unity με συμπληρωματική χρήση της γλώσσας προγραμματισμού C# για τη διαχείριση των λειτουργιών των γραφικών αντικειμένων και την υλοποίηση των επιμέρους λειτουργιών της εφαρμογής. Τα γραφικά υποστηρίχτηκαν από τις βιβλιοθήκες γραφικών DirectX 11 που ενσωματώνει η Unity. Η συγγραφή του κώδικα έγινε στην πλατφόρμα Visual Studio. Για την σχεδίαση εικονιδίων και γραφικών αντικειμένων χρησιμοποιήθηκε το πρόγραμμα επεξεργασίας γραφικών Gimp. In this work, we address the constructive conversion of Nondeterministic Finite Automata (NFAs) to equivalent Regular Expressions (REs). Such a conversion is often required in practical scenaria and it is a standard part of the curriculum of courses on Theory of Computation. It is always feasible and can be done by the application of a particular recursive technique, also known as the GNFA algorithm. This technique gradually eliminates states and transitions among them and replaces them with equivalent regular expressions, which are eventually combined into a single regular expression. We designed and implemented an online application offering a very user-friendly graphical environment. The application receives as input a user-designed NFA and computes an equivalent RE, while enabling users to observe every step of the conversion process. Launching the application, users are presented with a canvas where they can design in a simple and straight-forward way the input NFA. Then, by the press of a button, an equivalent regular expression is computed and presented on-screen. Users can graphically observe in a step-by-step fashion the overall conversion process, thus gaining insight for the algorithm behind the conversion. A comprehensive tutorial for the supported functionalities and the design procedure is also provided. For the development, we used Unity (version 2022.1) in combination with the default DirectX 11 libraries and C#. We used Visual Studio 2022 as our code editor as well as for writing C# scripts and for debugging purposes. 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. 2022-10-31T12:56:03Z 2022-10-31T12:56:03Z 2022-10 https://hdl.handle.net/10889/23569 el application/pdf |
