רוטר - עזרה באוטומטים, בהקשר מחלקות שקילות וכו

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"עזרה באוטומטים, בהקשר מחלקות שקילות וכו"

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #20475	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 20475

coler
חבר מתאריך 21.3.02
1473 הודעות, דרג אמינות חבר זה

15:44 08.12.13

עזרה באוטומטים, בהקשר מחלקות שקילות וכו

עבר עריכה לאחרונה בתאריך 09.12.13 בשעה 00:32 על-ידי danny444 (מפקח)

https://www.dropbox.com/s/5mpq1l0jkeia7d4/IMAG0044.jpg#
למי שיש כיוון, אשמח
תודה רבה

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
מכתב:	matan13	10.12.13 23:13	1

matan13
חבר מתאריך 14.7.08
19469 הודעות, דרג אמינות חבר זה

23:13 10.12.13

1. מכתב:
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 10.12.13 בשעה 23:23 בברכה, matan13

תוכיח את טענת עזר הבאה: מחרוזת מנתבת משני מצבים למצב בודד באוטומט עם k מצבים היא מגודל לכל היותר k^2.
ואז תבנה מהמילים הללו מילה באורך k^3 מנתבת באוטומט.. אני אתן לך את תחילת הבנייה, ומשם הכל אותו דבר רק עם מצבים אחרים:
לפי טענת העזר קיימת w שמנתבת בין מצב q1 ו-q2 לq3(או כל מצב אחר..) אורכה לכל היותר k^2.
כעת תיקח מצב שלישי q4, ואז: delta(q4,w)=q5 כלשהו, ובין q5 ל-q3 יש לפי טענת העזר מילה u מנתבת למצב יחיד q6 באורך לכל היותר k^2.
כעת תסתכל במילה wu, היא מאורך לכל היותר 2k^2, והיא מנתבת את המצבים q1 וq2 וq4 לq6.

ואם תרצה לקרוא עוד:
http://en.wikipedia.org/wiki/Synchronizing_word

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד