שאלה 9 במסלול מודלים חישוביים. שני סעיפים בלתי-תלויים. בסעיף א׳ נתון שלד של אוטומט סופי דטרמיניסטי (9 מצבים; כל הקשתות, סימוני הקלט והמצבים המקבלים חסרים) עבור שפה L מעל {a,b} המוגדרת בארבעה תנאים (לא מתחילה ב-ab; aa ו-bb לא יכולות להופיע שתיהן; אחת מהן חייבת להופיע לפחות פעם) — ויש לבנות ולהשלים אותו. בסעיף ב׳ נתונה השפה L={a^(2m) b^(m-1) c | m≥1}: יש למצוא את המילה הקצרה ביותר בה ולקבוע האם היא רגולרית.
שאלה 9 במסלול מודלים חישוביים. שני סעיפים בלתי-תלויים. בסעיף א׳ נתון שלד של אוטומט סופי דטרמיניסטי (9 מצבים; כל הקשתות, סימוני הקלט והמצבים המקבלים חסרים) עבור שפה L מעל {a,b} המוגדרת בארבעה תנאים (לא מתחילה ב-ab; aa ו-bb לא יכולות להופיע שתיהן; אחת מהן חייבת להופיע לפחות פעם) — ויש לבנות ולהשלים אותו. בסעיף ב׳ נתונה השפה L={a^(2m) b^(m-1) c | m≥1}: יש למצוא את המילה הקצרה ביותר בה ולקבוע האם היא רגולרית.
אוטומט סופי דטרמיניסטי מלא, חסרי מעברים/סימני קלט/מצבים מקבלים -- p-14.png
states q0..q8, start q0, NO accepting states marked, NO edge labels shown. Skeleton edges (topology only, all unlabeled): q0->q1->q2->q3 (top path); q4 isolated (no edges at all); q0->q6->q7->q8->q5 (bottom path).
נתונה השפה L מעל הא"ב {a,b}, שמכילה מילים המקיימות את כל התנאים שלפניכם: המילה לא מתחילה ב-ab; אם המילה מכילה aa אז היא לא מכילה bb; אם המילה מכילה bb אז היא לא מכילה aa; המילה חייבת להכיל aa או bb לפחות פעם אחת. לפניכם אוטומט סופי דטרמיניסטי מלא שמקבל את השפה L. באוטומט חסרים מעברים, סימני קלט ומצבים מקבלים. העתיקו את האוטומט למחברת הבחינה והשלימו אותו כך שיקבל את השפה L. הערה: אין להוסיף או להוריד מצבים ואין להוריד מעברים מהאוטומט הנתון.
נתונה השפה L מעל הא"ב {a,b,c}: L={a^(2m) b^(m-1) c | m>=1}. (1) מהי המילה הקצרה ביותר בשפה L? (2) האם השפה L רגולרית? נמקו בקצרה.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.