שאלה 8 במסלול מודלים חישוביים — שני סעיפים בלתי-תלויים. בסעיף א׳: L1={מספר המופעים של a שווה למספר המופעים של b}, L2={a מופיעה לפחות פעמיים}, L3=L1∩L2, מעל {a,b}. בסעיף ב׳: שפה L מעל {0,1} שבה כל מילה באורך לפחות 2 והרצף "000" מופיע בה לכל היותר פעם אחת — יש להוכיח שהיא רגולרית (מומלץ באמצעות תכונות הסגירות).

כתבו מילה באורך 6 או יותר השייכת לשפה L1.

כתבו מילה באורך 6 או יותר השייכת לשפה L2.

הגדירו במילים את השפה L3.

מהו אורך המילה המינימלי בכל אחת מן השפות?

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

• אורך כל המילים בשפה הוא לפחות 2.
• הרצף 000 מופיע לכל היותר פעם אחת בלבד במילה. דוגמאות למילים בשפה: 00, 01010, 101000100 דוגמאות למילים שאינן בשפה: 0000, 1, 1000110001 הוכיחו שהשפה L רגולרית. מומלץ להשתמש בתכונות הסגירות.