אוטומטים ושפות פורמליות
מוסד לימוד | האוניברסיטה הפתוחה |
סוג העבודה | ממ"ן |
מספר ממ"ן | 14 |
מקצוע | מתמטיקה ומדעי המחשב |
קורס | אוטומטים ושפות פורמליות |
מילות מפתח | 14, אוטומטים, ושפות פורמליות, פתרונות ממנים האוניברסיטה הפתוחה |
שנת הגשה | 2020 |
מספר מקורות | 1 |
תקציר העבודה
מטלת מחה (ממ"ן) 14
הקורס: 20440 – אוטומטים ושפות פורמליות
חומר הלימוד למטלה: יחידה 5
מספר השאלות: 5 משקל המטלה: 2 קודות
סמסטר: ב2020 מועד אחרון להגשה: 2020.5.12
י.ק
אא שים לב:
מלא בדייקות את הטופס המלווה לממ"ן בהתאם לדוגמה שלפי המטלות.
העתק את מספר הקורס ומספר המטלה הרשומים לעיל.
(22%) 1 שאלה
הבאה רגולרית: הן שפות רגולריות מעל .הוכח באמצעות ביית אוטומט ש- L L2 ו- L1
;
;
n 1
,1 i n ,i לכל i
{ … | L 1 2 n
}
:ש כך, 1 k n ,k וקיים , v L2 קיימת
1 2 1 1 1 (בלבד v היא 1…v… n כל אז n=1 אם ( … k v k … n L
(22%) 2 שאלה
עבור השפה הבאה: RL רשמו את מחלקות השקילות של היחס
12 2 L w w u v uv u u v u { {0,1, 2}* | 0 ; , {1, 2}*; # ( ) # ( ) ; # ( ) | |}
(12%) 3 שאלה
בה אוטומט סופי דטרמייסטי קשיר ומצומצם השקול לאוטומט הסופי הבא:
b a
a b
b a
b b
a a a,b
a, b
a,b a a a,b
b
b c a
e
f
h
J
d
I
g
10
(22%) 4 שאלה
הוכח באמצעות משפט רוד שהשפה הבאה שמעל {e,d,c,b,a {איה רגולרית:
{ | ( )*, ( )*, # ( ) # ( )} 2 L xey x a d y b c x y a b
(22%) 5 שאלה
{ {0,1,2}* | # ( ) # ( )} . M 01*0 -ו L w 0 w 1 w
אם אפשר רשום ביטוי רגולרי המציין את השפה L/M ,ולא, ציין מהי השפה בכתיב קבוצות
העבודה בקובץ PDF