מאגר שאלות ותשובות להוראת מודלים חישוביים:

מודלים אלטרנטיביים

ריקה רם

 

שאלה 1

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

למשל, הנה אוטומט עם מערך מונים המקבל את השפה  {anbncnïn³0}:

לאוטומט ארבעה מצבים {q0, q1, q2, q3, q4}. q0 הוא המצב ההתחלתי והמצבים המקבלים הם q0 ו- q4. אלו תפקידי המצבים:

q0 – מצב התחלתי.

q1 – לקריאת אותיות a.

q2 – לקריאת אותיות b.

q3 – לקריאת אותיות c.

q4 – מצב מקבל המציין שוויון. 

א"ב הקלט הוא כמובן {a, b, c}.

אלו מעברי האוטומט:

קריאת a ראשונה –

(q0, a, q1)

קריאת רצף האותיות a 

(q1, a, q1)

קריאת b ראשונה כאשר מספר האותיות b שנקראו (כולל זו)

קטן ממספר האותיות a שנקראו –

(q1, b, (arr[b]<arr[a]) ® q2)

קריאת b ראשונה כאשר מספר האותיות b שנקראו (כולל זו)

שווה למספר האותיות a שנקראו – 

(q1, b, (arr[a]=arr[b]) ® q3)

קריאת b שנייה ויותר כאשר מספר האותיות b שנקראו (כולל זו)

קטן ממספר האותיות a שנקראו – 

(q2, b, (arr[b]<arr[a]) ® q2)

קריאת b שנייה ויותר כאשר מספר האותיות b שנקראו (כולל זו)

שווה למספר האותיות a שנקראו – 

(q2, b, (arr[a]=arr[b]) ® q3)

קריאת c כאשר מספר האותיות c שנקראו (כולל זו)

קטן ממספר האותיות a ו-b שנקראו – 

(q3, c, (arr[c]<arr[b]) ® q3)

קריאת c כאשר מספר האותיות c שנקראו (כולל זו)

שווה למספר האותיות a ו-b שנקראו – 

(q3, c, (arr[c]=arr[b]) ® q4)

 

אוטומט זה הוא דטרמיניסטי.

בנה אוטומט עם מערך מונים שמקבל את השפה {anbmcndm | n,m³0}

 

פתרון

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

לאוטומט שנבנה יהיו עשרה מצבים:

q0 – מצב התחלתי. זהו גם מצב מקבל.

q1 – מצב לקריאת אותיות a.

q2 – מצב לקריאת אותיות b.

q3 – מצב לקריאת אותיות c כאשר נקראו לפניהן אותיות b.

q4 – מצב לקריאת אותיות c כאשר לא נקראו לפניהן אותיות b. 

q5 – מצב לקריאת אותיות d כאשר נקראו לפניהן אותיות a ו- c.

q6 – מצב מקבל המציין שוויון מספר האותיות a ומספר האותיות c שנקראו, כאשר מספר האותיות b ו- d שווה ל- 0.

q7 – מצב מקבל המציין שוויון מספר האותיות a ומספר האותיות c שנקראו, ושוויון מספר האותיות b ומספר האותיות d שנקראו.

q8 – מצב לקריאת אותיות d כאשר לא נקראו אותיות a ו-c.

q9 – מצב מקבל המציין שוויון מספר האותיות d ומספר האותיות b שנקראו, כאשר מספר האותיות a ו-c שווה ל-0. 

א"ב הקלט הוא כמובן {a, b, c, d}.

 

אלו המעברים:

קריאת a ראשונה –

(q0, a, q1)

קריאת a שניה ויותר 

(q1, a, q1)

קריאת b ראשונה כאשר לא נקראו לפני כן אותיות a

(q0, b, q2)

קריאת b ראשונה כאשר נקראה לפניה לפחות a אחת –

(q2, b, q2)

קריאת c ראשונה כאשר נקראו קודם אותיות b

ומספר האותיות c שנקראו (כולל זו)

קטן ממספר האותיות a שנקראו – 

(q2, c, (arr[c]<arr[a]) ® q3)

קריאת c ראשונה כאשר נקראו קודם אותיות b

ולפניהן אות a אחת – 

(q2, c, (arr[c]=arr[a]) ® q5)

קריאת c שנייה ויותר כאשר נקראו קודם אותיות b

ומספר האותיות c שנקראו (כולל זו)

קטן ממספר האותיות a שנקראו –

(q3, c, (arr[c]<arr[a]) ® q3)

קריאת c שנייה ויותר כאשר נקראו קודם אותיות b

ומספר האותיות c שנקראו (כולל זו)

שווה למספר האותיות a שנקראו –

(q3, c, (arr[c]=arr[a]) ® q5)

קריאת c ראשונה כאשר לא נקראו אותיות b

ומספר האותיות c שנקראו (כולל זו)

קטן ממספר האותיות a שנקראו –

(q1,c, (arr[c]<arr[a]) ® q4)

קריאת c ראשונה כאשר לא נקראו אותיות b

ונקראה קודם אות a אחת – 

(q1, c, (arr[c]=arr[a]) ® q6)

קריאת c שנייה ויותר כאשר לא נקראו קודם אותיות b

ומספר האותיות c שנקראו (כולל זו)

קטן ממספר האותיות a שנקראו –

(q4, c, (arr[c]<arr[a]) ® q4)

קריאת c שנייה ויותר כאשר לא נקראו אותיות b

ומספר האותיות c שנקראו (כולל זו)

שווה למספר האותיות a שנקראו –

(q4, c, (arr[c]=arr[a]) ® q6)

קריאת d כאשר נקראו לפני כן אותיות a ו-c

ומספר האותיות d שנקראו (כולל זו)

קטן ממספר האותיות b שנקראו –

(q5, d, (arr[d]<arr[b]) ® q5)

קריאת d כאשר נקראו לפני כן אותיות a ו-c

ומספר האותיות d שנקראו (כולל זו)

שווה למספר האותיות b שנקראו –

(q5, d, (arr[d]=arr[b]) ® q7)

קריאת d ראשונה כאשר לא נקראו לפני כן אותיות a ו-c

ומספר האותיות d שנקראו (כולל זו)

קטן ממספר האותיות b שנקראו 

(q2, d, (arr[a]=0,arr[b]<arr[d]) ® q8)

קריאת d ראשונה כאשר לא נקראו לפני כן אותיות a ו-c

ומספר האותיות d שנקראו (כולל זו)

שווה למספר האותיות b שנקראו 

(q2, d, (arr[a]=0,arr[b]=arr[d]) ® q9)

קריאת d שנייה ויותר כאשר לא נקראו לפני כן

אותיות a ו-c ומספר האותיות d שנקראו (כולל זו)

קטן ממספר האותיות b שנקראו –

(q8, d, (arr[a]< arr[b]) ® q8)

קריאת d שנייה ויותר כאשר לא נקראו לפני כן

אותיות a ו-c ומספר האותיות d שנקראו (כולל זו)

שווה למספר האותיות b שנקראו –

(q8, d, (arr[d]= arr[b]) ® q9)

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים