5.13 Σά, 8/2/03: Θέματα και αποτελέσματα Τελικού Διαγωνίσματος

Δείτε εδώ τους τελικούς βαθμούς του μαθήματος.

Τα θέματα που ρωτήθηκαν ήταν τα παρακάτω 6 προβλήματα (2 ώρες διάρκεια).

1. Κατασκευάστε DFA για τις γλώσσες (α) τις λέξεις του ${\left\{{0,1}\right\}}^*$ που περιέχουν την υπολέξη 0101 (β) ${\left\{{w\in{\left\{{a,b}\right\}}^*:    5 \mid 2A(w)+3B(w)+1}\right\}}$, όπου $A(w)$, και $B(w)$ είναι το πλήθος των $a$ και των $b$ στη λέξη $w$ και $x\vert y$ σημαίνει ότι το $x$ διαιρεί το $y$.
2. Δείξτε ότι η γλώσσα ${\left\{{a^kb^k:   k\in{\mathbf N}}\right\}}$ δεν είναι κανονική.
3. Αν $L \subseteq \Sigma^*$ είναι μια γλώσσα η σχέση $R_L$ ορίζεται ως: $x R_L y$ αν και μόνο αν για κάθε $z \in \Sigma^*$ έχουμε
   $$xz \in L \Leftrightarrow yz \in L,$$
   δηλ. τα $xz$, $yz$ είτε ανήκουν και τα δυο στην $L$ είτε κανένα. Δείξτε ότι η σχέση $R_L$ είναι σχέση ισοδυναμίας.
4. Δώστε μια context-free γραμματική για τη γλώσσα $(01^*0^*1)^+$.
5. Δείξτε ότι η γλώσσα ${\left\{{xx:  x\in{\left\{{0,1}\right\}}^*}\right\}}$ δεν είναι context free.
6. Δείξτε ότι το σύνολο των προγραμμάτων $\pi$ τα οποία δεν τερματίζουν δεν είναι αναδρομικά απαριθμήσιμο. (Μπορείτε να χρησιμοποιήσετε το ότι το halting problem δεν είναι αλγοριθμικά αποφασίσιμο.)