γλώσσα ανεξάρτητη συμφραζομένων

Έστω η γλώσσα ανεξάρτητη συμφραζομένων L = { x $ y $ y^R $ x^R | x,yÎ{0, 1}*}, όπου με x^R συμβολίζουμε την αντίστροφη συμβολοσειρά της συμβολοσειράς x.

(A) Να δώσετε γραμματική ανεξάρτητη συμφραζομένων που να παράγει την L.

(Β) Να σχεδιάσετε ντετερμινιστικό αυτόματο στοίβας που να αναγνωρίζει την L. Στη συνέχεια να δώσετε τη λειτουργία του αυτομάτου με είσοδο την συμβολοσειρά (α) 1$$$1 και (β) $0$0$.

(Γ) Με χρήση της γραμματικής του υποερωτήματος (Α), να σχεδιάσετε μη ντετερμινιστικό αυτόματο στοίβας που να αναγνωρίζει την L. [Υπόδειξη: εργαστείτε σύμφωνα με την κατασκευή που δίνεται στην απόδειξη του Θεωρήματος 8.2 του Τόμου Γ΄.] Στη συνέχεια να δώσετε τη λειτουργία του αυτομάτου ώστε να αναγνωρίσει την συμβολοσειρά $$$.