Διαφορά κανονικών γλωσσών

Έστω δύο κανονικές γλώσσες L₁, L₂. Θα αποδείξουμε ότι η διαφορά τους L = L₁ ∖ L₂ είναι επίσης κανονική γλώσσα.

Η ιδέα

Στην πραγματικότητα δεν υπάρχουν πολλά να αποδείξουμε. Για τη διαφορά δύο συνόλων ισχύει η ακόλουθη σχέση:

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

όπου L₂′ είναι το συμπλήρωμα της γλώσσας L₂. Από τα κεφάλαια για την τομή κανονικών γλωσσών και για το συμπλήρωμα κανονικής γλώσσας γνωρίζουμε ότι οι κανονικές γλώσσες είναι κλειστές ως προς αυτές τις δύο πράξεις. Αυτό σημαίνει ότι μπορούμε να κατασκευάσουμε αυτόματο που αποδέχεται την τομή γλωσσών και αυτόματο που αποδέχεται το συμπλήρωμα μιας γλώσσας. Μπορούμε λοιπόν να χρησιμοποιήσουμε αυτά τα αυτόματα για να κατασκευάσουμε αυτόματο που θα αποδέχεται τη γλώσσα L₁ ∩ L₂′, η οποία είναι ταυτόχρονα η γλώσσα L₁ ∖ L₂.

Παράδειγμα

Έστω το αυτόματο A₁, που αποδέχεται όλες τις λέξεις που περιέχουν άρτιο πλήθος μονάδων:

και το αυτόματο A₂, που αποδέχεται τις λέξεις που περιέχουν περιττό πλήθος μηδενικών:

Θα κατασκευάσουμε το αυτόματο που θα αποδέχεται τη διαφορά αυτών των γλωσσών. Χρειαζόμαστε λοιπόν το αυτόματο A₂′, που θα είναι το συμπλήρωμα του αυτομάτου A₂. Απλώς εναλλάσσουμε τις τελικές με τις μη τελικές καταστάσεις:

Τώρα απομένει να κατασκευάσουμε το αυτόματο A, που θα αποδέχεται την τομή των γλωσσών L(A₁) και L(A₂′):

Πηγές

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools