שני סעיפים בלתי-תלויים. בסעיף א׳ נתון שלד של אוטומט סופי דטרמיניסטי (9 מצבים; חלק מהמעברים, סימני הקלט והמצבים המקבלים חסרים) עבור שפה L מעל {a,b} המוגדרת בארבעה תנאים (לא מתחילה ב-ab; aa ו-bb לא יכולות להופיע שתיהן; אחת מהן חייבת להופיע לפחות פעם) — ויש לבנות ולהשלים אותו. בסעיף ב׳ נתונה השפה L={a^(2m) b^(m-1) c | m≥1}: יש למצוא את המילה הקצרה ביותר בה ולקבוע האם היא רגולרית.
אוטומט סופי דטרמיניסטי מלא, חסרי מעברים/סימני קלט/מצבים מקבלים
מצבים q0–q8, מצב התחלתי q0. בשרטוט אין מצבים מקבלים מסומנים ואין סימני קלט על החצים. החצים שבשרטוט:
q0 → q1 → q2 → q3 (מסלול עליון)
q0 → q6 → q7 → q8 → q5 (מסלול תחתון)
q4 — ללא חצים
סעיף א
נתונה השפה L מעל הא"ב {a,b}, שמכילה מילים המקיימות את כל התנאים שלפניכם: המילה לא מתחילה ב-ab; אם המילה מכילה aa אז היא לא מכילה bb; אם המילה מכילה bb אז היא לא מכילה aa; המילה חייבת להכיל aa או bb לפחות פעם אחת. לפניכם אוטומט סופי דטרמיניסטי מלא שמקבל את השפה L. באוטומט חסרים מעברים, סימני קלט ומצבים מקבלים. העתיקו את האוטומט למחברת הבחינה והשלימו אותו כך שיקבל את השפה L. הערה: אין להוסיף או להוריד מצבים ואין להוריד מעברים מהאוטומט הנתון.
סעיף ב(1)-(2)
נתונה השפה L מעל הא"ב {a,b,c}: L={a^(2m) b^(m-1) c | m>=1}. (1) מהי המילה הקצרה ביותר בשפה L? (2) האם השפה L רגולרית? נמקו בקצרה.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.