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

השפה היא

הסבר של השפה במילים: a בחזקת i

b בחזקת i+k-j

c בחזקת j

d בחזקת k

כאשר i j k גדולים מ-0 וk גדול מ j

זה נראה כמו context free language

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

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

בסך הכל שאלה די מעניינת.

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

במבט זריז (תבדוק את הפתרון כי אולי פספסתי משהו):

- בהתחלה כשאתה מקבל a אתה דוחף אותו.

- אחר כך כשאתה מקבל b: - כל עוד יש בראש המחסנית a אתה שולף מהמחסנית.

- ברגע שהמחסנית ריקה אתה דוחף למחסנית.

- כשאתה מקבל c את דוחף אותו למחסנית.

אחרי שסיימת לדחוף את c יש לך במחסנית k איברים (יש לך k-j פעמים b, ו j פעמים c. בסה"כ k-j+j=k

- כשאתה מקבל d את מתחיל לשלוף מהמחסנית. אם סיימת כשהמחסנית ריקה המילה תקינה.

במבט זריז (תבדוק את הפתרון כי אולי פספסתי משהו):

- בהתחלה כשאתה מקבל a אתה דוחף אותו.

- אחר כך כשאתה מקבל b: - כל עוד יש בראש המחסנית a אתה שולף מהמחסנית.

- ברגע שהמחסנית ריקה אתה דוחף למחסנית.

- כשאתה מקבל c את דוחף אותו למחסנית.

אחרי שסיימת לדחוף את c יש לך במחסנית k איברים (יש לך k-j פעמים b, ו j פעמים c. בסה"כ k-j+j=k

- כשאתה מקבל d את מתחיל לשלוף מהמחסנית. אם סיימת כשהמחסנית ריקה המילה תקינה.

נראה לי שזה יעבוד

אני גם ניסיתי להגדיר את השפה יש לי משהו חלקי כי אני עדיין לא חשבתי על איך לקיים את ה תנאי k>j אני לא בטוח שזה מתקיים

a^(i)b^(k+i-j)c^(j)d^(k)

S->ABBD

AB->AABB

BD->BBDD

BD->CD

BC->CC

A->a

B->b

C->c

D->d

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

אם תיקחו i=k ו j=0 תקבלו את השפה a^i b^2i ^i שהינה שפה בעלת הקשר.

דותן

אבל נתון ש-j גדול מ0.