שאלה באוטומטים

[generala]

שאלה באוטומטים

יש לי שאלה באוטומטים שאני ממש שובר את הראש עליה ולדעתי יותר מדי... אני בטוח שהפתרון טריויאלי מאשר אני חושב. אם נתונים לי 2 אוטומטים A ו-B אשר בקובץ המצ"ב. ואני אמור לבנות ע"י האוטומטים הנ"ל אוטומט שלישי C, המקבל את השפה הרגולרית שהיא ההפרש הסימטרי בין A ל-B. אני אמור להגדיר את האוטומט במדוייק ולהתחשב בזה שמספר מצביו לא יעלה על מספר המצבים המתואר בקובץ.... איך אני בונה את אותו האוטומט ומתחשב בתנאים ? תודה !

 

[אלכס קפלן]

אוטומט מכפלה

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

 

[generala]

../images/Emo36.gif

אתה יכול לתת לי דוגמא ממשית ?

 

[אלכס קפלן]

הנה דוגמה

נגיד שיש לנו שני אוטומטים A, B . לאוטומט A יש שני מצבים a1, a2. לאוטומט B יש שלושה מצבים b1,b2,b3. קבוצת המצבים של אוטומט המכפלה היא { (a1,b1) ; (a1,b2) ; (a1,b3) ; (a2,b1) ; (a2,b2) ; (a2,b3) } פונקצית המעברים של A היא f והפונקציה של B היא g. אז פונקצית המעברים של אוטומט המכפלה מקבלת אות קלט וזוג מצבים של האוטומטים A, B ומסמלצת את קריאת האות בשניהם: (( f(c,qa) ,g(c, qb)) = h(c, (qa,qb ודיר באלאק התפוזבל שלא יהפוך לי את הסוגריים. אגב, אפשר של A, B יהיו אליפביתים שונים ואז האליפבית של אוטומט המכפלה הוא המכפלה הקרטזית של האליפביתים. קבוצת המצבים המקבלים של אוטומט המכפלה זה מה שאתה בוחר לפי מה שמתאים לך. (איך תבחר אות כדי לקבל חיתוך של שתי השפות? ) מקווה שזה עוזר