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

L₁ = { כל המילים בהן מספר המופעים של האות a והאות b שווה }

L₂ = { כל המילים בהן מספר הפעמים שהאות a מופיעה לפחות שתי פעמים }

L₃ = L₁ ∩ L₂

(1) כתבו מילה באורך 6 או יותר השייכת לשפה L₁.

(2) כתבו מילה באורך 6 או יותר השייכת לשפה L₂.

(3) הגדירו במילים את השפה L₃.

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

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

• אורך כל המילים בשפה הוא לפחות 2.
• הרצף 000 מופיע לכל היותר פעם אחת בלבד במילה.

✎ דוגמאות למילים בשפה

00, 01010, 101000100

✎ דוגמאות למילים שאינן בשפה

0000, 1, 1000110001

הוכיחו שהשפה L רגולרית. מומלץ להשתמש בתכונות הסגירות.