9.2 Ορισμός context free γραμματικών και των γλωσσών τους

Ορισμός 9.2   Μια context free γραμματική $G$ πάνω από ένα αλφάβητο $\Sigma$ (τα τερματικά σύμβολα) είναι μια πεπερασμένη συλλογή από

• μη τερματικά σύμβολα, που συνήθως τα συμβολίζουμε με κεφαλαία λατινικά γράμματα, και που περιλαμβάνουν το διακεριμένο σύμβολο $S$ (αρχικό μη τερματικό σύμβολο)
• κανόνες παραγωγής $X \to w$, όπου $X$ είναι ένα μη τερματικό σύμβολο και $w$ είναι μια λέξη από γράμματα του $\Sigma$ και μη τερματικά σύμβολα (η $w$ μπορεί να είναι και η κενή λέξη).

Αν $G$ είναι μια Context Free Grammar(CFG), Context Free Γραμματική, και $w$.$v$ είναι δύο λέξεις από τερματικά ή μη τερματικά σύμβολα, τότε γράφουμε

$$w \overset{G}{\Rightarrow} v$$

αν με χρήση ενός κανόνα παραγωγής $X \to \alpha$ μπορεί να προκύψει η λέξη $v$ από τη λέξη $w$. Αυτό σημαίνει ότι αντικαθιστούμε μια εμφάνιση του μη τερματικού συμβόλου $X$ στη λέξη $w$ με τη λέξη $\alpha$ (που απαρτίζεται από τερματικά και μη τερματικά σύμβολα) και με την αντικατάσταση αυτή προκύπτει η λέξη $v$.

Για παράδειγμα, αν $G$ είναι η γραμματική που ορίσαμε παραπάνω τότε ισχύει

$$x+S \overset{G}{\Rightarrow} x+(S)$$

μια και από την αριστερή λέξη προκύπτει η δεξιά αν χρησιμοποιηθεί ο κανόνας 2.

Ορίζουμε επίσης

$$w \underset{*}{\overset{G}{\Rightarrow}} v$$

να σημαίνει ότι υπάρχει πεπερασμένη ακολουθία λέξεων $v_1,\ldots,v_n$ ώστε

$$w \overset{G}{\Rightarrow} v_1 \overset{G}{\Rightarrow} \cdots \overset{G}{\Rightarrow} v_n \overset{G}{\Rightarrow} v,$$

ότι δηλ. η λέξη $v$ μπορεί να προκύψει από τη λέξη $w$ με επανειλημμένη χρήση των κανόνων παραγωγής της $G$. Στην παραπάνω γραμματική για τις εκφράσεις ισχύει, για παράδειγμα,

$$S \underset{*}{\overset{G}{\Rightarrow}} (S+S)$$

αφού μπορούμε από τη λέξη $S$ να πάμε στη λέξη $(S+S)$ εφαρμόζοντας πρώτα τον κανόνα 3 και μετά τον κανόνα 2.

Έχοντας στα χέρια μας τον συμβολισμό αυτό μπορούμε εύκολα να ορίσουμε πλέον ποια είναι η γλώσσα που αντιστοιχεί σε μια λέξη (από τερματικά ή μη σύμβολα).

Ορισμός 9.3   Αν $G$ είναι μια CFG και $w$ μια λέξη από τερματικά ή μη τερματικά σύμβολα της $G$ τότε η γλώσσα της $w$ ορίζεται ως

$$L(w) = L_G(w) = {\left\{{x\in\Sigma^*:   w \underset{*}{\overset{G}{\Rightarrow}} x}\right\}}.$$

Απαρτίζεται δηλ. η $L(w)$ από εκείνες τις λέξεις χωρίς μη τερματικά σύμβολα που μπορούν να παραχθούν σε πεπερασμένο πλήθος βημάτων από τη λέξη $w$ με τους κανόνες παραγωγής της $G$.

Τέλος ορίζουμε την γλώσσα της $G$.

Ορισμός 9.4   Αν $G$ είναι μια CFG η γλώσσα $L(G)$ ορίζεται να είναι η γλώσσα $L(S)$. Μια γλώσσα $L$ λέγεται Context Free Language (CFL), Context Free Γλώσσα, αν είναι η γλώσσα κάποιας context free γραμματικής.

Είναι δηλ. η γλώσσα της $G$ όλες οι λέξεις του $\Sigma^*$ που παράγονται από το αρχικό μη τερματικό σύμβολο $S$.

Θα χρησιμοποιούμε συνήθως τη συντομογραφία

$$X \to w_1 \vert w_2 \vert \ldots \vert w_n$$

για να υποδηλώσουμε μια ομάδα από κανόνες παραγωγής

$$X \to w_1, X \to w_2, \ldots, X \to w_n,$$

με το ίδιο αριστερό μέλος.

Άσκηση 9.1   Ποια είναι η γλώσσα της γραμματικής με κανόνες $S \to \epsilon \vert 0 S 0 \vert 1 S 1$;

Άσκηση 9.2   Δώστε μια CFG για τη γλώσσα ${\left\{{0^n1^n:  n=1,2,\ldots}\right\}}$.

Άσκηση 9.3   Ανατρέξτε πίσω στον ορισμό του τι είναι κανονική έκφραση. Αν σταθεροποιήσουμε το αλφάβητο σε, ας πούμε, $\Sigma = {\left\{{a, b}\right\}}$, δώστε μια CFG για τη γλώσσα των κανονικών εκφράσεων πάνω από το $\Sigma$.