9.4 Οι κανονικές γλώσσες είναι και context free

Θεώρημα 9.2   Κάθε κανονική γλώσσα είναι και context free.

Το αντίστροφο φυσικά δεν ισχύει όπως δείχνουν πολλά από τα παραδείγματα που έχουμε δει ως τώρα, π.χ. η γλώσσα ${\left\{{0^n1^n:  n=1,2,\ldots}\right\}}$.

Απόδειξη. Έστω $L$ κανονική γλώσσα. Αυτό σημαίνει ότι υπάρχει μια κανονική έκφραση $r$ για τη γλώσσα. Αρκεί να δείξουμε ότι κάθε κανονική έκφραση περιγράφει μια context free γλώσσα.

Αρχίζουμε από τις απλούστερες κανονικές εκφράσεις και το δείχνουμε σταδιακά για όλες. Κάνουμε δηλ. επαγωγή ως προς το μήκος της κανονικής έκφρασης. Αν η κανονική έκφραση $r$ έχει μήκος 1, τότε είναι αναγκαστικά ένα γράμμα του $\Sigma={\left\{{\alpha_1,\ldots,\alpha_k}\right\}}$, το σύμβολο $\epsilon$ ή το σύμβολο $\emptyset$ (ανατρέξτε πίσω στον Ορισμό 7.19). Αν είναι γράμμα του $\Sigma$ δηλ. $r = \alpha_j$ για κάποιο $j\in{\left\{{1,\ldots,k}\right\}}$, τότε η γλώσσα $L(r)$ είναι το μονοσύνολο ${\left\{{\alpha_j}\right\}}$, το οποίο δίνεται από την CFG $S \to \alpha_j$. Αν $r = \epsilon$ τότε $L(r) = {\left\{{\epsilon}\right\}}$ που δίνεται από την CFG $S \to \epsilon$, και αν $r = \emptyset$ τότε $L(r) = \emptyset$ και αυτό το σύνολο δίνεται από τη CFG $S \to S$, που προφανώς δεν παράγει τίποτα.

Αν τώρα το μήκος της έκφρασης $r$ είναι μεγαλύτερο του 1 τότε, με βάση τον ορισμό των κανονικών εκφράσεων, η $r$ είναι της μορφής

• $r = (st)$, με $s, t$ κανονικές εκφράσεις μικρότερου μήκους. Από την επαγωγική υπόθεση υπάρχουν context free γραμματικές $G_1$ και $G_2$ τέτοιες ώστε $L(G_1) = L(s)$ και $L(G_2) = L(t)$. Για να φτιάξουμε μια CFG για τη γλώσσα $L(r) = L(s)L(t)$ μετονομάζουμε κατ' αρχήν όλα τα μη τερματικά σύμβολα της $G_1$ και της $G_2$ ώστε να είναι διαφορετικά μεταξύ τους και διαφορετικά από $S$, και ονομάζουμε τα δύο αρχικά μη τερματικά σύμβολα σε $S_1$ και $S_2$ για τις $G_1$ και $G_2$ αντίστοιχα. Η CFG για τη γλώσσα $L(r)$ έχει ως κανόνες όλους τους κανόνες της $G_1$ και της $G_2$ συν τον κανόνα $S \to S_1 S_2$, που είναι και ο μόνος κανόνας για το αρχικό μη τερματικό σύμβολο $S$.
• $r = (s+t)$. Όπως και πριν όλα μόνο που ο επιπλέον κανόνας της γραμματικής δεν είναι τώρα ο $S \to S_1 S_2$ αλλά οι δύο κανόνες $S \to S_1 \vert S_2$.
• $r=(s^*)$. Μετονομάζουμε το αρχικό μη τερματικό σύμβολο της CFG για το $s$ σε $S_1$ (ή κάποιο άλλο όνομα αν αυτό υπάρχει ήδη στη γραμματική) και προσθέτουμε τον κανόνα $S \to \epsilon \vert S_1 S$.

$\qedsymbol$

Άσκηση 9.5   Υπάρχει και άλλος τρόπος να δείξουμε ότι κάθε κανονική γλώσσα είναι κανονική. Μπορούμε να δουλέψουμε κατ' ευθείαν πάνω στο DFA ή NFA που αναγνωρίζει τη γλώσσα μας και να φτιάξουμε μέσω αυτού τη γραμματική. Διαλέξτε ένα από τα DFA ή NFA (η δουλειά είναι ουσιαστικά η ίδια) που εμφανίζονται σε αυτές τις σημειώσεις, π.χ. το αυτόματο που αναγνωρίζει τις λέξεις του ${\left\{{0,1}\right\}}^*$ με περιττό πλήθος από μηδενικά και περιττό πλήθος από άσους (Σχήμα 7.1). Αντιστοιχήστε ένα μη τερματικό σύμβολο σε κάθε κατάσταση του αυτομάτου και βρείτε πώς πρέπει να φτιάξετε τους κανόνες παραγωγής ώστε να προκύψει μια CFG που να περιγράφει την ίδια γλώσσα. Διατυπώστε ένα γενικό τρόπο ώστε να πηγαίνετε από DFA ή NFA σε ισοδύναμη (που να περιγράφει την ίδια γλώσσα) CFG, χωρίς να περνάτε από την αντίστοιχη κανονική έκφραση.