[ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

THMMY.gr > Forum > Μαθήματα Κύκλου Ηλεκτρονικής & Υπολογιστών > 7ο Εξάμηνο > Θεωρία Υπολογισμών και Αλγορίθμων (Moderators: geo66, Elliot Alderson, Prosontas, sassi, Tasos Bot) > [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

0 Members and 2 Guests are viewing this topic.

Pages: 1 2 [3] 4 5 ... 8

Author

Topic: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012 (Read 19188 times)

thessalos

Ανερχόμενος/Ανερχόμενη

Posts: 53

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #30 on: January 24, 2012, 19:29:59 pm »

Στο πρωτο θεμα 2009 η λυση ειναι οτι το αυτοματο που θα φτιαξουμε ειναι το (Μ1ενωση με το Μ2) και παραθεση με το Μ3*?

edit: μονο αυτο θελει ή πρεπει να το αναλυσουμε πιο πολυ, δηλαδη να βρουμε και τα Δ,F,K,s καθε πραξης?


« Last Edit: January 24, 2012, 19:32:06 pm by thessalos »	Logged

nati19

Νεούλης/Νεούλα

Posts: 20

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #31 on: January 24, 2012, 19:39:36 pm »

οκ ευχαριστω!

Το θέμα 4 του 2009 το εχεις κοιταξει?

Με αρχική στο κενό μετα από 2 θέσεις δεξια δεν θα διαβάσει πάλι κενό? ετσι δεν θα φτάσει ποτε στην τελευταία εκφραση. Αλλα μάλλον έτσι οπως το σκέφτομαι δεν ειναι και πολύ σωστο!


	Logged

thessalos

Ανερχόμενος/Ανερχόμενη

Posts: 53

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #32 on: January 24, 2012, 19:55:18 pm »

οταν ξεκιναει η μηχανη το πρωτο R (που δεν εχει κουτακι κατω δεξια) μετακινει την κεφαλη μια θεση δεξια, τοτε ελεγχει αμα στην θεση αυτη υπαρχει κενο, αν δεν υπαρχει τοτε πηγαινει παλι μια θεση δεξια και κανει παλι το ιδιο και κινειται παλι μια θεση δεξια, οποτε τωρα βρισκεται στην εντολη R (που εχει κουτακι κατω δεξια) και σημαινει να παει στο πρωτο κενο που θα βρει απο δεξια... εκει θα γραψει το α(δηλαδη τον χαρακτηρα που βρηκε στην αρχη, οχι αναγκαστηκα α), και θα παει στην επομενη εντολη που ειναι R (που εχει κουτακι κατω δεξια) και θα κινηθει παλι μια θεση δεξια και θα γραψει το β δηλαδη το δευτερο γραμμα που διαβασε...

παραδειγμα ταινιας:
>_dfrefgg_ η κεφαλη ειναι στο πρωτο κενο, η μηχανη θα κινηθει δεξια μια θεση και θα βρει το d (που το αποθηκευει στην μεταβλητη a), στην συνεχεια θα μετακινηθει δεξια και θα αντιγραψει στην μεταβλητη b το f, και θα παει στο πρωτο κενο απο δεξια και θα γραψει d και στο δευτερο f οποτε η ταινια μετα θα ειναι >_dfrefggdf_

το R χωρις κουτακι δεξια σημαινει μονο μετακινηση δεξια, ενω με κουτακι, πηγαινε στο πρωτο κενο χαρακτηρα που θα βρεις...
δεν ξερω ομως αν μπορει στην w να περιεχει κενα...γιατι αν το πρωτο γραμμα ειναι κενο τοτε η μηχανη σταματαει... ολα αυτα τα βρηκα στο βιβλιο σελιδα 252 - 254


	Logged

nati19

Νεούλης/Νεούλα

Posts: 20

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #33 on: January 24, 2012, 20:05:32 pm »

Quote from: thessalos on January 24, 2012, 19:55:18 pm

Συμφωνα με το παράδειγμα 4.1.8 η w περιεχει μόνο μη κενα συμβολα αλλά μπορεί να είναι κενή. Αν υποθέσουμε οτι δεν ειναι κενή τότε θα πάει μια θέση δεξία αι τώρα η κεφαλή θα διαβάζει το w. Εφόσον το w δεν είναι κενό θα πάει άλλη μια θέση δεξια μέσα στη w. αλλα εμείς δεν ξέρουμε το μηκος της w για να δούμε αν θα συνεχίσει. Πρέπει να πάρουμε περιπτώσεις?


	Logged

thessalos

Ανερχόμενος/Ανερχόμενη

Posts: 53

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #34 on: January 24, 2012, 20:09:42 pm »

οταν κοιταξει στην πρωτη θεση της w (συμφωνα) με την α != _ το τε θα προχωρησει παρακατω, αμα η w εχει μηκος 1 τοτε στην δευτερη συνθηκη b != _ τοτε θα βρει κενο και θα σταματησει μονο αν τα δυο πρωτα γραμματα ειναι μη κενα θα συνεχησει... δεν μας ενδιαφερει ποσα γραμματα εχει η w, αρκει να ειναι >= του 2

Αν ειναι κενη τοτε θα σταματησει αμεσως
Αν εχει ενα γραμμα θα το διαβασει αλλα μετα θα σταματησει
Αν εχει δυο γραμματα τοτε θα τα διαβασει και θα παει στο τελευταιο κενο και θα τα γραψει το ενα μετα το αλλο
Αν εχει περισσοτερα του δυο τοτε θα διαβασει τα δυο πρωτα και θα παει στο τελευταιο κενο και θα τα γραψει το ενα μετα το αλλο


« Last Edit: January 24, 2012, 20:25:58 pm by thessalos »	Logged

AZMAGILLIAN

Ανερχόμενος/Ανερχόμενη

Posts: 53

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #35 on: January 24, 2012, 22:43:32 pm »

Εχει κανεις ιδεα για το 2ο θεμα του 2009
αν η L=[w/w ε (0,1)*,w εχει περισσοτερα 1 απο οτι 0] ειναι κανονικη
εγω το λυνω καπως μπακαλιστικα ..πρεπει να υπαρχει λυση χρησιμοποιωντας κλειστοτητα


	Logged

ΚΗΜΜΥ

Επιβεβαρυμένος

Gender:

Posts: 13065

Κ από το Καμμένος...

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #36 on: January 24, 2012, 23:09:30 pm »

Λυση απο το μαθημα: Λες οτι για να ειναι κανονικη πρεπει να την αποδεχεται καποιο ΠΑ. Για την απαριθμηση ομως των 0 κ 1 επρεπε να υπαρχει ενα balance. Αυτο απαιτει μια κατασταση για καθε τιμη, αρα απειρες καταστασεις. Ατοπο, η γλωσσα δεν ειναι κανονικη. (Θ. Αντλησης)


	Logged

thessalos

Ανερχόμενος/Ανερχόμενη

Posts: 53

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #37 on: January 24, 2012, 23:38:15 pm »

ναι ωραια για το συγκεκριμενο παραδειγμα γινεται οπως λες, το εχει και στο βιβλιο σελιδα 128 (για την γλωσσα a^nb^n)... Το θεμα 1 2008 πως λυνεται?


	Logged

AZMAGILLIAN

Ανερχόμενος/Ανερχόμενη

Posts: 53

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #38 on: January 24, 2012, 23:41:40 pm »

Ευχαριστώ!!!
εψαχνα λυση τύπου
Ν.δ.ο. L = {w ∈ {0, 1}*: w έχει ίδιο αριθμό 0 και 1}
δεν είναι κανονική.
L ∩ 0*1* = { 0n 1n : n ≥ 0}, που δεν είναι κανονική.
0*1* κανονική.
Κανονικές γλώσσες κλειστές ως προς τομή.
Άρα L δεν είναι κανονική.


	Logged

ΚΗΜΜΥ

Επιβεβαρυμένος

Gender:

Posts: 13065

Κ από το Καμμένος...

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #39 on: January 25, 2012, 02:57:48 am »

Τι κανει η μηχανη Τuring στο 4ο θεμα του 2009?
(Μη μου πειτε καλα ειναι Tongue

)


	Logged

edenaxas

Εθισμένος στο ΤΗΜΜΥ.gr

Posts: 620

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #40 on: January 25, 2012, 03:11:46 am »

αντιγραφεις τα 2 πρωτα συμβολα στο τελος της w.
η w δεν πρεπει να εχει κενα στην αρχη, ομως αυτο πρεπει να ισχυει εξ ορισμου ετσι κι αλλιως.


	Logged

ΚΗΜΜΥ

Επιβεβαρυμένος

Gender:

Posts: 13065

Κ από το Καμμένος...

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #41 on: January 25, 2012, 03:16:25 am »

Eυχαριστω!

Στο πρωτο του 11 τι θα κανουμε για να βρουμε την G'?


	Logged

edenaxas

Εθισμένος στο ΤΗΜΜΥ.gr

Posts: 620

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #42 on: January 25, 2012, 10:26:29 am »

σελιδα 14 σημειώσεων


« Last Edit: January 25, 2012, 11:03:27 am by edenaxas »	Logged

nati19

Νεούλης/Νεούλα

Posts: 20

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #43 on: January 25, 2012, 11:31:00 am »

Στο θέμα με τα αυτόματα όταν κατασκευάζουμε μη αιτιοκρατικό πρέπει να βάλουμε και ίδιες μεταβάσεις? Δηλαδή όταν διαβάσει b να πάει σε μια κατάσταση q1 μη τελική η σε μια q4 τελική?

Και στο αιτιοκρατικό πρέπει απλά να συμπεριλάβουμε όλες τις πιθανές μεταβάσεις χωρίς να έχουμε διπλές?


	Logged

atalanta

Ανερχόμενος/Ανερχόμενη

Posts: 82

Re: [ Θ. Υ. Α. ]-Επικαιρότητα, απορίες, ασκήσεις 2011-2012

« Reply #44 on: January 25, 2012, 14:28:03 pm »

εχει λυσει κανενας το θεμα 2 του 2008 με την KMC??


	Logged

Pages: 1 2 [3] 4 5 ... 8

Jump to: