אוטומטים ושפות פורמליות

מטלת מנחה (ממ"ן) 11
הקורס: 20440 – אוטומטים ושפות פורמליות
חומר הלימוד למטלה: יחידות 2-1
מספר השאלות: 5 משקל המטלה: 2 קודות
סמסטר: ב2020 מועד אחרון להגשה: 2020.3.31
י.ק

אנא שים לב:
מלא בדייקנות את הטופס המלווה לממ"ן בהתאם לדוגמה שלפני המטלות.
העתק את מספר הקורס ומספר המטלה הרשומים לעיל.

הערות:
א. אם"ם הוא סימון מקובל לאם ורק אם.
ב. בחלק מהשאלות תתבקש לבות אוטומט. במקרה שהפתרון מורכב, יש לצרף הסבר מילולי על
על דרך הבייה ועל כוות התשובה. תמיד רצוי להציג אוטומט פשוט וקומפקטי.

(5%) 1 שאלה
תוות השפות הבאות מעל {1,0 :{
5 L { ,001,101,0110,00100}  3   L { ,0,00,01,111}  L1
6 L  {0110,1001, ,0111,1110,1}  4 { } L {0,01,011,1,110,1001} 2 L  
מהן השפות הבאות?
.א R L2 .ב L4  L6 .ג L1L5  L2L5 .ד R (L L L ) 1 2 5 .ה L5L6
(30%) 2 שאלה
תהייה , 1 2 L L ו- L3 שפות מעל א"ב  .
הוכח או הפרך:
.א     ( ) L1 L2 L1L2
.ב   
1 2  3  1 2  1 3 L (L L ) L L L L
( )( ) .ג L1  L2L3  L1  L2 L1  L3
הדרכה: כדי להוכיח שוויון יש להוכיח את שי כיווי ההכלה בין השפות התוות.
כדי להפריך שוויון מספיק להראות מקרה פרטי של השפות , 1 2 L L ו- L3 , ולהציג מילה לדוגמא
שמצאת באחת השפות (המוגדרות מצדי השוויון) אך לא בשיה.
2
(21%) 3 שאלה
בה אוטומטים סופיים דטרמייסטיים המקבלים את השפות הבאות מעל {1,0{  :
א. כל המילים שבהן האות הלפי אחרוה (אם קיימת – אם יש לפחות 2 אותיות) היא 0 .
ב. כל המילים שאורכן אי-זוגי ואין בהן תת-מילה 110 .
ג. כל המילים שבהן ההפרש, בערך מוחלט, בין מספר ה-0-ים לבין מספר ה-1-ים מתחלק ב-3
(ללא שארית).
(14%) 4 שאלה
R היא שפה רגולרית. LR היא שפה רגולרית. הוכח או הפרך: L היא שפה רגולרית.
(30%) 5 שאלה
R היא שפה רגולרית. L היא שפה שאיה רגולרית. וגדיר:
L4  L  R .4 L3  * L .3 L2  R  L .2 L1  L  R .1
לגבי כל אחת מהשפות שהגדרו – אם היא בהכרח רגולרית – הוכח; אם היא בהכרח איה רגולרית
– הוכח; ואם היא לעתים רגולרית ולעתים לא, תן דוגמא לכל מקרה (הצג דוגמא אחת של L ו- R
שעבורה Li רגולרית ודוגמא אחרת של L ו- R שעבורה Li איה רגולרית ).