הא"ב הוא A ו B , והשפה היא שפת כל המילים שבהן מספר האותיות A מתחלק ב-3 עם שארית 1 וגם מספר האותיות הכולל זוגי (AABBBAA, למשל , אינה בשפה, אך AABBBAAB נאמצת בפשה).

תודה מראש.

כן, ומה אתה צריך? דקדוק? אוטומט?

לא פשוט בכלל.

ישבתי על זה לא מעט זמן.

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

ואינם מתקבלים (בעיות באוטמט שלי).

לא ממש יצא לי לבדוק כי יצא לי הראש מרוב מחשבה על זה יותר מידי זמן.

הינה :

נא לא להתייחס לB למעלה בצד שמאל (ענייני עצלנות).

זה נראה לי כמו מכפלה של שני אוטומטים (יותר קל לחשוב על זה ככה, והרבה יותר קל לבדוק)

נכון

הדרך הפשוטה ביותר לעשות את זה (והיא די פשוטה) היא לעשות חיתוך של שני אוטומטים (אני חושב שלזה גם התכוון Boomerang) :

אחד של המילים שבהן מספר האותיות A מתחלק ב-3 עם שארית 1

ואחד של מילים שבהן מספר האותיות הכולל זוגי.

בבקשה, תעשה.

אתה חושב שלא ניסתי?

עשיתי אוטמוט אחד שהוא המילים שA מתחלק ב3 עם שארית אחד

ואוטומט שמספר המילים זוגי. את שני האוטומטים האלה קל מאוד מאוד לעשות,

ולא צריך לחשוב עליהם יותר מדקה.

מה שקשה זה לשלב את הקלט B בכל מצב נתון!

ולחשוב על העניין שB יכול להביא למצב מקבל ויכול גם להרוס מצב מקבל.

ניסתי גם לבנות אוטומט (א"ב A בלבד) שמקבל את המילים שאורכם זוגי

ומספר האותיות של הA מתחלק ב3 עם שארית אחד.

ואז אוטומט למילים זוגיים.

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

לכן בניתי אוטומט ישירות לשאלה, אפילו שבהתחלה באמת הלכתי לפי השיטה לפצל את זה ל2 בעיות ולעשות

אחר כך איחוד בינהם.

זה לא חיתוך, ולא איחוד - זו מכפלה בין האוטומטים.

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

באוטומט מכפלה, כל מצב הוא זוג סדור של מצב מהאוטומט הראשון ומצב מהאוטומט השני, לכן מספר המצבים הוא מכפלה של מספר המצבים בשני האוטומטים.

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

המצבים המקבלים הם אלה ששני הרכיבים שלהם הם מצבים מקבלים.

לא למדתם את זה ב- 5 יחידות?

נכון, צודק במה שאמרת.

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

בכל מקרה, בניתי את האוטומט בחלק אחד ישירות לשאלה.

צודק... צריך להתחיל לרענן את החומר

(btw עוד לא עשיתי את הבחינה של ה2 יחידות האחרונות, אני עכשיו ב-י"א. למדתי את רוב החומר לבד בשנה שעברה והייתי אמור לגשת לכל ה-5 כבר בכיתה י', אבל בסוף לא היה לי זמן לעשות את זה. אז עכשיו, כמו בשנה שעברה, אני יכול לא להכנס לשעורים )

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

הנה השרטוט שלי (סליחה על האיכות):

מצב התחלתי q00 מצב מסיים q10

הספרה הראשונה (0/1/2) מציינת את השארית של חלוקת מס' ה-A ב-3, הספרה השניה (0/1) מציינת את הזוגיות (0 אם מס' האותיות הכולל זוגי, 1 אם אי זוגי).

החץ הכפול ( <--> ) מסמן שני חצים, אחד בכיוון ימין ואחד בכיוון שמאל, שניהם עבור האות B (פשוט לא רציתי להעמיס על הציור).