מאגר שאלות ותשובות להוראת מודלים חישוביים:

בעיות משולבות

דורון זוהר

 

שאלה 1 – (הוכחות אי רגולריות + תכונות סגירות של שפות רגולריות)

א. נתבונן בשפת כל המילים מעל הא"ב {a,b,c} המקיימות את כל ארבעת התנאים הבאים:

I. מספר המופעים של האות c במילה הוא זוגי.

II. אורך המילה גדול מ-1.

III. המילה מתחילה באות c.

IV. אם נסמן ב-n את מספר המופעים של האות a במילה אז מספר המופעים של האות b הוא ndiv3.

האם השפה רגולרית? הוכח את תשובתך.

ב. נתבונן בשפה מעל הא"ב {a,b,c} המוגדרת כמו השפה בסעיף א' פרט לכך שסעיף IV הוא התנאי: אם נסמן ב-n את מספר המופעים של האות a במילה אז מספר המופעים של האות b במילה הוא nmod3.
האם השפה רגולרית? הוכח את תשובתך.

 

פתרון

א. השפה אינה רגולרית. נניח בשלילה שהיא רגולרית ולכן קיים אוטומט סופי A שמקבל אותה.

    נתבונן בקבוצת המילים האינסופית W={cca3i½i³0}.

    נניח בשלילה שקיימות בקבוצה זו שתי מילים cca3i, cca3j כך ש- i≠j, והאוטומט A מגיע על שתיהן לאותו מצב q.

    נתבונן במילה cca3ibi. זו מילה השייכת לשפה משום שאורכה גדול מ-1, היא מתחילה באות c, מספר המופעים של האות c בה הוא 2 וזה מספר זוגי, ומספר מופעי האות a במילה הוא 3i ומספר מופע האות b במילה הוא (3i)div3=i. לכן מהמצב q האוטומט מגיע למצב מקבל בקוראו את הסיפא  bi. אבל מכאן נובע שהאוטומט מקבל גם את המילה  cca3ibj שאינה שייכת לשפה – אמנם היא מקיימת את שלושת התנאים הראשונים, אך j≠(3i)div3 ולכן היא אינה מקיימת את התנאי האחרון.

    לכן, על כל מילה ב-W האוטומט מגיע למצב שונה ומכיוון ש-W אינסופית, נובע שלאוטומט A אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן בהכרח השפה אינה רגולרית.

 

ב. השפה שמוגדרת בסעיף זה היא שפה רגולרית. ניתן להגדירה בעזרת ארבע השפות הבאות, כולן מעל הא"ב {a,b,c}:

L1 : שפת כל המילים שמספר האותיות c בהן הוא זוגי.

L2 : שפת כל המילים שאורכן גדול מ-1.

L3 : שפת כל המילים שמתחילות  ב-c.

L4 : שפת כל המילים שמספר מופעי האות b בהן שווה לשארית של מספר האותיות a במילה מחולק ב-3.

ברור כי  L1=((L1∩L2) ∩L3)∩L4

 

כל השפות רגולריות. הנה אוטומטים מתאימים עבורן:

A1 עבור L1:

A2 עבור L2:

A3 עבור L3:

A4 עבור L4:

 

באוטומט A4 עבור L4 המצב qij זוכר כי השארית של מספר האותיות a שנקראו בחלוקה ב-3 היא i, ומספר האותיות b שנקראו הוא  j.

 

מסגירות משפחת השפות הרגולריות לפעולת החיתוך גם L1∩L2, (L1∩L2)∩L3 ו-((L1∩L2)∩L3)∩L4 רגולריות.

 

שאלה 2

לגבי כל אחת מהטענות הבאות קבע אם היא נכונה או לא. אם היא נכונה, הוכח זאת, ואם היא שגויה – הבא דוגמא נגדית מתאימה.

א.    כל שפה חופשית הקשר היא רגולרית.

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

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

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

ה.    כל שפה המתקבלת ע"י אוטומט מחסנית דטרמיניסטי לא מלא היא שפה חופשית הקשר.

ו.      כל שפה המתקבלת ע"י מכונת טיורינג היא שפה חופשית הקשר.

ז.     כל שפה המתקבלת ע"י אוטומט סופי היא שפה חופשית הקשר.

 

פתרון

א. הטענה אינה נכונה – השפה {anbn½n³0} היא שפה חופשית הקשר (יש עבורה אוטומט מחסנית בסעיף 5.2 בספר הלימוד) שאינה רגולרית (מוכח בספר הלימוד בסעיף 3.2).

ב. הטענה נכונה – כל שפה רגולרית מתקבלת ע"י אוטומט סופי דטרמיניסטי וניתן להסב אותו לאוטומט מחסנית דטרמיניסטי שכלל אינו משתמש במחסנית (זהו למעשה כיוון אחד בפתרון תרגיל 6.1 מספר הלימוד).

ג. הטענה נכונה – אוטומט מחסנית דטרמיניסטי הוא בפרט אוטומט מחסנית לא דטרמיניסטי.

ד. הטענה אינה נכונה – השפה w} מילה מעל הא"ב {w∙R(w) ½{a,b} היא שפה המתקבלת ע"י אוטומט מחסנית לא דטרמיניסטי (דוגמה 5.4 בספר הלימוד), אך לא קיים אוטומט מחסנית דטרמיניסטי שמקבל אותה (כנאמר בספר הלימוד).

ה. הטענה נכונה – אוטומט מחסנית דטרמיניסטי לא מלא הוא בפרט אוטומט מחסנית לא דטרמיניסטי ולכן כל שפה המתקבלת על ידו היא חופשית הקשר.

ו. הטענה אינה נכונה – השפה {anbncn½n³0} היא שפה שמתקבלת ע"י מכונת טיורינג (דוגמה 7.2 בספר הלימוד), אך כפי שנאמר בפרק 6 בספר הלימוד (דוגמה 6.1) היא אינה חופשית הקשר.

ז. הטענה נכונה – שפה המתקבלת ע"י אוטומט סופי, מתקבלת גם ע"י אוטומט מחסנית – כי ניתן להסב את האוטומט הסופי לאוטומט מחסנית שכלל אינו משתמש במחסנית (כפי שנעשה בסעיף 6.1 בספר הלימוד) ולכן היא חופשית הקשר.

 

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

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים