PDA

צפה בגרסה המלאה : שאלה יפה במודלים



12orel122
04-06-2012, 17:27
נתונה מחרוזת אינסופית: . . . 3123123123123 . . .
א. בנה אוטומט סופי דטרמיניסטי מעל הא"ב { 1 , 2 , 3} , המקבל את כל המילים
באורך אי–זוגי שכל אחת מהן היא תת–מחרוזת של המחרוזת הנתונה.
אני הצלחתי ב6 מצבים אם מישהו הצליח בפחות שיגיד לי =]

12orel122
04-06-2012, 17:35
הנה הפתרון שלי מי שרוצה ..
http://up353.siz.co.il/up2/gyq0mj0zdtyo.jpg

elixvx
04-06-2012, 18:30
תת מחרוזת יכולה להתחיל גם ב123 או 231 לא?

elixvx
04-06-2012, 18:55
בנתי ויצא לי 10 מצבים!
רק השאלה יא אם גם ספרה אחת נחשבת לתת מחזורת אי זוגית וצריכה להתקבל?
ואגב זה אוטומט לא מלא, שירד במיוקד.
אפשר גם במלא אבל יהיו עוד מלא חצים למצב "מלכודת".

12orel122
04-06-2012, 21:33
:O
10 מצבים? תראה את הפתרון שלי תגיד מה דעתך..

12orel122
04-06-2012, 21:33
וכן גם ספרה אחת מתקבלת.

imper
24-04-2014, 02:41
עשיתי את זה ב-7 מצבים.
אני חושב שאצלך יש טעות מכיוון שלא לקחת בחשבון מה קורה כאשר הסדר מתערער (למשל המילה: 111). אין לך את המעברים האלה.

מצ"ב הצעת פתרון שלי (מצב המלכודת מסומן כ-trap):
30615

דבר נוסף, אני רוצה להמליץ על כלי חביב בשם jflap (חפש בגוגל) שאיתו אפשר לשרטט בצורה סבירה את האוטומטים.

chenkop
18-07-2015, 20:13
עשיתי את זה ב-7 מצבים.
אני חושב שאצלך יש טעות מכיוון שלא לקחת בחשבון מה קורה כאשר הסדר מתערער (למשל המילה: 111). אין לך את המעברים האלה.

מצ"ב הצעת פתרון שלי (מצב המלכודת מסומן כ-trap):
30615

דבר נוסף, אני רוצה להמליץ על כלי חביב בשם jflap (חפש בגוגל) שאיתו אפשר לשרטט בצורה סבירה את האוטומטים.
קודם כל, האוטומט של אוראל נכון. הוא בנה אוטומט לא מלא (כל האותיות שלא צוינו יישלחו למלכודת). לעומת זאת, האוטומט שלך לא נכון,
המילה 1 בשפה אך האוטומט שלך לא מקבל אותה.
האוטומט המינימלי (לא מלא) המתאר את השפה הנ"ל מכיל 7 מצבים (אוטומט מלא יכיל 8 כמובן..) ונראה כך:
36604

imper
18-07-2015, 22:05
קודם כל אני מאוד שמח שמישהו מצא את הזמן והחשק לחזור אחורה להגיב למשהו שעשיתי לפני למעלה משנה, אז שאפו.
לגבי התשובה שלי עצמה, עושה רושם שאכן יש טעות מפני שמשום מה הסתמכתי על כך שתת המחרוזת מתחילה בהכרח מ-3 וזה לא נכון.

דבר שני, באס"ד יש לרשום את כל המצבים, כולל מצב מלכודת וכמו כן את כל המעברים. בגלל זה משמעות השם שלו (סופי-דטרמיניסטי). אם מדובר באסל"ד אז מצב "תקיעה" שבו אין אפשרויות לאן להתקדם הוא אפשרי. לכן גם הפתרון שלך דורש שדרוג עבור תשובה מלאה.

chenkop
18-07-2015, 22:08
הסופי הכוונה מספר סופי של מצבים ודטרמיניסטי הכוונה החלטי, כלומר שיוצא מכל מצב לא יותר ממעבר אחד עבור כל אות.

imper
18-07-2015, 22:24
לגבי סופי אתה מוכרח באס"ד להעביר גם את חוקי המעבר בין המצבים, אחרת אין דטרמיניזם. כאמור, באסל"ד זה שונה בהגדרה.
אני מניח שהאוטומט הבא עונה לכלל הדרישות.

נ.ב: הדטרמיניזם לא אומר שאין יותר ממעבר אחד עבור כל אות, אלא בדיוק מעבר אחד עבור כל אות.

chenkop
19-07-2015, 14:02
לגבי סופי אתה מוכרח באס"ד להעביר גם את חוקי המעבר בין המצבים, אחרת אין דטרמיניזם. כאמור, באסל"ד זה שונה בהגדרה.
אני מניח שהאוטומט הבא עונה לכלל הדרישות.

נ.ב: הדטרמיניזם לא אומר שאין יותר ממעבר אחד עבור כל אות, אלא בדיוק מעבר אחד עבור כל אות.

"אוטומט סופי דטרמיניסטי לא מלא


אוטומט שבו לכל מצב ולכל אות קלט יהיה מעבר אחד לכל היותר ( או אחד או אף אחד). כלומר,


באוטומט זה מאפשרים קיום משבצות ריקות בטבלת המעברים . יתכן , כי באוטומט כזה, עבור


מצב מסוים ואות קלט מסוימת , לא מותאם מעבר . במצב כזה האוטומט "נתקע" ."

לא סותר את הדטרמיניסטיות שלו, אם אין מעבר לאות מסוימת, ההחלטה היא דחייה. אבל יש החלטה.

imper
19-07-2015, 22:39
"אוטומט סופי דטרמיניסטי לא מלא


אוטומט שבו לכל מצב ולכל אות קלט יהיה מעבר אחד לכל היותר ( או אחד או אף אחד). כלומר,


באוטומט זה מאפשרים קיום משבצות ריקות בטבלת המעברים . יתכן , כי באוטומט כזה, עבור


מצב מסוים ואות קלט מסוימת , לא מותאם מעבר . במצב כזה האוטומט "נתקע" ."

לא סותר את הדטרמיניסטיות שלו, אם אין מעבר לאות מסוימת, ההחלטה היא דחייה. אבל יש החלטה.

אני לא מכיר את ההגדרה הזאת של "אס"ד לא מלא" והיא נראית לי מאוד בעייתית מכיוון שלא מוגדר עבור אס"ד מצב של "היתקעות", בניגוד לאסל"ד, שכן הוא מוכרח לרוץ עד סוף הקלט. בכל מקרה, עבור השאלה הנוכחית היה קל יחסית להשלים את האוטומט ובמידה וזה אכן אפשרי רצוי לעשות זאת בכדי לקבל פתרון מלא.

chenkop
20-07-2015, 00:35
אני לא מכיר את ההגדרה הזאת של "אס"ד לא מלא" והיא נראית לי מאוד בעייתית מכיוון שלא מוגדר עבור אס"ד מצב של "היתקעות", בניגוד לאסל"ד, שכן הוא מוכרח לרוץ עד סוף הקלט. בכל מקרה, עבור השאלה הנוכחית היה קל יחסית להשלים את האוטומט ובמידה וזה אכן אפשרי רצוי לעשות זאת בכדי לקבל פתרון מלא.
במבחן אני דורש אוטומט מלא, אבל פה לא רציתי להרוס את היופי של האוטומט עם קשתות נחתכות :)