לפניכם השפות הרגולריות L₁ ו־L₂ מעל הא"ב {a,b}:

הוכיחו בעזרת תכונות הסגירות של השפות הרגולריות שהשפה L₃ רגולרית.

נתונות השפות הבאות:

✎ דוגמה למילה בשפה L

aaabbcbccddd

• a^z = aaa
• w₁ = bbc
• w_k = bcc
• d^k+1 = ddd

הסבר: מספר תווי a הוא אי זוגי. בין תווי a בתחילת המילה לתווי d בסוף המילה, יש שתי מילים השייכות לשפה L₁, לכן k=2 ובהתאמה מספר תווי d בסוף המילה הוא 3.

כתבו את המילה הקצרה ביותר בשפה L.

נתון אוטומט מחסנית דטרמינסטי חלקי המקבל את השפה L. האוטומט כולל את כל המצבים (כולל סימון מצב מקבל).

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

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

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

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