מטלת מחה (ממ"ן) 12
הקורס: 20440 – אוטומטים ושפות פורמליות
חומר הלימוד למטלה: יחידה 3
מספר השאלות: 6 משקל המטלה: 2 קודות
סמסטר: ב2020 מועד אחרון להגשה: 2020.4.14
י.ק
אא שים לב:
מלא בדייקות את הטופס המלווה לממ"ן בהתאם לדוגמה שלפי המטלות.
העתק את מספר הקורס ומספר המטלה הרשומים לעיל.

הערות:
א. בחלק מהשאלות תתבקש לבות אוטומט סופי או לרשום ביטוי רגולרי. צרף לפתרון הסבר
מילולי המבהיר את דרך מחשבתך וממק את כוות הפתרון.
ב. השם "אוטומט סופי לא-דטרמייסטי" מתייחס הן לאוטומט כזה עם מסעי- ,הן לאוטומט
כזה בלי מסעי- .
ג. אוטומט סופי דטרמייסטי הוא מקרה פרטי של אוטומט סופי לא-דטרמייסטי.
לפיכך כשהך מתבקש לבות אוטומט סופי לא-דטרמייסטי מותר שהאוטומט כן יהיה
דטרמייסטי, ואולם, רצוי שהאוטומט יהיה פשוט ככל האפשר ולהשגת מטרה זו, במקרים
רבים, האי-דטרמייזם עוזר.
ד. מותר לסמן בקיצור את השפה שמציין ביטוי רגולרי r על-ידי r עצמו – אין צורך בסימון
. L r[ ] המלא

(20%) 1 שאלה
בה אוטומטים סופיים לא-דטרמייסטיים המקבלים את השפות הבאות שמעל abc {,,}   :
a b j i א. { i מתחלק ב-3 ללא שארית, ושארית חלוקת j ב- 4 היא 1{ |
.ב 1 2 { * | … ; w w w cw c w c   k
k  1;
( )*,1 , לכל ; w a b i ki i   
( )* ,1 , קיים { w aa b b i k i i   
4
(10%) 2 שאלה
בה אוטומט סופי לא-דטרמייסטי שמקבל את שפת כל המילים מעל {c,b,a {  שבהן אם יש
רצף bb ואם באיזשהו מקום בהמשך המילה יש רצף cc ,הרי שבשום מקום בייהם אין רצף cba .
השתדל שהאוטומט יהיה קטן ככל האפשר.

(16%) 3 שאלה
אוטומט עם שי קלטים הוא אוטומט דומה לאוטומט סופי, אלא שהוא מיועד לקבל זוגות של
מילים מעל א"ב .
את זוג מילות הקלט מקבל האוטומט משי מקורות שוים. לאוטומט שתי קבוצות זרות של
מצבים. כשמצא האוטומט במצב של הקבוצה הראשוה הוא מקבל קלט מהמקור הראשון,
וכשהוא מצא במצב של הקבוצה השיה הוא מקבל קלט מהמקור השי. לאחר קריאת אות קלט
עובר האוטומט למצב כלשהו בקבוצה כלשהי.
המצב ההתחלתי של האוטומט מצא בקבוצה הראשוה. מצבים מקבלים של האוטומט יכולים
להמצא בכל אחת משתי הקבוצות.
השפה שאוטומט זה מקבל: כל זוגות המילים (x,w (שבסיום קריאת שתיהן מצא האוטומט
במצב מקבל.
דוגמא
האוטומט שבאיור הבא מקבל את כל זוגות המילים מעל הא"ב {b,a {שבהן אורך המילה השיה
(זו מהמקור השי) כפול מאורך המילה הראשוה (זו מהמקור הראשון):

Start a,b a,b

a,b
{ , |0 , , } השפה את המקבל  -מסעי בלי קלטים יש עם אוטומט הב n m ln . a bb ab b l m n 
(24%) 4 שאלה
לפיך 2 זוגות של ביטויים רגולריים. לגבי כל זוג קבע אם הביטויים מצייים אותה שפה.
אם התשובה חיובית הוכח זאת, ולא – מק בקצרה את קביעתך.
*(( * )* ) א.
( * ( * ))*
a b ab
a ba b
   
 
ב.
( )*
(*) * *
a b
ba b b a  
 

  
5
(20%) 5 שאלה
א. רשום ביטוי רגולרי המציין את שפת כל המילים מעל {b,a {  שמתחילות ב-b ,שיש בהן
לפחות שתי אותיות b ,ושאין בהן תת-מילה bab .
ב. רשום ביטוי רגולרי המציין את שפת כל המילים מעל {b,a {  שאורכן מודולו 3 הוא 1 ,והן
שייכות לשפה *b*a .
(10%) 6 שאלה
בה באמצעות האלגוריתמים שביחידה אוטומט סופי דטרמייסטי השקול לאוטומט הסופי הלא-
דטרמייסטי:

1,
1 1 0