Regular expression

Θεωρούμε τις εξής γλώσσες L πάνω στο αλφάβητο Σ = {a, b}:

·         L_α η γλώσσα που αντιστοιχεί στην κανονική έκφραση b^* + b^* a.

• L_β που αναγνωρίζεται από το παρακάτω ντετερμινιστικό πεπερασμένο αυτόματο Μ_β.
• L_γ που αναγνωρίζεται από το παρακάτω ντετερμινιστικό πεπερασμένο αυτόματο Μ_γ.

1.           Δώστε μια περιγραφή σε φυσική γλώσσα για την L_α. Να κατασκευάσετε ένα ντετερμινιστικό πεπερασμένο αυτόματο που να αναγνωρίζει την γλώσσα L_α. Να δικαιολογήσετε την κατασκευή σας.

2.           Να δώσετε μία κανονική έκφραση που να παράγει την γλώσσα L_β.

3.           Να περιγράψετε άτυπα τη γλώσσα L_γ και να δώσετε μία κανονική έκφραση που την παράγει (π.χ. πλήθος ίδιων διαδοχικών συμβόλων αή b, περιεχόμενες υποσυμβολοσειρές, μήκος συμβολοσειρών, …).

Regular expression

-------------------------------------------------!

< Απάντηση>

<Α>

Οι συμβολοσειρές δεν θα έχουν περισσότερα από  3 α.

1.      Ο συνολικός αριθμός α που θα περιέχει η έκφραση μας θα είναι 0 ή 1 ή 2.

2.      Ακόμα η έκφραση μας όταν περιέχει 1 ή 2 άλφα θα μπορούσε να ξεκινά από α ή b , δηλαδή η έκφραση μας ξεκινά b* επειδή σε b  δεν υπάρχει περιορισμός.

3.      Όταν περιέχει 1 ή 2 α τότε στην έκφραση τα α θα μπορούσαν τα α να είναι στο τέλος της έκφρασης (α+0 )δηλαδή να τελειώνει με b*

Λαμβάνοντας όλα τα παραπάνω μπορούμε να σχηματίσουμε την κανονική έκφραση.

L₁ = b*(ε+α)b*(ε+α)b*(ε+α)b*

Δηλαδή η έκφραση μας ξεκινά με b* και έπειτα έχει  (ε+α) ακολουθώντας από το b*.

(ε+α) σημαίνει ότι μπορεί να διαλέξω το κενό. Παράδειγμα εάν διαλέξω το κενό και στις 3 επιλογές τότε δεν θα εχω κανένα α αντίθετα εάν διαλέξω  1 α από την πρώτη και κενό στις επόμενες 2 τότε θα  έχω ένα άλφα στην έκφραση μου. Σε όλες τις επιλογές μου μεταξύ του α μπορεί να παρεμβάλλεται το b. Επίσης εάν διαλέξω 2 φορές α και ένα κενό τότε θα εχω 2 α ενώ εάν διαλέξω 3 α και κανένα κενό θα εχω τρία α στην έκφραση μου.

<Γ>

Όλες οι συμβολοσειρές που ο περιχέουν μια φορά ακριβώς την εμφάνιση της υποσυμβολοσειράς ααα.

Θα μπορούσαμε τα 3 άλφα να περικλείουμε από b* δηλαδή να είναι b*αααb*, όμως αυτή είναι μια περίπτωση. Σίγουρα δεν θα έχουμε περισσότερα από 3 α δηλαδή θα εξασφαλίσουμε τα  ααα αλλά μπροστά από τα ααα θα μπορούσα να έχω τίποτα η b* όμως και μπροστά από το b θα μπορούσαμε να έχουμε 1 α ή αα .Το ίδιο  και πίσω. Δηλαδή εκτός από την μοναδική εμφάνιση ααα  μπορεί να περιχέουν και εμφανίσεις ενός α ανάμεσα σε b* ή και αα ανάμεσα σε b*η μπορεί να μην περιέχουν άλλες εμφανισης του ααα εκτός από το μοναδικο ααα.Δηλαδη σε κάθε συμβολοσειρα b*αααb* μπορουμε να προσθεσουμε δεξιά και αριστερα από καμια ή μια ή 2  α. Δηλαδη η η κεφραση θα είναι.

L₃ = [(ε+α+αα)b⁺]*b*αααb*[b⁺([(ε+α+αα)]*b*

Δεξιά Το b+ διτοτι πρέπει να είναι τουλάχιστον 1 b για να μην εινοθουν τα α  και γίνουν περισσότερα από 3.

 ------------------

Τώρα μπορούμε να σχεδιάσουμε το αυτόματο με τις 4 καταστάσεις του. Την αρχική q0 και τις q1 και q2 όπου η q1 είναι για συμβολοσειρές b ενώ και η q2 για αυτές που τελειώνουν σε α και την q3 που είναι η Κατάσταση Παγίδευσης (καταβόθρα)

Η αρχική κατάσταση θα δέχετει το α και το b. Από την αρχική κατάσταση εάν δεχθούμε b τότε θα μεταβούμε στην κατάσταση q1. Στην κατάσταση q1 το αυτόματο «απαντά» - αναγνωρίζει  πως η συμβολοσειρά  ανήκει στο αλφάβητο και είναι κατάσταση αποδοχής .Από την q1 ανεξάρτητα από το πληθος3  b που δεχόμαστε παραμένουμε στην q1 όταν δεχθούμε το πρώτο  α θα μετάβουμε στην q2 που και η q2 είναι κατάσταση αποδοχής.

 Από την αρχική κατάσταση εάν δεχθούμε το χαρακτήρα α τότε θα μεταβούμε στην κατάσταση q2 που είναι κατάσταση αποδοχής. Έπειτα από την q2 εάν δεχθούμε οποιαδήποτε χαρακτήρα είτε α είτε b τότε θα μεταβούμε στην κατάσταση q3. Στην κατάσταση q3 ότι και να δεχθούμε παραμένουμε εκεί δηλαδή εάν μεταβούμε στην κατάσταση q3 τότε το αυτόματο δεν αναγνωρίζει και η συμβολοσειρά που θα δεχτεί δεν ανήκει στον αλφάβητοι της Lα.

< 2>

 Βλέποντας το αυτόματο και τροφοδοτώντας το Μ_β αυτόματο με λέξεις για να διαπιστώσουμε την συμπεριφορά του.

1.)   bbb…ba(a+b)*

2.)   baa…ab(a+b)*

3.)   (ba)..(ba)b…ba(a+b)*

4.)   (ba)..(ba)a…ab(a+b)*

5.)   aa...ab(a+b)*

6.)   abb..ba(a+b)*

7.)   (ab)..(ab)a..ab(a+b)*

8.)   (ab)…(ab)b…ba(a+b)*

Παραπάνω είναι ενδεικτικές τιμές για να δούμε πως συμπεριφέρετε το αυτόματο.

Συμβολίζουμε ΄…’  όταν επαναλαμβάνετε το ίδιο σύμβολο (βάζουμε παρένθεσή για την ομάδα συμβόλων που επαναλαμβάνετε . Ακόμα στην κατάσταση q5 παρατηρούμε είναι κύκλος  για αποιοδηποτε σύμβολο του αλφάβητου α ή β και επειδή είναι τελική κατάσταση που μεταβούμε  ερχόμενοι από άλλες μεταβάσεις , σε κάθε συμβολοσειρά στο τέλος μπορούμε να προσθέσουμε (α+β)*.

Καταλήγουμε στην έκφραση

[b+(ab)⁺)(ab)*(b⁺a)(a+b)*]+ [a+(ab)⁺)*(ba)*(a⁺b)(a+b)*] έκφραση2

Παρατηρούμε  το αυτόματα για να μετάβουμε στην q3 χρειάζεται bb έπειτα όσα b και να πάρουμε μένουμε στην q3 είναι δηλαδή bb⁺και μεταβαίνουμε  στην τελική κατάσταση q5 με α δηλαδή συνολικά bb⁺a. Στην τελική κατάσταση μπορούμε να δεχθούμε και (α+β)*. Αντίστοιχα το ιδιο ισχύει και για την q4 για το σύμβολα α δηλαδή θα είναι αα⁺b και στο τέλος (α+β)*

Στην q1 μεταβαίνουμε  με b αλλά και με αb μάλιστα το αβ μπορεί να επαναλαμβάνεται δηλαδή θα μπορούσε να είναι [b+(ab)⁺] αντίστοιχα και για το a: [a+(ba)⁺]. Το κάθε χρώμα δηλώνει και το διαφορετικό μονοπάτι προς την κατάσταση q5. Τελικά θα σχηματίσουμε την εκφραση2 ενώνοντας τα 2 διαφορετικά(χρωματισμένα )  μονοπάτια προς την q5 με το + διότι αποτελούν διαφορετικές επιλογές για να φθάσουμε στην q5.

< 3>

Παρατηρούμε ότι η αρχική κατάσταση είναι η q0. Η q0 είναι και η τελική κατάσταση  και επειδή είναι και αρχική κατάσταση σημαίνει πως το κενό ανήκει στο αλφάβητο της που υποστηρίζει το αυτόματα.

   Δοκιμάζουμε το αυτόματο Μγ με λέξεις:

1.      (ab)..(ab)

2.      (aabb)… (aabb)

3.      a(ab)...(ab)b

Βλέπουμε πως η κατάσταση q1 είναι κατάσταση παγίδα και εάν μετάβουμε σε αυτήν την κατάσταση δεν μπορούμε να πάμε στην τελική κατάσταση.

Το κείνο ανήκει στο αλφάβητο

Δηλαδή στην  έκφραση πρέπει να δεσμεύσουμε ότι ξεκινά με α και ότι τελειώνει με bκαι το αβ επαναλαμβάνετε και όλα τα παραπάνω να επαναλαμβάνονται.

Επομένως η έκφραση είναι.

(a(ab)*b)*