כמה שאלות לבגרות מחר (מדעי המחשב ב'

[LiranViper]

כמה שאלות לבגרות מחר (מדעי המחשב ב'

שלום, יש לי בגרות מחר, תודה רבה לעוזרים! כמה שאלות: 1) מה הסיבוכיות בפקודה "אחזר_מרשימה"? 2) מה זה L*? (ראיתי בשאלה מבגרות קודמת) 3) אם בשאלה מצויין שגודל המערך הוא N והוא זוגי וגדול מ0 ובמשימה אומרים "כתוב תוכנית.." אז כשאני כותב את התוכנית אני עושה Const = 10; לדוגמא? (יעינו אני סתם ממציא מספר שעונה לקרטריונים, במקרה שלנו- זוגי וגדול מ0) 4) איך מוכיחים שהשפה a^n b^n c^n היא לא חופשית הקשר? 5) כשאומרים בנה אוטומטס סופי דטרמינסטית, מותר במקום לבנות אותו- לפרק ל2 שפות ולהוכיח את ה2? (ואח"כ כמובן לאחד עם הכללים) תודה רבה.

 

[CaSsIe]

גם לי שאלה קטנה..

בתורת המחשב כשמבקשים ממני לכתוב אוטומט מחסנית. מספיק לכתוב את רשימת המעברים/מצבים? או שאני צריכה גם בצורה גרפית? (היינו עיגולים וחיצים). תודה מראש לעונים!

 

[gilatb1]

מספיק אחד מהם (לא משנה איזה)

 

[ron369]

תשובות ל-2, ו-5

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

3) נראה לי שכן. 4) למת הניפוח - מותר? 5) כן. אם שתי שפות הן רגולריות, האיחוד שלהן רגולרי.

 

[shirbi]

4. עם למת הניפוח לשפות ח"ה.

 

[gilatb1]

5. כן, אפשר לעשות איחוד אוטומטים

רק קח בחשבון שזה לוקח יותר זמן לעשות 2 שונים ולאחד...

 

[גיל14]

כמה תשובות מאוחר מדי

1) (O(n, כאשר n אורך הרשימה. 2) שרשור של L לעצמה 0 או יותר פעמים, אבל אין את זה לדעתי בבגרות. 3) כן - רצוי לכתוב הערה שכאן זה ערך שרירותי. 4) עם חומר שלא למדנו. 5) כל עוד אתה מאחד באמצעות אוטומט מכפלה, ומגיש את האוטומט הסופי כתשובתך. סתם להראות ששפה כלשהי רגולרית לא מספיק - אם מבקשים אוטומט אתה צריך להראות אוטומט, לא לומר שיש כזה. שים לב שיתכן שיורידו לך נקודות על אוטומט מסובך מדי.

 

[ron369]

אוטומט מסובך מדי?

אתם מודעים לעובדה שאוטומט סופי דטרמיניסטי מינימלי הוא יחיד, נכון?

 

[גיל14]

כן, אבל אוטומט מכפלה הוא לא מינימלי

לפחות אם אתה לא עושה אותו מינימלי.

 

[ron369]

אבל זה אלגוריתם נורא נורא פשוט...

(כלומר, זה שלוקח אלגוריתם, והופך אותו לאסל"ד)

 

[גיל14]

כן אבל לפעמים דורשים אס"ד

או בשמו הבגרותי אסד"מ - המ' בשביל "מלא".

 

[lim1989]

אס"ד

בקשר לאוטומט סופי דטרמיניסטי... אפשר לפרק לשניים זה נקרא אוטומט חיתוך / ייחוד וזה חלק מהנושא של אס"ד.. (אני חושבת.. )