5.10 Δε, 18/11/02: Θέματα και αποτελέσματα Προόδου

Δείτε εδώ για τα αποτελέσματα της προόδου (άριστα το 30).

Τα θέματα που ρωτήθηκαν ήταν τα παρακάτω 6 προβλήματα (τα πρώτα τρία για τη μισή τάξη και τα υπόλοιπη γα την άλλη μισή).

1. Κατασκευάστε DFA για τις γλώσσες (α) $00^*1^*1$, και (β) ${\left\{{w\in{\left\{{a,b}\right\}}^*:    6 \mid A(w)+2B(w)}\right\}}$, όπου $A(w)$, και $B(w)$ είναι το πλήθος των $a$ και των $b$ στη λέξη $w$ και $x\vert y$ σημαίνει ότι το $x$ διαιρεί το $y$.
2. Δώστε μια κανονική έκφραση για τη γλώσσα που αναγνωρίζει το αυτόματο του Σχήματος 18.

   
   Σχήμα 18. Το Σχήμα για την Άσκηση 2
3. Δείξτε ότι η γλώσσα ${\left\{{(ab)^k(cd)^k:   k\in{\mathbf N}}\right\}}$ δεν είναι κανονική.
4. Κατασκευάστε DFA για τις γλώσσες (α) τις λέξεις του ${\left\{{0,1}\right\}}^*$ που περιέχουν την υπολέξη 0000, και (β) τη γλώσσα που δίνεται από την κανονική έκφραση $10+(0+11)0^*1$.
5. Δώστε μια κανονική έκφραση για τη γλώσσα που αναγνωρίζει το αυτόματο του Σχήματος 19.

   
   Σχήμα 19. Το Σχήμα για την Άσκηση 5
6. Δείξτε ότι η γλώσσα ${\left\{{xx:   x\in{\left\{{0,1}\right\}}^*}\right\}}$ δεν είναι κανονική.