אוטומטים

[M a r i n a 8 4]

אוטומטים

שלום! אני ניסיתי לצייר את האוטומט שמתאר שפה מעל {0,1} ככה שהמספר הבינארי שמתקבל הוא מתחלק ב-3 והוא גדול מ-31 בעזרת אוטומט מכפלה, ויצא לי אוטומט עם 21 מצבים! מישהו יודע אולי על דרך יותר קצרה לצייר אוטומט כזה? תודה.

 

[johnny d]

לי יצא אוטומט עם 13 מצבים

כל מצב מראה כמה ספרות (without leading zero's) ומה התוצאה למספר מודולו 3. יש מצב בו ישנם אפס ספרות (זה המצב ההתחלתי) ממנו רק עם 1 ניתן להגיע למצב בו יש ספרה אחת משם ניתן להגיע לשני מצבים בעלי שני ספרות ומשם ניתן להגיע לשלוה מצבים בעלי 3 ספרות וכו עד שיש 5 ספרות ונשארים באותו הסטטאטוס (5 ספרות או יותר זה לא משנה זה כבר גדול מ31). בכל מקרה צריך לשים לב שמספר בעל ספר אחת יש רק 1 הוא: "1", ובעלי 2 ספרות יש שניים: "10" ו- "11" ...