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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\displaystyle 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$.

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

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

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

$\displaystyle 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$.

Mihalis Kolountzakis 2015-11-28