PDA

צפה בגרסה המלאה : אין יותר זמן... תרגיל בנושא מחשבים- מודליים חישובים - אוטומט מחסנית



Malakazzam
02-03-2014, 15:57
השאלה דחופה! היא בתמונה בקשור זה: View 495TYV.jpg - cubeupload (http://cubeupload.com/im/495TYV.jpg)

maozbd
02-03-2014, 16:56
קצת בעייתי לעשות שרטוט אז אני אנסה לכתוב בערך אלגוריתם...

סעיף א:

ה n המינימלי הוא 1 וה m המינימלי הוא 2 ולכן המילה הקצרה ביותר: abbcc.

סעיף ב:

בעיקרון סופרים את מספר ה a שנכנסו במחסנית על ידי הכנסת A למחסנית כל פעם שנקלט a,
כשנקלט b מוציאים כל פעם A מהמחסנית עד שלא נשארו A ואז מכניסים כל פעם שני B.
כשנקלט c מוציאים B עד שהמחסנית ריקה.

אשמח לענות אם משהו לא ברור :)

ב ה צ ל ח ה !!!

Malakazzam
03-03-2014, 16:01
תודה רבה. הכל ברור. :)

maozbd
03-03-2014, 16:25
בכיף ;)

chenkop
18-07-2015, 15:02
ראשית, כדאי לפשט את השפה, כך: 36594
סעיף א': נציב את ערכי ה-k,n הקטנים ביותר, כלומר k=1,n=1 ונקבל: abbcc.
סעיף ב': כדי להוכיח ששפה היא חופשית הקשר, יש לבנות אוטומט מחסנית המקבל אותה (אם ניתן אפילו לבנות אס"ד השפה רגולרית וודאי שחופשית הקשר). לאחר פישוט השפה קל לראות כי המילה מחולקת לשני חלקים: הראשון שבו מספר ה-a שווה למספר ה-b (לפי התבנית כמובן..) והחלק השני שבו מספר ה-c כפול ממספר ה-b. כך שנבנה את אוטומט המחסנית נפעל כך: בחלק הראשון, על כל a נדחוף אות ועל כל b נשלוף. בחלק השני נדחוף על כל b שתי אותיות, ועל כל c נשלוף אות. האוטומט שנקבל:
36595