Μετατροπή ΚΕ σε ΠΑ

Επειδή μια γλώσσα μπορεί να εκφραστεί από ένα αυτόματο ή ισοδύναμα από μια κανονική έκφραση, μπορούμε να μετατρέψουμε μια κανονική έκφραση σε αυτόματο και αντίστροφα.

Βασικές ισοδυναμίες

Στη συνέχεια μπορούμε να δούμε τις βασικές ισοδυναμίες μεταξύ μιας κανονικής έκφρασης και ενός πεπερασμένου αυτόματου.

regular expression

Να μετατραπεί η κανονική έκφραση R = ba*b σε πεπερασμένο αυτόματο.

Απάντηση

Για την έκφραση R = ba*b η ακολουθία είναι:

bb, bab, baab, baaab, ...

Ξεκινώντας από την πρώτη συμβολοσειρά bb έχουμε:

regular expression

Να μετατραπεί η κανονική έκφραση R = (a + b)c σε πεπερασμένο αυτόματο.

Απάντηση

Για την έκφραση R = (a + b)c η ακολουθία είναι:

ac, bc

Ξεκινώντας από την πρώτη συμβολοσειρά ac έχουμε:

regular expression

Να μετατραπεί η κανονική έκφραση R = a(bc)* σε πεπερασμένο αυτόματο.

Απάντηση

Για την έκφραση R = a(bc)* η ακολουθία είναι:

a, abc, abcbc, abcbcbc, ...

Ξεκινώντας από την πρώτη συμβολοσειρά a έχουμε:

regular expression

Να μετατραπεί η κανονική έκφραση R = (a + b)*(abb + aa*b) σε πεπερασμένο αυτόματο.

Απάντηση

Για την πρώτη έκφραση R1 = (a + b)* η ακολουθία είναι:

ε, a, b, aa, ab, ba, bb, ...

Και το αντίστοιχο αυτόματα είναι:

regular expression

Για την δεύτερη έκφραση R2 = (abb + aa*b) η ακολουθία είναι:

abb

ή

ab, aab, aaab, ...

Και το αντίστοιχο αυτόματα είναι:

regular expression

Συνδυάζοντας τα δύο παραπάνω έχουμε:

regular expression

Να μετατραπεί η κανονική έκφραση R = 10 + (0 + 11)0*1 σε πεπερασμένο αυτόματο.

Να μετατραπεί η κανονική έκφραση R = 0*1 + 10 σε πεπερασμένο αυτόματο.

Να μετατραπεί η κανονική έκφραση R = 10 + (0 + 11)0* 1 σε πεπερασμένο αυτόματο.

Να βρεθεί η κανονική έκφραση για το παρακάτω πεπερασμένο αυτόματο.

regular expression

Να βρεθεί η κανονική έκφραση για το παρακάτω πεπερασμένο αυτόματο.

regular expression