9.1 Ένας τρόπος περιγραφής απλών αριθμητικών εκφράσεων

Ας υποθέσουμε ότι θέλουμε να ορίσουμε το τι σημαίνει σωστά δομημένη αριθμητική έκφραση. Για να κάνουμε τα πράγματα πιο απλά (χωρίς να χαθεί η ουσία) ας περιοριστούμε σε αριθμητικές εκφράσεις όπου οι μόνες πράξεις είναι η πρόσθεση (+) και ο πολλαπλασιασμός (*), και όπου ισχύουν οι συνηθισμένοι κανόνες για τις παρενθέσεις. Ας υποθέσουμε επίσης ότι οι βασικές ποσότητες που φτιάχνουν μια έκφραση συμβολίζονται όλες με το γράμμα $x$. Για παράδειγμα η έκφραση $x*(x+x)+x$ είναι μια σωστή έκφραση ενώ η $xx+*()$ δεν είναι.

Έχουμε δηλαδή ένα πολύ περιορισμένο αλφάβητο

$$\Sigma = {\left\{{+,*,(,),x}\right\}}$$

και προσπαθούμε να ορίσουμε τη γλώσσα των σωστών εκφράσεων, που είναι ένα κομμάτι του $\Sigma^*$.

Ένας γρήγορος και καθαρός τρόπος να τις ορίσουμε είναι να σκεφτούμε το πώς τις φτιάχνουμε: κολλάμε μαζί, με συγκεκριμένους κανόνες, μικρότερες εκφράσεις και φτιάχνουμε μεγαλύτερες. Δίνουμε έτσι τον εξής ορισμό.

Ορισμός 9.1   Η λέξη $x$ είναι σωστή έκφραση. Επίσης αν οι λέξεις $w$ και $v$ είναι σωστές εκφράσεις, τότε σωστές εκφράσεις είναι επίσης και οι λέξεις $(w)$.$w+v$.$w*v$. Τέλος, σωστές εκφράσεις είναι μόνο οι λέξεις που προκύπτουν από τους άνω κανόνες.

Έτσι η λέξη $x*(x+x)+x$ είναι σωστή έκφραση επειδή οι λέξεις $x$ και $(x+x)+x$ είναι σωστές, και η δεύτερη είναι σωστή επειδή επειδή οι $(x+x)$ και $x$ είναι σωστές και η πρώτη από αυτές είναι σωστή επειδή η $x+x$ είναι σωστή και, τέλος, αυτή είναι σωστή επειδή η $x$ είναι σωστή.

Ορισμοί σαν τον παραπάνω (αλλά και αρκετά πιο περίπλοκοι) κωδικοποιούνται στις λεγόμενες context free γραμματικές. Πριν δώσουμε τον ακριβή ορισμό για αυτές ας πούμε ότι η context free γραμματική που αντιστοιχεί στον παραπάνω ορσιμό είναι η:

1. $S \to x$
2. $S \to ( S )$
3. $S \to S + S$
4. $S \to S * S$

Με το σύμβολο $S$ συμβολίζουμε μια «μεταβλητή» λέξη, η οποία μπορεί να αντικατασταθεί με το δεξί μέλος μιας από τις παραγωγές ( $S \to \ldots$) από τις οποίες απαρτίζεται η γραμματική. Η λογική είναι ότι ξεκινάμε με τη λέξη $S$ και εφαρμόζουμε σε αυτήν συνεχώς κάποιους από τους κανόνες παραγωγής μέχρι να πάρουμε τη λέξη που θέλουμε. Αν αυτό καταστεί εφικτό τότε, και μόνο τότε, η λέξη αυτή θα είναι στην context free γλώσσα που περιγράφεται από την άνω context free γραμματική.

Με την παρακάτω ακολουθία μετασχηματισμών προκύπτει π.χ. η λέξη $x*(x+x)+x$

$S$	$\to$	$S+S$	(κανόνας παραγωγής 3)
	$\to$	$S*S+S$	(κανόνας παραγωγής 4)
	$\to$	$S*(S)+S$	(κανόνας παραγωγής 2)
	$\to$	$S*(S+S)+S$	(κανόνας παραγωγής 3)
	$\to$	$x*(x+x)+x$	(κανόνας παραγωγής 1, τέσσερεις φορές)

Εύκολα βλέπει κανείς ότι με όποιο τρόπο και να χρησιμοποιήσουμε τους κανόνες παραγωγής δε μπορούμε να πάρουμε από την $S$ τη λέξη $xx+*()$.