תורת המחשב

[lim1989]

תורת המחשב

היי.. אני עושה השבוע בגרות במדעי המחשב (2 יח"ל השלמה ל-5) ויש לי בעיונת קטנה עם תורת המחשב - בנושא דקדוקים. מישהו יודע איך בונים דקדוק שהשפה שלו כזאת: a(i)b(j)c(i-j) | i,j >=0 אני אודה לכם אם תוכלו לעזור לי...

 

[lim1989]

תיקון להודעה הקודמת

בטעות לא הקלדתי נכון את השפה... הנה התיקון: a(i)b(j)c(i-j) | i,j >=1 , i >= j

 

[ron369]

אולי כך,

תחשוב איך אפשר להציג את זה בצורה שונה, כלומר, ללא i-j (חיבור אולי?). הטריק הוא החלפת משתנים, למיטב זכרוני הרעוע.

 

[lim1989]

איך?

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

 

[lim1989]

מישהו יודע איך לפתור את זה?

 

[shirbi]

אפשר להסתכל על זה גם ככה:

רצף של a-ים באורךm+n ואח"כ רצף של b-ים באורך n ואח"כ רצף של c-ים באורך m. מכאן זה כבר הרבה יותר פשוט: מייצרים קודם כל את ה c-ים מימין ואת ה a-ים משמאל, אותו מספר של a-ים ושל c-ים. כשלא רוצים לייצר יותר a-ים ו c-ים, מתחילים לייצר באמצע את הa-ים הנותרים במספר שווה למספר של b-ים. בשביל צריך לדעת איך לייצר את הדקדוק של a^n||b^n, אבל אני מניח שזו בעיה קלה.

 

[ron369]

למה הגעת?