שאלון על אוטומטים סופיים אי-דטרמיניסטיים

בשאלון זה נבקש מכם לתכנן אוטומטים סופיים אי-דטרמיניסטיים עבור מספר שפות.

נתאר א״ד ע״י ״קוד״ שמורכב מאוסף של שורות:

• אוסף המצבים: Q = {q0, ..., qn}
• אלפבית: Sigma = {s1, ..., sm}
• מצבים התחלתיים: I = {...}
• יחס המעברים: R(q3, s4) = {...}
• מצבים מקבלים: F = {...}

ביחס המעברים ניתן לכלול גם מסעי אפסילון: R(q3, epsilon) = {...}

שימו לב: בכיתה תיארנו את יחס המעברים כאוסף של שלשות. כאשר אנו רושמים R(q,s), כוונתנו היא לקבוצה {p | (q,s,p) ∈ R}.

ניתן לראות דוגמה בשאלה הראשונה, בה נתנו גם את הפתרון.

הערה: דף זה מונגש בצורה בסיסית בלבד. סטודנט שנתקל בבעיות מתבקש לפנות לצוות הקורס.

1. בנו אוטומט מעל הא״ב {a,b} שמקבל את שפת כל המילים בהן לפחות אות אחת מופיעה לפחות פעמיים (שאלה מתרגול 10):

   Q = {q0, qa, qb, qf} Sigma = {a, b} I = {q0} R(q0, a) = {q0, qa} R(q0, b) = {q0, qb} R(qa, a) = {qa, qf} R(qa, b) = {qa} R(qb, a) = {qb} R(qb, b) = {qb, qf} R(qf, a) = {qf} R(qf, b) = {qf} F = {qf}

   בדיקה

2. בנו אוטומט מעל הא״ב {a,b} שמקבל את שפת כל המילים הלא-ריקות שמתחילות ומסתיימות באותה אות:

   בדיקה

3. בנו אוטומט מעל הא״ב {a,b,c} שמקבל את שפת כל המילים הלא-ריקות בהן האות האחרונה מופיעה רק פעם אחת במילה:

   בדיקה

4. בנו אוטומט מעל הא״ב {a,b,c} שמקבל את שפת כל המילים המסתיימות בשתי אותיות זהות:

   בדיקה

5. בנו אוטומט מעל הא״ב {a,b} שמקבל את שפת כל המילים שאורכן מתחלק ב-3, או מספר ה-a-ים בהן זוגי, או מספר ה-b-ים בהן אי-זוגי:

   בדיקה

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

   האלפבית מורכב מכל הספרות ומהסימן x.

   מספר הוא חוקי אם הוא 0, או שספרתו השמאלית ביותר אינה 0. במילים אחרות, איננו מרשים מספרים בסגנון 01.

   דוגמאות למילים חוקיות בשפה: 10, 0x3, 4x5x6.

   בדיקה