מטלת מחה (ממ”ן) 13
הקורס: 20440 – אוטומטים ושפות פורמליות
חומר הלימוד למטלה: יחידה 4
מספר השאלות: 5 משקל המטלה: 2 קודות
סמסטר: ב2020 מועד אחרון להגשה: 2020.4.28
י.ק
אא שים לב:
מלא בדייקות את הטופס המלווה לממ”ן בהתאם לדוגמה שלפי המטלות.
העתק את מספר הקורס ומספר המטלה הרשומים לעיל.
הערה: אחת הדרכים להוכיח ששפה היא רגולרית, היא ביית אוטומט (או הצגת ביטוי רגולרי).
במקרה שבחרת בדרך זו איך דרש להוכיח שאכן השפה שהאוטומט מקבל (או השפה
שהביטוי יוצר) שווה לשפה המבוקשת.
ואולם, הגדר את האוטומט במדויק, באופן פורמלי, וכן הסבר מדוע הבייה מתאימה
לשפה המבוקשת.
(15%) 1 שאלה
ם”אם דרוםפלי קראת {a,b,c} מעל w מילה R . w w
הוכח באמצעות למת היפוח ששפת הפלידרומים מעל {c,b,a {איה רגולרית.
(36%) 2 שאלה
הוכח באמצעות תכוות סגירות שהשפות הבאות אין רגולריות:
{a,b} מעל , L1 {bwbwb | w a*} .א
{ | ( )*, ( )*, # ( ) # ( )} .ב 2 L xey x a b y c d x y a c {a,b,c,d,e} מעל,
(14%) 3 שאלה
תהי L שפה רגולרית מעל .יהי A אוטומט סופי דטרמייסטי המקבל את L .
בה באמצעות A אוטומט סופי המקבל את שפת כל המילים שב- L המקיימות: לכל רישא ממש
שלהן, הרישא איה ב- L .
הערה: u היא רישא ממש של v אם”ם u היא רישא של v ,ו- v u .
(20%) 4 שאלה
תהי L שפה רגולרית מעל .הוכח שגם השפה הבאה רגולרית:
8
; 112 2 1 … { * | w ww w nnn Lˆ w
1 n ;
; :1 i n 1,i לכל i
; * :1 i n ,i לכל wi
L } 1
2 … n n1
(15%) 5 שאלה
L היא שפה רגולרית. NP היא שפת כל המילים השייכות ל-L שעבורן לא קיים אף פירוק uvw=z ,
uv w L i 0 שלכל כך | v | 0 שעבורו i .
הוכח או הפרך את הטעה ש-NP רגולרית.
| מילות מפתח | 13, אוטומטים, ושפות פורמליות, ממן |
| מקצוע/ות | ממ"נים |
| מספר מילים | |
| מספר מקורות | 1 |
| שנת הגשה | 2020 |