שאלה באוטומטים ? קצת מאוחר אני יודע

[ELIELI22]

שאלה באוטומטים ? קצת מאוחר אני יודע

שלום , אני לא כל כך הבנתי מה היא השפה שבשאלה 4? מישהו מוכן להסביר לי מה רוצים ? אני לא הבנתי אם זה לכל n או רק לn מסוים. משם נראה לי שאני אדע להמשיך . אשמח לכל תשובה .

 

[Fingertip]

אם הצלחתי לקרוא נכון...

אז השפה היא:

a^i1b^j1a^i2b^i2...a^inb^in​

והשאר רואים ברור. ובכן, השפה היא אוסף כל הרצפים של a^nb^m כאשר בכל זוג כזה מספר ה-b-ים כפול ממספר ה-a-ים. הפתרון לא מסובך מדי... אהד.

 

[Fingertip]

דוגמאות

בשפה:

abbaabbbbabb aabbbbaaaaaabbbbbbbbbbbb aaabbbbbb​

לא בשפה:

ε (n ≥ 1 כי) bba (ים-a-כי קודם באים ה) abbb (פשוט לא אותו מספר) aabbbbab (כנ"ל)​

מקווה שעזרתי, אהד.

 

[ELIELI22]

אני הבנתי ש..

לא משנה מה קרה עד כה ... מה שמשנה זה האיברים האחרונים הווה אומר : aaabbabbabbbabbaaaaaabbb לדוגמא כן בשפה , וגם abababaab כן בשפה . אבל אני רואה גם שלn כלשהו גדול מ 1 זה מתקיים . נכון ?

 

[Fingertip]

צודק... טעות שלי...

רק שזה הפוך. כמות ה-b-ים האחרונים צריכה להיות כפולה מכמות ה-a-ים האחרונים, לא להפך. אהד.

 

[ELIELI22]

ותודה קודם כל .

 

[ELIELI22]

מישהו אולי יכול לתת לי כיוון בשאלות

5,6 ? אני אשמח לקבל עזרה בשאלות 5,6 . האם זו תשובה ראויה ל 6?

 

[Fingertip]

אני לא זוכר משהו...

האם באוטומט מחסנית אני רשאי לאתחל את המחסנית במחרוזת כלשהי? אהד.

 

[ELIELI22]

באות אחת ,

באות אחת עד כמה שאני יודע . שנראית בדרכ כמו כמו "|-" משהו כזה רק מחובר , כמובן אפשר לאתחל בכל אות אחרת . (פשוט זה הסימן המקובל) .

 

[gil levi]

ניסיתי לפתור (סתם,בשביל עצמי)

אבל נתקלתי בבעיה. הרעיון שלי בקווים כללים הוא כזה: בפעם הראשונה שרואים a מכניסים A למחסנית ועוברים למצב q_a1 (מכל מצב שהיינו בו קודם). כשאנחנו במצב q_a1, אם אנחנו רואים עוד a-ים, אנחנו לא מכניסים ולא מוציאים ונשארים באותו מצב. אם אנחנו רואים b אנחנו מוציאים A מהחסנית ועוברים למצב q_b1. כשאנחנו במצב q_b1 , אם אנחנו רואים עוד b-ים, אנחנו לא מכניסים ולא מוציאים ונשארים באותו מצב. אם אנחנו רואים a אנחנו מכניסים A למחסנית ועוברים למצב q_a1. זה צריך לקרות n-1 פעמים ואז מגיעים לשלב שבו כמות הb-ים האחרונים צריכה להיות כפולה מכמות הa-ים האחרונים, ואת זה אני יודע לעשות בעזרת אוטומט מחסנית. הבעיה שלי היא איך אני סופר את n-1 המחרוזות הקודמות של a ו b ? איך אני יודע שהיו לי בדיוק n-1? אפשר הכוונה? תודה מראש.

 

[ELIELI22]

על איזו שאלה מדובר ?

 

[gil levi]

שאלה 4

 

[ELIELI22]

פתרתי אותה וזה הולך פחות או יותר כך

האוטומט הוא לא דטרמיניסטי ולכן : ישנן 2 אפשרויות : 1> להתעלם (להשאיר את |- במחסנית) 2> להניח שאנו קוראים רצף מתאים . אם אנו קוראים רצף מתאים על כל a שנקרא נדחוף AA למחסנית אם לאחר שקראנו רצף מסוים של a אנו קוראים b אנו מבצעים מחיקה של A יחיד ומעבר למצב שיודע לקבל רק b ולמחוק A מהמחסנית . אם הגענו למחסנית ריקה סיימנו .והמילה בשפה . אם אנו קוראים עוד אות לאחר המחסנית הריקה נתקעים . (למקות שבתחילה יכולנו לבחור בעזרת האי דטרמיניזם) זה בגדול .

 

[ELIELI22]

הרעיון הוא אי דטרמיניזם ..

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

 

[ELIELI22]

ככל הנראה ...

נפתרו השאלות 4,6 5 ארוכה מדי וקיבלתי גם כך הארכה עד היום , אז אני כנראה מגיש בלי 5 . אין לי שמץ של מושג איך לפתור את השאלה הזו .. אני אנסה לחשוב טיפה ואז אני כבר צריך לנסוע לשים את המכתב בתיבה . יום טוב .