שאלה 7 במסלול מודלים חישוביים. נתונות שתי שפות מעל הא"ב {0,1}: L1 = {0^k1^n0^m | k,n,m>0, n+m>=k}, ו-L2 = {0^k1^n | n,k>0, n mod 2 = k mod 2}. בסעיף א׳ יש למצוא מילה באורך 6 בכל שפה. בסעיפים ב׳-ג׳ יש להחליט לכל שפה אם היא רגולרית ולבנות עבורה את המודל המתאים: אוטומט סופי דטרמיניסטי לא-מלא אם רגולרית, או אוטומט מחסנית דטרמיניסטי אם אינה רגולרית.

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

אם השפה L1 רגולרית, יש לבנות אוטומט סופי דטרמיניסטי לא מלא שיקבל את מלא השפה. אם השפה אינה רגולרית, יש לבנות אוטומט מחסנית דטרמיניסטי שיקבל את השפה.

אם השפה L2 רגולרית, יש לבנות אוטומט סופי דטרמיניסטי לא מלא שיקבל את מלא השפה. אם השפה אינה רגולרית, יש לבנות אוטומט מחסנית דטרמיניסטי שיקבל את השפה.