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

בניית אוטומט מחסנית

דגנית מורן

 

שאלה 1

בנה אוטומט מחסנית המקבל את השפה L מעל הא"ב {a,b}:

L= {anbk½k=ndiv2, n,k ³ 0}

פתרון

האוטומט יעבוד עפ"י האלגוריתם הבא:

על כל אות a שניה שנקראת הוא יכניס אות למחסנית (תוך סימון התחתית). אם מספר האותיות a שנקראו (שנסמנו ב-n) זוגי, יוכנסו למחסנית בדיוק n/2 אותיות. אם n אי זוגי יוכנסו למחסנית (n-1)/2. אם כך, בכל מקרה יכנסו למחסנית ndiv2 אותיות. לכן עם כל אות b שנקראת תישלף אות מהמחסנית ועם התרוקנותה יעבור האוטומט למצב מקבל. א"ב הקלט הוא כמובן {a,b}. א"ב המחסנית הוא {S,A}.

לאוטומט חמישה מצבים.

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

q1 – זוכר כי נקרא עד כה מספר אי זוגי של אותיות a.

q2 – זוכר כי נקרא עד כה מספר זוגי של אותיות a.

q3 – זוכר כי נקראו אותיות b שמספרן קטן מ- ndiv2, כאשר n הוא מספר האותיות a שנקראו לפניהן.

q4 – זוכר כי נקראו אותיות b שמספרן שווה ל- ndiv2, כאשר n הוא מספר האותיות a שנקראו לפניהן. גם זהו מצב מקבל.

אלו המעברים:

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

(q0,a,^,q1,ε)

קריאת a שניה –

(q1,a,^,q2,S)

קריאת a שלישית –

(q2,a,S,q1,S)

קריאת a רביעית – 

(q1,a,S,q2,SA)

קריאת a אי זוגית, חמישית ויותר –

(q2,a,A,q1,AA)

קריאת a זוגית, שישית ויותר – 

(q1,a,A,q2,AA)

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

(q1,b,S,q4,ε)

קריאת b ראשונה, כשלפניה נקרא מספר אי זוגי וגדול מ-1 של אותיות a

(q1,b,A,q3,ε)

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

(q2,b,S,q4,ε)

קריאת b ראשונה, כשלפניה נקרא מספר זוגי וגדול מ-2 של אותיות a

(q2,b,A,q4,ε)

קריאת b שניה ויותר, כאשר לפניה נקראו n אותיות a, ומספר האותיות b שנקראו קטן מ- ndiv2

(q3,b,A,q3,ε)

קריאת b שניה ויותר, כאשר לפניה נקראו n אותיות a, ומספר האותיות b שנקראו הוא ndiv2

(q3,b,S,q4,ε)

 

חזרה

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

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