היי, עזרה בבקשה....

[mashaz1]

היי, עזרה בבקשה....

אני צריכה לכתוב אוטומט סופי דרטמיניסתי שמקבל מספרים בינאיריים שמתחלקים ב 5. לא נראה לי שיש הגבלה על אורך המספר, אבל אם צריך להניח אז מספר באורך 8 ביטים. תודה

 

[immortalus]

פתרון + הסבר

טוב, אז הפתרון מצורף בתמונה (סליחה מראש על איך שזה נראה, זה צוייר ב-paint... טוב, עכשיו, מה בעצם הולך שם בתמונה: העקרון שעליו בניתי את האוטומט הוא זכירת שארית החלוקה ב-5. יש את מצב ה-0 (start) ועוד 4 מצבים - מצב לכל אפשרות של שארית חלוקה ב-5. כעת נזכור עובדה חשובה על מספרים בינאריים: הוספת אפס מימין = הכפלה של המספר פי 2 (ואם יש שארית חלוקה, גם שארית החלוקה מוכפלת פי 2) הוספת אחד מימין = הכפלה של המספר פי 2 והוספה של אחד, בסדר הזה. (אם יש שארית חלוקה, היא מוכפלת פי 2, ונוסף לה אחד). עובדה חשובה על שארית החלוקה: היא עובדת במחרב של מודולו n, כלומר קיימים עבורה רק המספרים: 0, 1, 2, ..., n-1 ואם כתוצאה ממכפלה יוצאת שארית חלוקה של m>n אזי השארית היא: m-n*k כאשר k הוא מספר טבעי כזה כך שתוצאת החיסור תהיה קטנה מ-n וגדולה מ-0. במרחב שלנו - שארית מודולו 5, קיימים רק המספרים: 0, 1, 2, 3, 4. שארית חלוקה 9 תהפוך ל- 1*9-5=4 מכאן, קל לראות איך נבנה האוטומט: במצב ההתחלתי (0) שארית החלוקה היא אפס (אפס חלקי כל מספר הוא אפס - מספר שלם). כאשר נוסף ה-1 הראשון, שארית החלוקה הופכת ל-1 (5 חלקי 1 נותן 0 ושארית חלוקה 1) כאשר מוסיפים עוד 0 - מכפילים את המספר פי 2, ושארית החלוקה הופכת ל-2 כאשר מוסיפים עוד 1 - מכפילים פי 2 ומוסיפים אחד - ושארית החלוקה הופכת ל 3=2*1+1 כך בונים את כל האוטומט. שיהיה בהצלחה