γλώσσες

(Α) Να δώσετε γραμματική ανεξάρτητη συμφραζομένων για τις παρακάτω γλώσσες (δεν απαιτείται απόδειξη ορθότητας):

1. {aⁱb^j : j = 4i + 2}
2. {w anhkei  {a,b}^* : w = w^R και μετά από κάθε a θα υπάρχει αναγκαστικά ένα b}, όπου με w^R συμβολίζουμε την αντίστροφη της συμβολοσειράς w\

Β) Ορίζουμε το σύνολο s(w) των επιθημάτων του w ως το σύνολο όλων των λέξεων x Î Σ^* για κάθε μία από τις οποίες υπάρχει z Î Σ^* έτσι ώστε w = zx. Για παράδειγμα, s(abba)={abba, bba, ba, a, ε}. Έστω η γλώσσα L = {w Î {a, b}^* : σε κάθε επίθημα (suffix) του w το πλήθος των a είναι τουλάχιστον τόσο όσο και το πλήθος των b (διαφορετικά, "p Î s(w) : #_a(p) ³ #_b(p))}. Σας ζητούνται τα εξής:

1. 1. Να δώσετε πέντε παραδείγματα λέξεων που ανήκουν στην L και να περιέχουν 3 a και 3 b. Η κενή λέξη ανήκει στην L;
   2. Να δώσετε μία γραμματική ανεξάρτητη συμφραζομένων G που να παράγει την L. Για ευκολία, σας δίνουμε τρεις κανόνες και εσείς χρειάζεται να προσθέσετε ακόμα έναν (το ερωτηματικό ?) ώστε η γραμματική να είναι σωστή (δεν απαιτείται απόδειξη ορθότητας).
   S ® ? | bSa | SS | e
   3.      Να περιγράψετε τη φυσική σημασία της γλώσσας L^R = {w^R : w Î L} όπου με w^R συμβολίζουμε την αντίστροφη της συμβολοσειράς w. Έπειτα, να δώσετε μία γραμματική ανεξάρτητη συμφραζομένων G^R που να την παράγει.
   4.      Να δώσετε μία γραμματική ανεξάρτητη συμφραζομένων η οποία να παράγει τη γλώσσα LL^R (συνένωση των δύο γλωσσών).
   (Γ) Έστω η γραμματική G = ({S}, {a, b}, S, R), όπου R = {S ® aSb, S ® bSa, S ® SS , S ® e}.  Να απαντήσετε στα εξής:
   1.      Περιγράψτε τη γλώσσα που παράγεται από την γραμματική G (δεν απαιτείται απόδειξη ορθότητας).
   2.      Είναι η γραμματική διφορούμενη; Να αποδείξετε την περίπτωση στην οποία η απάντησή σας είναι θετική.
   (Δ) Δώστε μία κανονική γραμματική, η οποία να παράγει τη γλώσσα που αναγνωρίζεται από το παρακάτω ντετερμινιστικό πεπερασμένο αυτόματο: