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

• המילה לא מתחילה ב־ab.
• אם המילה מכילה aa אז היא לא מכילה bb.
• אם המילה מכילה bb אז היא לא מכילה aa.
• המילה חייבת להכיל aa או bb לפחות פעם אחת.

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

⚠ הערה — אילוץ מחייב

אין להוסיף או להוריד מצבים ואין להוריד מעברים מהאוטומט הנתון.

נתונה השפה L מעל הא"ב {a,b,c}:

(1) מהי המילה הקצרה ביותר בשפה L?

(2) האם השפה L רגולרית? נמקו בקצרה.