next up previous contents
Next: 5.14 Σεπτέμριος Up: 5 Ημερολόγιο Μαθήματος (Διδακτικές Previous: 5.12 Υπολογισιμότητα   Contents

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^*$ έχουμε

    $\displaystyle 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 δεν είναι αλγοριθμικά αποφασίσιμο.)



Mihalis Kolountzakis 2003-09-04