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