אוטומט סופי דטרמיניסטי

באוטומט סופי דטרמיניסטי מלא

• אורך הקלט הוא סופי

• חייב להיות מצב מלכודת

• מספר המצבים סופי, ומכל מצב יש חץ אחד לכל אחד מהקלטים

• מספר המצבים קטן מחמישים, ויש מצב מקבל אחד בלבד

Answer explanation

מספר המצבים סופי, אך לא מוגבל במספר כלשהו.

יתכן ואורך הקלט לא יהיה סופי. למשל: רצף של 0 ולאחריו רצף של 1. אין הגבלה בכמות האחדים והאפסים.

יכול להיות יותר ממצב מקבל אחד.

לא חייב להיות מצב מלכודת.

?מה המילה הקצרה ביותר שמקבל האוטומט

• מילה ריקה

• b

• a

• ab

?איזו מילה/שפה לא מתקבלת על ידי האוטומט

• aaa

• bbb

• aaabbb

Answer explanation

האוטומט מקבל מילים שמתחילות

ברצף של a

באורך כלשהו

ולאחריו רצף של b

באורך כלשהו

שגדול מאפס

ניתן לכתוב אוטומט שמקבל את המילה הריקה בלבד

• 
• בלתי אפשרי. כל אוטומט חייב לקבל מילה בנוסף למילה הריקה

• אפשרי, אלא שכאן חסר מידע לגבי הקלט

?מתי לא ניתן להשתמש בלולאה עצמית

• בכל אוטומט חייבת להופיע לולאה עצמית

• כאשר מתבצעת ספירה

• באוטומט שבודק רצפים

• במצב מלכודת

Answer explanation

זו דוגמה לאוטומט שבודק רצפים עם שימוש בלולאה עצמית: אם קיים רצף של a

ולאחריו רצף של b

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

הדרך אותה עוברת מילה על פני האוטומט החל מהמצב ההתחלתי ועד לסיום המילה, נקראת

Answer explanation

מסלול יכול להסתיים במצב מקבל או במצב לא מקבל.

מסלול מקבל מסתיים תמיד במצב מקבל.

?איזו שפה מקבל האוטומט

• כל המספרים שמתחילים

  ב - 0 או ב - 9

• את המילה הריקה

• כל הספרות בתחום

  0 - 9

• כל המספרים השלמים חיוביים, כולל המילה הריקה

?איזו שפה מקבל האוטומט

• כל המספרים שלא מתחילים ב - 5 ולא מסתיימים ב - 6

• כל המספרים שלא מתחילים ב - 5, ולא מכילים את הרצף 56

• כל המספרים שלא מתחילים ב - 5 ומכילים את הרצף 56

• כל המספרים שלא מתחילים ב - 5 והספרה שלפני האחרונה היא 5

מה צריך לשנות באוטומט כדי שהמספרים יתחילו גם ב - 5?

• להוסיף לולאה עצמית למצב ההתחלתי עם הערך 5

• אין אפשרות להתחיל ב - 5 כדי שלא יתקבל רצף 56 בלולאה העצמית

• להוסיף על החץ מהמצב ההתחלתי את 5

• להוסיף מעבר מהמצב ההתחלתי

  q2 - ל

  עם הקלט 5

?איזו שפה מקבל האוטומט

• מספר הגדול מ - 999

• מספר המכיל שלוש פעמים 9, ולא מסתיים ב - 9

• מספר המכיל את הרצף 999 ולא מסתיים ב - 9

• מספר שאורכו לפחות 4 ומכיל מספר אי זוגי של 9