שאלה בנוגע לכלל האפשרויות של כל מצב מסוים

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

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

ברור שלא מאותו האינפוט. אנסה לחדד. אם ישנם שלושה מצבים, ABC. ואינפוט אפשרי של כל ספרה 0-9. אז מתמטית, מצב A יכול לעבור בין שלושה מצבים מאינפוטים שונים. לדוגמה, אם מקבל 1, מחזיר לעצמו, אם מקבל 2 עובר ל B, אם מקבל 3 עובר ל C.
מצב כזה לא נתון באף אחת מהדוגמאות, ואני מנסה להבין אם הוא אפשרי מבחינת המכניזם הבסיסי של האוטומט, או שבהגדרה, כל מצב יכול לעבור בין שני מצבים, ללא קשר למספר המצבים הכללי באוטומט

לא ברור לי כ"כ הנוסח של “מצב יכול לעבור בין יותר משני מצבים”. תוכל להרחיב?

שהאם כל מצב נתון יכול לעבור לכל אחד מכל המצבים האפשריים באוטומט, או שתמיד, כמו בדוגמאות, הוא יכול לעבור רק לשני מצבים מתוך סך האפשרויות.
להמחשה, זאת ההדוגמה השניה שניתנה:
s0: 0 -> s0
s0: 1 -> s1
s1: 1 -> s0
s1: 0 -> s2
s2: 0 -> s1
s2: 1 -> s2

האם זאת גם היתה יכולה להיות אפשרות באוטומט? בהינתן והיה גם קלט אפשרי של 2, לצורך הענין:
s0: 0 -> s0
s0: 1 -> s1
s0: 2 -> s2
s1: 1 -> s0
s1: 0 -> s2
s2: 0 -> s1
s2: 1 -> s2

לייק 1

אה, בוודאי. מצב יכול לעבור לכל כמות סופית של מצבים אחרים, ולא חייב להיות קשר בין כל מצב לבין כל מצב.

2 לייקים

תודה, וקצת חבל שכך…:slight_smile:

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

אם זה לא נכון, מה אני מפספס פה?

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

אוקי אז זה הרבה יותר מובן לי עכשיו. אז בהמשך לזה, אם ניקח את q0 כדוגמא:
0, 3, 6, 9 - מובילים ל Q0
1, 4, 7 - מובילים ל Q2
2, 5, 8 - מובילים ל Q1

אז מה היחסים בין מקבל/לא מקבל לשלושת מצבי המעבר האלה?

אין יחסים, מצב “מקבל” הוא סך הכל מצב שמוקף בשני עיגולים ומסמן שהקלט שהתקבל הוא “טוב”

לייק 1

אוקי, מובן לי עכשיו.

שאלה על התרשים הראשון ששמת - יש שם מצבים שהם בעצם שני מצבים לדוגמה:
q2, qo
ואפילו q1, q1
אני לא מבינה מה זה אומר- חשבתי שכל מצב הוא מצב בודד ויחיד, כלומר אם תתחיל ממצב אחד ותלך מספר צעדים ספציפי תגיע למצב אחר אבל גם הוא מצב ספציפי יחיד.

אז איבדתי קצת את מה שקורה בתרשים הזה. תודה!

לייק 1

תנסי לדמיין את זה כמו כפתור של ווליום, ברדיו ישן. הוא יכול לעבור בין המון מצבים, שכל אחד מהם הוא עוצמה שונה. מספר המצבים האפשריים במכונה, מוגדר על פי הכללים הנתונים בהוראות. נניח לצורך הדוגמה, שישנם רק שני מצבים אפשריים לכפתור. גבוה ונמוך
נניח שאת יכולה ‘לדבר’ עם הכפתור בצבעים. את מגדירה לו שישנם 2 צבעים אפשריים. אלה סוגי הקלט, אשר גם מוגדרים. נאמר אדום וצהוב.
עכשיו, הכפתור הזה ממש ממש עצלן. לא מגדיל ראש. והוא לא עושה כלום בלי שיגידו לו… אז כשאת נותנת לו צבע, נאמר אדום, את צריכה גם לומר לו בדיוק מה לעשות איתו. אם הוא בנמוך, האם האם עליו לעבור לגבוה, או להישאר בנמוך? ואם הוא בגבוה כשהוא מקבל אדום? מה עליו לבצע? אותו הדבר עבור הצבע הצהוב.
אלה הם ה- transitions המוגדרים בהוראות. כללי המעבר בין המצבים, על פי סוגי הקלט האפשריים, שגם הם מוגדרים בהוראות.
בהוראות גם מוגדר, מתוך סך כל המצבים, איזה מהמצבים הם ‘מנצחים’ ואילו ‘מפסידים’. אם בסיום ההוראות, הכפתור נמצא על מצב שמוגדר ‘מנצח’, אז זאת התוצאה. אם על מצב שמוגדר ‘מפסיד’, אז זאת התוצאה. תחשבי על זה רק כשם. אין לזה משמעות מבחינת כתיבת התרגיל, מעבר לזה שהתוצאה צריכה לצאת בהדפסה
מקווה שעזרתי ולא סיבכתי :slight_smile:

לייק 1

עוד דרך לחשוב על זה (אולי) היא כמו כיוון דרך : נניח שיש N משבצות על לוח משחק (זה המצבים שלנו). אני נותת הוראות שהן צעדים - צפון, דרום, מזרח מערב - אז ‘צעד אחד צפונה’ מעביר ממשבצת מס’ 1 למשבצת מס’ 2 שנמצאת בדיוק מצפון למשבצת מס’ 1, אבל מ2 ל3, מ 3 ל 4, ומ4 ל 1. כלומר - ההוראה זהה, אבל הביצוע תלוי במשבצת שאני עומדת עליה כרגע. מתחילים במשבצת מסוימת , ואחרי כמות מסוימת של צעדים ניצחתי רק אם עכשיו אני במשבצת ‘הנצחון’ (המקבלת). כל המשבצות האחרות באסה.

אם זאת תשובה אליי- אז הבנתי את כל זה בלי בעיה. ואוקי עכשיו הסתכלתי שוב על התרשים הראשון והבנתי שבעצם אין בעיה- בכל התרגיל הזה יוצאים משני מצבים, הולכים כמה צעדים ומגיעים לשני מצבים. זה לא שמגיעים ממצב אחד לשני מצבים. סבבה. תודה על ההסברים! אני חושבת שהם יכולים להיות מאד יעילים לאנשים שהתחילו עם התרגיל ולא הבינו לגמרי מה צריך לעשות שם.

לייק 1

להצעתך:

מוסיפה פה מילות מפתח

מחברת 6 - Leveraging Simple Dictionaries

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

לא יודעת אם יש אפשרות לערוך את שורת הנושא

לייק 1