Προς το περιεχόμενο
  • 0
bacileios

Regular expression σε NFA

Ερώτηση

Γεια σας ,εχω μια ερωτηση σχετικα με σχεδιαση NFA (ΜΠΑ)
 
η έκφραση είναι η
 
[A-E]|[A-E]{3}|[A-E]{4} 
 
δηλαδη ισοδύναμα
 
[A-E]|[A-E] [A-E] [A-E]|[A-E][A-E][A-E] [A-E]
 
 
 
Εχω κανει 2 NFA αλλα δε ξερω αν ειμαι 100% σωστος και επειδη πρεπει να προχορησω στο DFA θελω μια δευτερη γνωμη
 
1)Το πρωτο ειναι αυτο
image.png
 
 
 
2)η αυτο
image.png
 
 
Και δεν ξερω ποιο απο τα 2 ειναι ορθότερο...
 
το [A-E] NFA μου ειναι
 
image.png

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

7 απαντήσεις σε αυτή την ερώτηση

Προτεινόμενες αναρτήσεις

  • 0

Νομίζω αναγνωρίζουν τις ίδιες γλώσσες το 1 και το 2. Είναι ισοδύναμα. Αλλά λογικά το 1 που έχει λιγότερες καταστάσεις θα το μετατρέψεις πιο εύκολα σε DFA.

 

Btw, εμείς στη θεωρία υπολογισμού γιατί κάνουμε πιο δύσκολα; :/

Να φανταστείτε έχουμε κάνει αυτόματα στοίβας, plumbing lema (σε κανονικές και context free γλώσσες), Turing machine, μη αναγνωρίσιμες γλώσσες και δε συμμαζεύται...

 

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Εμένα πάλι τα 2 πρώτα μου φαίνονται λάθος.Με ε μετάβαση πας από  την αρχική σε τελική.Δηλαδή  κάνεις αναγνώρηση μόνο της κενής συμβολοσειράς και δεν ορίζεις καν μεταβάσεις για [Α-Ε]. Μόνο το τελευταίο είναι σωστό, το οποίο μπορείς να το ελαχιστοποιήσεις σε 2 καταστάσεις( αρχική και τελική ).

Από την άλλη αφού έχεις ήδη  έτοιμη την κανονική έκφραση,γιατί δεν κάνεις κατευθείαν το ΝΠΑ ; Αν θες πρώτα να φτιάξεις το ΜΠΑ,έχε στο νου σου οτι αν έχεις Ν καταστάσεις στο ΜΠΑ, το ΝΠΑ χωρίς ελαχιστοποιηση έχει 2^Ν.Μεγάλο παλούκι και  δεν χωράει στο χαρτί...

@nilos

pumping lemma λέγεται βρε.
Κάνετε και συντακτική ανάλυση ( LL , LR ) κτλ ; Ωραία είναι αυτά ! Πλάκα έχουν :P

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Εμένα πάλι τα 2 πρώτα μου φαίνονται λάθος.Με ε μετάβαση πας από  την αρχική σε τελική.Δηλαδή  κάνεις αναγνώρηση μόνο της κενής συμβολοσειράς και δεν ορίζεις καν μεταβάσεις για [Α-Ε]. Μόνο το τελευταίο είναι σωστό, το οποίο μπορείς να το ελαχιστοποιήσεις σε 2 καταστάσεις( αρχική και τελική ).

 

 

 

Το τελευταιο ειναι το ΜΠΑ του [Α-Ε] , τα πρωτα 2 ειναι το ΜΠΑ ολης της εκφρασης [A-E]|[A-E]{3}|[A-E]{4}

(ισοδυναμα [A-E]|[A-E] [A-E] [A-E]|[A-E][A-E][A-E] [A-E])

 

Απλα για το ΜΠΑ ολης της εκφρασης κατι δεν μου κολουσε και γι αυτο εφτιαξα 2 .

 

Το ΝΠΑ αν το κανω σωστα εχει γραψιμο αλλα ειναι τυφλοσουρτης και βγενει απλο .

 

p.s : Η σχηματικη απεικονιση του ΜΠΑ ειναι ενα δραμα αλλα να ναι καλα ο nfa generator 

 

Επισης επειδή υποτίθεται οτι η έκφραση συμβολίζει , τρίγωνα , τετράγωνα αν και αρχικά αγνοούμε την περίπτωση εισαγωγής

ΑΑB σαν όνομα τρίγωνου , κάτι που είναι λάθος στη συνεχεία θελουμε να το φτιάξουμε ετσι ώστε να μην επιτρέπει ονόματα που ο χρήστης βάζει για όνομα τρίγωνου η τετράγωνου ένα γραμμα 2 φορές.  Αυτο ψαχνω τωρα οποτε καποιο hint η site που περιγραφουν παρομοια περιπτωση θα ηταν χρησημο

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Το τελευταιο ειναι το ΜΠΑ του [Α-Ε] , τα πρωτα 2 ειναι το ΜΠΑ ολης της εκφρασης [A-E]|[A-E]{3}|[A-E]{4}

(ισοδυναμα [A-E]|[A-E] [A-E] [A-E]|[A-E][A-E][A-E] [A-E])

 

Απλα για το ΜΠΑ ολης της εκφρασης κατι δεν μου κολουσε και γι αυτο εφτιαξα 2 .

 

Το ΝΠΑ αν το κανω σωστα εχει γραψιμο αλλα ειναι τυφλοσουρτης και βγενει απλο .

 

p.s : Η σχηματικη απεικονιση του ΜΠΑ ειναι ενα δραμα αλλα να ναι καλα ο nfa generator 

 

 

Για να καταλάβω : Μέσα στο κυκλάκι έχεις [Α-Ε].Αυτό είναι  το όνομα της κατάστασης ή  το έχεις σαν "reference" στο τελευταίο ΜΠΑ ; Γιατί αν δεν είναι "reference" στο τελευταίο είναι και τα 2  λάθος

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Οκ τότε

Στη θέση σου θα έκανα το πρώτο αν και με ε-κλείσιμο στο ίδιο αποτέλεσμα πιστεύω θα φτάσεις

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
  • 0

Υπάρχει το jflap (προγραμματάκι σε java) το οποίο έχει υλοποιημένους πολλού αλγόριθμους σχετικά με γλώσσες, κ εκφράσεις, αυτόματα κλπ. Ψάξε και θα το βρεις -είμαι απ το κινητό τώρα και δε μπορώ να το βρω-

 

@Chris

Όχι, συντακτική ανάλυση και τα παρελκόμενα είναι στο μάθημα των compilers. Αλλά ναι όσο για το ότι είναι ωραία συμφωνώ ;-)

-Ξαναλέω χρησιμοποιώ τ9 και είμαι και ανορθογραφος :-P-

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε έναν λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι εύκολο!

Εγγραφείτε για έναν νέο λογαριασμό

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
×
×
  • Δημιουργία νέου...

Χρήσιμες πληροφορίες

Με την περιήγησή σας στο insomnia.gr, αποδέχεστε τη χρήση cookies που ενισχύουν σημαντικά την εμπειρία χρήσης.