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

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

 

שאלה 1 הוכחות אי רגולריות + בניית אוטומט מחסנית + תכונות סגירות של שפות חופשיות הקשר

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

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

 

פתרון

א. L היא שפת כל המילים מעל הא"ב {a,b} אשר בהן ההפרש בין מספר האותיות a למספר האותיות b אינו עולה על 3.

 

ב. L אינה רגולרית.

    ההוכחה עבור השפה שהוגדרה בסעיף ב' בתרגיל 3.14 בספר לתלמיד (התרגיל פתור במדריך למורה) מתאימה גם עבור השפה L.

L חופשית הקשר כי ניתן להציגה באופן הבא:  L=L1ÈL2 כאשר L1 ו-L2 שתיהן מעל הא"ב {a,b}:

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

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

נראה אוטומט מחסנית עבור L1. אוטומט מחסנית עבור L2 יתקבל ממנו ע"י החלפת כל a ב-b וכל b ב-a. האוטומט יהיה לא דטרמיניסטי והוא יעבור עפ"י העיקרון הבא:

במילה בשפה ייתכן שמספר האותיות b שווה למספר האותיות a, יתכן שמספר האותיות b גדול ב-1 ממספר האותיות  a, יתכן שהוא גדול ב-2 ממספר האותיות a או גדול ב-3 ממספר האותיות  a.

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

לאוטומט זה יהיה מצב התחלתי חדש q0' – נוסף למצבים q0 ו-q1 (q0 כבר לא מצב התחלתי).

יהיו לאוטומט זה המעברים הבאים:

מנחש הפרש 0 –

(q0',a,^,q1, S)

מנחש הפרש 1 –

(q0',a,^,q0,ε)

מנחש הפרש 2 –

(q0',a,^,q1,T)

מנחש הפרש 3

(q0',a,^,q1,TB)

מנחש הפרש 0 –

(q0',b,^,q1,T)

מנחש הפרש 1 –

(q0',b,^,q1,TB)

מנחש הפרש 2 –

(q0',b,^,q1,TBB)

מנחש הפרש 3

(q0',a,^,q1,TBBB)

 

בנוסף למעברים אלו יהיו המעברים המקוריים של האוטומט בפתרון תרגיל 5.19. המצבים המקבלים הם q0' ו- q0.

 

חזרה

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

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