נושא: שאלות פילוסופיות על מודלים חישוביים

נשלח בתאריך: 06 November 2006 בשעה 23:17 | IP רשוּם

1. צריכה לבנות אוטומט סופי לא דרמיניסטי שמקבל את שפת המילים מעל א-ב {9...0,1} שבהן מופיעה הספרה האחרונה לפחות עוד פעם אחת <לדוגמא: 1232 תתקבל, 123 לא תתקבל>

2. איך מוכיחים שלכל שפה רגולרית L שאיננה מכילה את המילה הריקה, יש אוטמט סופי לא דרמינסטי שם מצב התחלתי יחיד ומצב מקבל יחיד המזהה את L?

3. האם לכל שפה רגולרית יש אוטמט שמזהה אותה? <הוכחה?> 

האם כל שפה שאוטומט מזהה אותה, היא אכן שפה רגולרית? 

נשלח בתאריך: 06 November 2006 בשעה 23:25 | IP רשוּם

אבל אבל אבל-

זותומרת שאני צריכה שכל מצב יזכור את המספרים שעברו דרכו????

כמה מצבים זה צריך להיות?