Regular expression σε NFA

[bacileios]

Γεια σας ,εχω μια ερωτηση σχετικα με σχεδιαση 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]

 

αναγνωριζει    A,B, ABC, BCD, BCDE, ect.
(ιδιο με http://www.insomnia.gr/topic/330941-%CE%BC%CE%B5%CF%84%CE%B1%CE%B3%CE%BB%CF%89%CF%84%CE%B9%CF%83%CF%84%CE%B5%CF%82-%CE%BB%CE%B5%CE%BA%CF%84%CE%B9%CE%BA%CE%B7-%CE%B1%CE%BD%CE%B1%CE%BB%CF%85%CF%83%CE%B7/)

 

 

Εχω κανει 2 NFA αλλα δε ξερω αν ειμαι 100% σωστος και επειδη πρεπει να προχορησω στο DFA θελω μια δευτερη γνωμη

 

1)Το πρωτο ειναι αυτο

 

 

 

2)η αυτο

 

 

Και δεν ξερω ποιο απο τα 2 ειναι ορθότερο...
 

το [A-E] NFA μου ειναι

 

[nilosgr]

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

 

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

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

 

[ChRis6]

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

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

@nilos

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

[bacileios]

Εμένα πάλι τα 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 που περιγραφουν παρομοια περιπτωση θα ηταν χρησημο

[ChRis6]

Το τελευταιο ειναι το ΜΠΑ του [Α-Ε] , τα πρωτα 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  λάθος

[bacileios]

reference ειναι στο [Α-Ε] οπως εχει οριστει αυτο στο 3ο σχεδιο,

[ChRis6]

Οκ τότε

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

[nilosgr]

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

 

@Chris

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

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