בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. ענו על שני הסעיפים.
לפניכם שתי טענות (1)–(2) בנוגע לשפות L1, L2 שמעל הא"ב {a, b}. בעבור כל טענה, ציינו אם היא נכונה או לא נכונה. אם הטענה נכונה — נמקו מדוע; ואם היא לא נכונה — הביאו דוגמה נגדית. אין קשר בין הטענות.
(1) אם L1, L2 הן שפות לא רגולריות, בהכרח L1 ∩ L2 היא שפה לא רגולרית.
(2) L1^n · L2^n תמיד שווה ל-(L1 · L2)^n.
נתונה השפה L מעל הא"ב {a, b, c}:
L = { w | (#a(w) + #c(w)) הוא מספר זוגי, והרצפים ab ו-bc אינם מופיעים ב-w }
כאשר #a(w) ו-#c(w) מציינים את מספר המופעים של האותיות a ו-c במילה w. דוגמה למילה בשפה L: cba (סכום מופעי a ו-c הוא 2 — זוגי, והרצפים ab, bc אינם מופיעים).
לפניכם חמש מילים. בנוגע לכל אחת מהן ציינו אם המילה שייכת לשפה L או לא, ונמקו:
cbbba, baa, ε (המילה הריקה), aab, aaccc
בנו אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L.
בשאלה זו שני סעיפים, א–ב, שאין ביניהם קשר. ענו על שני הסעיפים.
לפניכם שתי טענות (1)–(2) בנוגע לשפות L1, L2 שמעל הא"ב {a, b}. בעבור כל טענה, ציינו אם היא נכונה או לא נכונה. אם הטענה נכונה — נמקו מדוע; ואם היא לא נכונה — הביאו דוגמה נגדית. אין קשר בין הטענות.
(1) אם L1, L2 הן שפות לא רגולריות, בהכרח L1 ∩ L2 היא שפה לא רגולרית.
(2) L1^n · L2^n תמיד שווה ל-(L1 · L2)^n.
נתונה השפה L מעל הא"ב {a, b, c}:
L = { w | (#a(w) + #c(w)) הוא מספר זוגי, והרצפים ab ו-bc אינם מופיעים ב-w }
כאשר #a(w) ו-#c(w) מציינים את מספר המופעים של האותיות a ו-c במילה w. דוגמה למילה בשפה L: cba (סכום מופעי a ו-c הוא 2 — זוגי, והרצפים ab, bc אינם מופיעים).
לפניכם חמש מילים. בנוגע לכל אחת מהן ציינו אם המילה שייכת לשפה L או לא, ונמקו:
cbbba, baa, ε (המילה הריקה), aab, aaccc
בנו אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L.