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

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

אלה פוק

 

שאלה 1

עבור מילה w ואות s נסמן ב-(w)s# את מספר מופעי האות s ב-w.

תהי L השפה הבאה מעל הא"ב {0,1}:

{w מעל הא"בL={w½#0(w)mod 2>#1(w)mod2, {0,1}

האם L היא רגולרית, שפה חופשית הקשר שאינה רגולרית או אף אחת משתי האפשרויות? הוכח את תשובתך.

 

פתרון

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

במקרה זה, מספר מופעי האות 1 ב-w מודולו 2 חייב להיות 0 (כלומר, זוגי)

ומספר מופעי האות 0 ב-w מודולו 2 חייב להיות 1 (כלומר אי-זוגי).

אם כך, ניתן להגדיר את L כך: L1=L1∩L2 כאשר  L1 ו-L2 מעל הא"ב {0,1}:

 

{(w)1# זוגי L1={w½

{(w)0# אי-זוגי L2={w½

 

L1 רגולרית, הנה אוטומט סופי שמקבל אותה:

L2 רגולרית, הנה אוטומט סופי שמקבל אותה:

 

ומסגירות משפחת השפות הרגולריות לחיתוך גם L=L1ÇL2  רגולרית.

 

שאלה 2הוכחת אי רגולריות + בניית אוטומטים + שימוש בתכונות סגירות

נתונות 4 שפות.

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

 

L1={aibjck½i mod 2=j mod 2, i,j,k³0}

L2={aibjck½i=j or  k<j, i,j,k³0}

L3={aibjck½|j-k|³i, j mod 2=0, i,j,k³0}

L4=L1ÈL3

 

פתרון

א. ניתן להציג את L1 בעזרת השפות הבאות.

{i אי-זוגי, i³0 ½  L6={ai             {i זוגי, i³0 ½  L5={ai

{i אי-זוגי, i³0 ½  L8={bi             {i זוגי, i³0 ½  L7={bi

{ i³0 ½  L9={ci

L1=L5∙L7∙L9ÈL6∙L8∙L9

A6,A5 ו-A9  הם אוטומטים עבור L6,L5 ו-L9 בהתאמה:

 

 

 

אוטומטים עבור L7 ו-L8 ניתן לקבל מ-A5 ו-A6 בהתאמה ע"י החלפת כל a ב-b.

לכן כל השפות רגולריות.

מסגירות משפחת השפות הרגולריות לשרשור גם L5×L7, (L5×L7)×L9, (L6∙L8), (L6×L8)×L9 רגולריות ומסגירות משפחת השפות הרגולריות לאיחוד גם L5∙L7∙L9ÈL6∙L8∙L9 רגולרית.

 

ב. L2 חופשית הקשר. ניתן להציגה באופן הבא:

L10={anbn½n³0}

L9={ci½i ³0}

L11={ai½i³0}

L12={bjck½k<j, k³0}

L2=L10∙L9ÈL11∙L12

 

L9 רגולרית – בנינו עבורה אוטומט בסעיף א'. לכן היא גם חופשית הקשר.

L11 רגולרית – ע"י אותו אוטומט, עם החלפת כל c ב-a. לכן גם היא ח"ה.

L10 חופשית הקשר וכך גם L12 – ע"פ ספר הלימוד.

מסגירות משפחת השפות חופשיות ההקשר לשרשור גם L10∙L9  וגם  L11∙L12חופשית הקשר, ומסגירות משפחת השפות חופשיות ההקשר לאיחוד גם   L2=L10∙L9ÈL11∙L12חופשית הקשר.

 

L2 אינה רגולרית. נניח בשלילה שהיא רגולרית ולכן קיים אוטומט סופי A שמקבל אותה. נסתכל על קבוצת המילים הבאה: W={an½n≥0} ונניח שקיימות ב-W שתי מילים i>j, aj,ai כך שהאוטומט מגיע לאותו מצב q עבור ai ו- aj. המילה aibici בשפה כי מספר האותיות a בה שווה למספר האותיות b שבה. לכן האוטומט מגיע למצב מקבל בקוראו את הסיפא bici מהמצב q. לכן הוא מקבל גם את המילה ajbici, אבל מילה זו אינה בשפה (j≠i, ו-i אינו קטן מ-i) בסתירה להיות A אוטומט שמקבל את השפה. לכן, על כל מילה ב-W האוטומט מגיע למצב שונה, ולכן בהכרח יש ל-A אינסוף מצבים, בסתירה להיותו אוטומט סופי. לכן L אינה רגולרית.

 

ג. L3 חופשית הקשר. ניתן להציגה באופן הבא:

L13={aibjck½ j-k³i, j³k, i,j,k³0, j mod 2=0}

L14={aibjck½ k-j³i, k³j, i,j,k³0, j mod 2=0}

L3=L13 ÈL14

 

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

יכניס למחסנית אות A על כל אות a שנקראת.

כאשר נקראות אותיות b יתחיל לשלוף אותיות מהמחסנית (תוך בדיקת זוגיות מספר האותיות b בעזרת מצבים מתאימים).

כאשר המחסנית מתרוקנת יתחיל למלא אותה שוב באותיות A (תוך סימון תחתית המחסנית ותוך המשך בדיקת זוגיות מספר האותיות b בעזרת המצבים). כאשר נקראות אותיות c יתחיל לשלוף אותיות מהמחסנית.

אם נקראו אותיות i אותיות a, אז יקראו i אותיות  b לפני ריקון המחסנית ועוד j-i אותיות b, ואז k אותיות c. כל עוד המחסנית לא התרוקנה הרי ש- j-i>k, כלומר j-k>i. לכן, כל מצב בו המחסנית לא ריקה ומספר האותיות b זוגי צריך להיות מצב מקבל. האוטומט לא יאפשר קריאת אותיות c אחרי שהמחסנית התרוקנה.

המצבים:

q0 – מצב התחלתי בו נקראות אותיות a.

q1 – מצב לקריאת אותיות b, לפני שהמחסנית התרוקנה, שזוכר שמספר האותיות b שנקראו עד כה זוגי.

q2 – מצב לקריאת אותיות b, לפני שהמחסנית התרוקנה, שזוכר שמספר האותיות b שנקראו עד כה אי-זוגי.

q3 – מצב לקריאת אותיות b, בשלב המילוי השני, שזוכר שמספר האותיות b שנקראו עד כה זוגי.

q4 – מצב לקריאת אותיות b, בשלב המילוי השני, שזוכר שמספר האותיות b שנקראו עד כה אי-זוגי.

q5 – מצב לקריאת אותיות c.

כל המצבים מקבלים, חוץ מ-q2 ו-q4.

מעברים:

קריאת אות a ראשונה –

(q0,a,^,q0,A)

קריאת אות a שניה ויותר 

(q0,a,A,q0,AA)

קריאת אות b ראשונה כשלא נקראו אותיות a

(q0,b,^,q4,A)

קריאת אות b ראשונה כשנקראו אותיות a

(q0,b,A,q2,ε)

קריאת אות b זוגית לפני התרוקנות המחסנית – 

(q2,b,A,q1,ε)

קריאת אות b אי-זוגית, שלישית ויותר, לפני התרוקנות המחסנית – 

(q1,b,A,q2,ε)

קריאת אות b זוגית אחרי התרוקנות המחסנית –

(q2,b,^,q3,A)

קריאת אות b אי-זוגית, שלישית ויותר, אחרי התרוקנות המחסנית –

(q1,b,^,q4,A)

קריאת אות b אי-זוגית בשלב המילוי השני 

(q3,b,A,q4,AA)

קריאת אות b זוגית בשלב המילוי השני 

(q4,b,A,q3,AA)

קריאת אות c ראשונה –

(q3,c,A,q5,ε)

קריאת אות c שניה ויותר –

(q5,c,A,q5,ε)

 

נשים לב שקריאת c ראשונה אפשרית רק במצב q3, המציין מספר זוגי של אותיות b, וכי לא ניתן לקרוא אותיות c כאשר המחסנית ריקה.

 

עבור L14, נשים לב כי הדרישה k-j³i משמעותה k³i+j. לכן האוטומט ימלא את המחסנית עם קריאת אותיות a ו-b וירוקן עם קריאת אותיות c. קריאת אותיות b, כמו מקודם, תשולב עם בדיקת זוגיות מספר האותיות b שנקראות. אין צורך גם כאן בסימון תחתית המחסנית, וניתן להמשיך ולקרוא אותיות c אחרי התרוקנות המחסנית.

q0 – מצב התחלתי

q1 – מצב לקריאת אותיות a.

q2 – מצב לקריאת אותיות b, שזוכר כי נקרא מספר זוגי של אותיות b.

q3 – מצב לקריאת אותיות b, שזוכר כי נקרא מספר אי-זוגי של אותיות b.

q4 – מצב לקריאת אותיות c, לפני התרוקנות המחסנית.

q5 – מצב לקריאת אותיות c, אחרי התרוקנות המחסנית.

המצבים המקבלים הם  q0 ו-q5.

המעברים:

קריאת אות a ראשונה –

(q0,a,^,q1,A)

קריאת אות a שניה ויותר 

(q1,a,A,q1,AA)

קריאת אות b ראשונה, כשלא נקראו אותיות a

(q0,b,^,q3,A)

קריאת אות b ראשונה, כאשר נקראו לפניה אותיות a

(q1,b,A,q3,AA)

קריאת אות b זוגית – 

(q3,b,A,q2,AA)

קריאת אות b אי-זוגית שלישית ויותר –

(q2,b,A,q3,AA)

קריאת אות c ראשונה, כשנקראו אותיות b 

(q2,c,A,q4,ε)

קריאת אות c ראשונה, כשלא נקראו אותיות b

(q1,c,A,q4,ε)

קריאת אות c ראשונה, כשלא נקראו אותיות a ואותיות b

(q0,c,^,q5, ε)

קריאת אות c שניה ויותר, לפני התרוקנות המחסנית –

(q4,c,A,q4, ε)

קריאת אות c שניה ויותר, הראשונה לאחר התרוקנות המחסנית –

(q4,c,^,q5, ε)

קריאת אות c שניה ויותר, אחרי התרוקנות המחסנית –

(q5,c,^,q5, ε)

 

לכן גם L14 חופשית הקשר, ומסגירות משפחת השפות חופשיות ההקשר לאיחוד גם L3=L13ÈL14 חופשית הקשר.

 

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

ראשית, נשים לב שמילים בהן מספר האותיות b זוגי, אין בהן אותיות c, ומספר האותיות a בהן שווה למספר האותיות b הן מילים ששייכות לשפה, כי מילים כאלו מקיימות .

בדומה, מילים שאין בהן אותיות c ומספר האותיות b בהן קטן ממספר האותיות a אינן בשפה,

כי הן מקיימות .

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

נניח שקיימות בקבוצה זו שתי מילים a,am, ℓ>m, כך ש-A מגיע על a ו-am לאותו מצב q.

אם m זוגי נתבונן במילה ambm, אחרת נתבונן במילה amabm+1. בשני המקרים המילה הנדונה בשפה כי מספר האותיות b שבה זוגי, אין בה אותיות c ומספר האותיות a שווה למספר האותיות b.

נניח ש-m זוגי: מאחר שהאוטומט מקבל את ambm אז קריאת הסיפא bm במצב q מביאה אותו למצב מקבל. אבל אז האוטומט מקבל גם את abm שאינה בשפה (אמנם מספר האותיות b שבה זוגי, אבל אין בה אותיות c ומספר האותיות b שבה קטן ממספר האותיות a).

בדומה, אם m אי-זוגי אז קריאת הסיפא abm+1 במצב q מביאה את האוטומט למצב מקבל ולכן הוא מקבל גם את המילה aabm+1. כלומר aℓ+1bm+1. אבל מילה זו אינה בשפה (כמו קודם, אמנם מספר האותיות b שבה זוגי, אבל אין בה אותיות c ומספר האותיות b בה קטן ממספר האותיות a).

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

 

ד. L1 רגולרית ובפרט חופשית הקשר, L3 חופשית הקשר ומסגירות משפחת השפות חופשיות ההקשר לאיחוד גם L4=L1ÈL3 חופשית הקשר.

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

נוכיח כי היא לא רגולרית באופן הבא:

ראשית, נשים לב כי מילים בהן מספר האותיות b זוגי, אין בהן אותיות c ומספר האותיות a בהן קטן או שווה למספר האותיות b שבהן הן מילים ששייכות לשפה, כי הן מקיימות.

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

נתבונן בקבוצת המילים האינסופית {n אי-זוגי W={an½n³0,.

נניח שיש בקבוצה זו שתי מילים am, a כך ש m<ℓ ו- ו-m אי-זוגיים והאוטומט מגיע על שתי המילים לאותו מצב q.

נתבונן במילה ambℓ-1. אי-זוגי ולכן ℓ-1, מספר האותיות b במילה, זוגי.

כמו כן בגלל ש- ℓ>m אז ℓ-1³m ולכן מתקיים שמספר האותיות a במילה קטן או שווה למספר האותיות b במילה, ולכן המילה בשפה. כלומר מהמצב q האוטומט מגיע למצב מקבל בקוראו את bℓ-1 . לכן האוטומט מקבל גם את abℓ-1. מילה זו אינה בשפה – זוגיות מספר האותיות a שונה מזוגיות מספר האותיות b, ובנוסף, אין במילה אותיות c ומספר האותיות b קטן ממספר האותיות a, ולכן, כפי שהראינו בסעיף הקודם, המילה גם אינה ב-L3.

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

 

שאלה 3  תכונות סגירות של שפות רגולריות ושפות חופשיות הקשר

נגדיר פעולה על זוגות של שפות מעל אותו א"ב:

C(L1,L2)={xyz½xyÎL1, yzÎL2, y≠ ε}

 

א. הראה כי משפחת השפות הרגולריות סגורה לפעולה C

ב. האם משפחת השפות חופשיות ההקשר סגורה לפעולה C? הוכח את תשובתך.

 

פתרון

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

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

     האינטואיציה מדוע יש סגירות היא שאפשר להרכיב את שני האוטומטים שמקבלים את L1 ו-L2 לאוטומט עבור C(L1,L2) באופן הבא:

     להתחיל לרוץ באוטומט עבור L1.

     באיזשהו שלב, באופן אי-דטרמיניסטי, לנחש שקטע הקלט הבא גם מסיים מילה ב-L1 וגם מתחיל מילה ב-L2, ולהריץ אותו במקביל (בדומה לאוטומט מכפלה) בשני האוטומטים, ובאיזשהו שלב, באופן אי-דטרמיניסטי, כאשר נמצאים במצב מקבל באוטומט הראשון, לנחש כי נכנסים לסיפא של המילה, המסיימת את המילה ב-L2 ולעבור לרוץ רק באוטומט עבור L2.

 

 

ההוכחה היא לכן קונסטרוקטיבית:

כדי להראות שאם L1 ו-L2 רגולריות אז גם C(L1,L2) רגולרית מראים שבהינתן אוטומטים סופיים עבור L1 ו-L2 A1 ו-A2 בהתאמה, ניתן מהם לבנות אוטומט שמקבל את C(L1,L2).

קבוצת המצבים של האוטומט החדש A תכיל את כל המצבים של A1, כל המצבים של A2, ובנוסף את כל זוגות המצבים המכילים מצב מ-A1 ומצב מ-A2 (כמו באוטומט מכפלה לקבלת שפת חיתוך או איחוד). כלומר, אם למשל ל-A1 מצבים q0 ו-q1 ול-A2 מצבים p0 ו-p1 אז ל-A יהיו המצבים: q1p1, q1p0, q0p1, q0p0, p1, p0, q1, q0.

הא"ב יהיה כמובן הא"ב של כל אחד מהאוטומטים (עפ"י הנתון, השפות הנתונות הן מעל אותו א"ב).

המעברים יוגדרו באופן הבא:

כל המעברים של A1 וכל המעברים של A2 יהיו גם מעברים של האוטומט החדש, כדי שניתן יהיה להריץ  את  הרישא  ב-A1  ואת  הסיפא  ב-A2.  בנוסף,  לכל  מעבר  (qi, sr, qj)  ב-A1  ומעבר (p, sr, pm) ב-A2 יהיה ב-A מעבר (qip, sr, qjpm).

אלו מעברים שנועדו להרצה במקביל של התת-מילה האמצעית ב-A1 וב-A2.

יש צורך גם במעברי חיבור. ראשית – מעברי הכניסה להרצה במקביל:

אם (qi, sr, qj) הוא מעבר של A1 ו- (p0, sr, pm) הוא מעבר מהמצב ההתחלתי של A2 אז ב-A יהיה המעבר (qi, sr, qjpm).

מעברי היציאה מההרצה במקביל:

אם (p, sr, pm) הוא מעבר של A2 ו-qi הוא מצב מקבל של A1 אז ב-A יהיה המעבר  (qip, sr, pm).

מהם המצבים המקבלים? בוודאי שכל המצבים המקבלים של A2 הם מצבים מקבלים של האוטומט החדש.

בנוסף, יתכן שמילה מסויימת עונה על הגדרת C(L1,L2) בעזרת z=ε. כלומר, המילה היא x∙y כך ש- x∙yÎL1 ו- yÎL2. כדי לקבל מילים כאלו יש לקבלן בסיום ההרצה במקביל, ולא לבצע הרצת סיפא ב-A2. לכן אם qi מצב מקבל של A1 ו-p מצב מקבל של A2, גם המצב qip צריך להיות מצב מקבל של A. ברור שהמצב ההתחלתי של A1 צריך להיות גם המצב ההתחלתי של האוטומט החדש A.

אם אכן מוכיחים את הסגירות לפעולה C כדאי להדגים את הבנייה על שני אוטומטים פשוטים ובפרט להתייחס לנקודות הבאות: כיצד מתקבלת באוטומט מילה עבורה z=ε? (לשאלה זו התייחסנו לעיל, בהגדרת קבוצת המצבים המקבלים), מילה עבורה x=ε? (מעברי הכניסה להרצה במקביל כוללים גם מעברים מ- q0, המצב ההתחלתי של A1, ומשמעותם שכבר האות הראשונה מורצת במקביל הן ב-A1 והן ב-A2).

ניתן היה להשמיט את ההגבלה y≠ε. השפות הרגולריות עדיין סגורות לפעולה C גם אחרי השינוי, אך אז הבנייה מעט יותר מורכבת. בנוסף, אז גם סעיף ב' הופך לסעיף קשה מדי.

 

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

L1={anbn½n>0}      L2={bncn½n>0}

C(L1,L2) = {anbncn½n>0}

וכמובן שבמקרה זה C(L1,L2) אינה חופשית הקשר.

בהמשך להערה בסוף פתרון סעיף א', נשים לב שאם אנחנו מרשים y=ε אז C(L1,L2) אינה השפה anbncn½n>0}}.

במקרה זה גם מילים מהצורה x×z כאשר xÎL1 ו- zÎL2 שייכות ל-C(L1,L2), כי ניתן להציגן כ-ÎL1 x×e, ε×zÎL2.

לכן C(L1,L2)  מכילה גם מילים מהצורה anbnbmcm .

גם במקרה זה C(L1,L2) אינה חופשית הקשר אך אין לתלמידים את הכלים להראות זאת.

 

חזרה

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

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