Μετατροπή ΚΕ σε ΠΑ
Επειδή μια γλώσσα μπορεί να εκφραστεί από ένα αυτόματο ή ισοδύναμα από μια κανονική έκφραση, μπορούμε να μετατρέψουμε μια κανονική έκφραση σε αυτόματο και αντίστροφα.
Βασικές ισοδυναμίες
Στη συνέχεια μπορούμε να δούμε τις βασικές ισοδυναμίες μεταξύ μιας κανονικής έκφρασης και ενός πεπερασμένου αυτόματου.
Να μετατραπεί η κανονική έκφραση R = ba*b σε πεπερασμένο αυτόματο.
Απάντηση
Για την έκφραση R = ba*b η ακολουθία είναι:
bb, bab, baab, baaab, ...
Ξεκινώντας από την πρώτη συμβολοσειρά bb έχουμε:
Να μετατραπεί η κανονική έκφραση R = (a + b)c σε πεπερασμένο αυτόματο.
Απάντηση
Για την έκφραση R = (a + b)c η ακολουθία είναι:
ac, bc
Ξεκινώντας από την πρώτη συμβολοσειρά ac έχουμε:
Να μετατραπεί η κανονική έκφραση R = a(bc)* σε πεπερασμένο αυτόματο.
Απάντηση
Για την έκφραση R = a(bc)* η ακολουθία είναι:
a, abc, abcbc, abcbcbc, ...
Ξεκινώντας από την πρώτη συμβολοσειρά a έχουμε:
Να μετατραπεί η κανονική έκφραση R = (a + b)*(abb + aa*b) σε πεπερασμένο αυτόματο.
Απάντηση
Για την πρώτη έκφραση R1 = (a + b)* η ακολουθία είναι:
ε, a, b, aa, ab, ba, bb, ...
Και το αντίστοιχο αυτόματα είναι:
Για την δεύτερη έκφραση R2 = (abb + aa*b) η ακολουθία είναι:
abb
ή
ab, aab, aaab, ...
Και το αντίστοιχο αυτόματα είναι:
Συνδυάζοντας τα δύο παραπάνω έχουμε:
Να μετατραπεί η κανονική έκφραση R = 10 + (0 + 11)0*1 σε πεπερασμένο αυτόματο.
Να μετατραπεί η κανονική έκφραση R = 0*1 + 10 σε πεπερασμένο αυτόματο.
Να μετατραπεί η κανονική έκφραση R = 10 + (0 + 11)0* 1 σε πεπερασμένο αυτόματο.
Να βρεθεί η κανονική έκφραση για το παρακάτω πεπερασμένο αυτόματο.
Να βρεθεί η κανονική έκφραση για το παρακάτω πεπερασμένο αυτόματο.
