9.6 Παραδείγματα PDA

Η γλώσσα $L_1 = {\left\{{0^n1^n:  n=1,2,\ldots}\right\}}$

Η γλώσσα $L_1 = {\left\{{0^n1^n:  n=1,2,\ldots}\right\}}$ είναι context free (η γραμματική είναι: $S \to \epsilon \vert 0S1$). Θα δώσουμε εδώ ένα PDA για τη γλώσσα αυτή. Ισοδύναμα, θα περιγράψουμε το PDA αυτό σα μια συνάρτηση σε python, σύμφωνα με αυτά που είπαμε στην προηγούμενη παράγραφο. Η συνάρτηση αυτή θα μπορεί να χρησιμοποιεί σταθερή σε μέγεθος μνήμη και θα έχει πρόσβαση στη στοίβα μέσω των συναρτήσεων READ(), POP(), PUSH() που ορίσαμε στην προηγούμενη παράγραφο. Τυγχάνει για τη γλώσσα αυτή να μη χρειάζεται ο μη ντετερμινισμός οπότε δε θα χρησιμοποιήσουμε τη συνάρτηση NF().

Το πρόγραμμα-PDA φαίνεται παρακάτω. Η συνάρτηση f επιστρέφει True αν η λέξη (που τη διαβάζουμε με διαδοχικές κλήσεις στη συνάρτηση INP()) ανήκει στην $L_1$ και False αλλιώς. Η στρατηγική της συνάρτησης είναι η εξής. Όσο διαβάζουμε μηδενικά τα σπρώχνουμε πάνω στη στοίβα. Για κάθε άσο που διαβάζουμε πετάμε κάτι από την στοίβα. Επίσης προσέχουμε ποτέ να μη διαβάσουμε 0 μετά που έχουμε διαβάσει κάποιο 1. Αν στο τέλος η στοίβα καταλήξει άδεια δεχόμαστε τη λέξη.

Ότι ακολουθεί το σύμβολο # αποτελεί σχόλιο και δεν είναι τμήμα του προγράμματος.

def f():
	SeenOne = False # Have not seen a 1 yet
	while True:
		letter = INP() # Read next letter
		if letter == 0:
			if SeenOne:
				return False # Reject after having seen a 1
			PUSH(0) # Push 0s onto stack
		elif letter == 1:
			SeenOne = True
			if -1 == READ():
				return False # The stack has emptied prematurely
			POP() # For each 1 pop a 0 from stack
		else:
			if -1 == READ():
				return True # Accept if end of word and empty stack
			else:
				return False # Reject if stack not empty

Παρατηρήστε ότι, πέρα από τη στοίβα, το πρόγραμμα αυτό χρησιμοποιεί πεπερασμένη και προκαθορισμένη μνήμη. Για την ακρίβεια χρησιμοποιεί όλες κι όλες δύο μεταβλητές, τις letter (που χρησιμοποιείται για να κρατάει το επόμενο γράμμα ή -1) και SeenOne (που φροντίζουμε να είναι 0 όσο δεν έχουμε ακόμη δει άσο και μετά να είναι 1). Η μεταβλητή letter παίρνει τρεις διαφορετικές τιμές, αρκούν δηλ. 2 λογικά bits για να την αποθηκεύσουμε (μια και με αυτά κωδικοποιούμε 4 διαφορετικές τιμές), ενώ για τη μεταβλητή SeenOne που παίρνει δύο τιμές αρκεί ένα λογικό bit.

Μια σημαντική παρατήρηση εδώ είναι το παραπάνω PDA δε χρησιμοποιεί τη συνάρτηση NF και άρα πρόκειται για ένα ντετερμινιστικό πρόγραμμα (το NFA ελέγχου είναι στην πραγματικότητα DFA).

Η γλώσσα $L_2 = {\left\{{xx^R:  x\in{\left\{{0,1}\right\}}^*}\right\}}$

Η γλώσσα $L_2 = {\left\{{xx^R:  x\in{\left\{{0,1}\right\}}^*}\right\}}$.$x^R$ είναι η λέξη $x$ γραμμένη ανάποδα) εύκολα φαίνεται ότι είναι context free. Μια CFG γι' αυτήν είναι απλούστατα η

$$S \to \epsilon \vert 0S0 \vert 1S1.$$

Παρακάτω δείχνουμε μια συνάρτηση g() η οποία υλοποιεί ένα PDA για την αναγνώριση της γλώσσας $L_2$. Εδώ χρησιμοποιείται η συνάρτηση NF(), πρόκειται δηλ. για ένα μη ντετερμινιστικό πρόγραμμα. Η στρατηγική είναι η εξής. Μέχρι τη μέση της ανάγνωσης της λέξης σπρώχνουμε τα γράμματα όπως τα διαβάζουμε πάνω στη στοίβα. Από τη μέση και πέρα για κάθε γράμμα που διαβάζουμε από το input πετάμε και ένα γράμμα από τη στοίβα και το συγκρίνουμε με αυτό που διαβάσαμε από το input. (Προσέξτε ότι τα γράμματα θα πεταχτούν από τη στοίβα με αντίστροφη σειρά από αυτή με την οποία γράφτηκαν.) Αν είναι ίδια συνεχίζουμε (μέχρι να τελειώσει το input) αλλιώς απορρίπτουμε τη λέξη.

Η σημαντική παρατήρηση εδώ είναι ότι δεν μπορούμε να ξέρουμε πότε έχουμε φτάσει τη μέση της λέξης εισόδου! Αυτή τη βοήθεια αναλαμβάνει να μας δώσει η συνάρτηση NF(), η οποία μας λέει ακριβώς αυτό. Στο παρακάτω πρόγραμμα κάθε κλήση στην NF() κατά τη διάρκεια της εκτέλεσης του προγράμματος ισοδυναμεί με μια ερώτηση (στο Θεό, αν προτιμάτε) για το αν φτάσαμε τη μέση της λέξης ή όχι. Αν ο Θεός μας βοηθήσει με τη σωστή απάντηση θα δεχτούμε τη λέξη, μόνο όμως αν πρέπει να τη δεχτούμε. Δε μπορεί δηλ. να μας κοροϊδέψει με τρόπο ώστε να δεχτούμε μια λέξη ενώ δε θα έπρεπε (επαναλαμβάνουμε ότι είναι πολύ σημαντική αυτή η ασυμμετρία στα μη ντετερμινιστικά προγράμματα).

def g():
	mid = False # We have not reached the middle of the input yet
	while True:
		letter = INP() # Read next letter
		if not mid:
			mid = (1 == NF(2)) # Is this letter after the middle;
		if not mid: # Have not passed the middle yet
			if letter == -1:
				return False # Premature end of input. Reject
			PUSH(letter) # No, push letter onto stack
			continue # Go back to while loop
		else: # We have passed the middle
			top = READ() # Read top of stack
			if (letter != -1) and (top == -1):
				return False # Empty stack. Reject
			POP() # Stack not empty. Pop top element.
			if top != letter:
				return False # Letters do not match. Reject.
			continue # Letters do match. Keep going.
		if -1 == READ():
			return True # Stack emptied with no problem. Accept.

Η γραμμή του παραπάνω προγράμματος όπου χρησιμοποιείται ο μη ντετερμινισμός είναι η mid = (1 == NF(2)), όπου (αν η μεταβλητή mid δεν έχει ήδη γίνει μια φορά True, οπότε και μένει για πάντα από κει και πέρα) θέτουμε τη μεταβλητή mid σε False ή True με μια κλήση στην NF(2). Όταν η NF(2) επιστρέψει 1 θεωρούμε από κει και πέρα ότι έχουμε περάσει τη μέση, και προσπαθούμε με το πρόγραμμα να δούμε αν, με αυτή την υπόθεση μπορούμε να δεχτούμε τη λέξη.

Το πρόγραμμα αυτό χρησιμοποιεί τρεις μεταβλητές (letter, mid, top) κάθε μια από τις οποίες παίρνει τιμές μέσα στο σύνολο ${\left\{{0,1,-1}\right\}}$ ή στο σύνολο {True, False} οπότε δύο λογικά bits αρκούν για την αποθήκευση κάθε μιας από αυτές.