# אוטומט סופי

### מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).
דלת כאוטומט סופי

בתורת החישוביות במדעי המחשב, אוטומט סופי הוא מכונה מופשטת בעלת זכרון מוגבל המגדירה שפה פורמלית.

קיימים שני סוגים של אוטומטים סופיים – אוטומט סופי דטרמיניסטי (DFA –‏ Deterministic Finite Automaton) ואוטומט סופי לא דטרמיניסטי (NFA –‏ Nondeterministic Finite Automaton).

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

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

ניתן להוכיח כי כל אוטומט סופי לא־דטרמיניסטי שקול לאוטומט סופי דטרמיניסטי. כלומר, היעדר הדטרמיניזם אינו מוסיף לכוחו החישובי של האוטומט הסופי (בשונה מבאוטומט מחסנית, לדוגמה).

שפות המתקבלות על ידי אוטומט סופי נקראות שפות רגולריות ונוצרות על ידי דקדוקים רגולריים.

ניתן להתייחס גם לריצות של אוטומטים סופיים על מילים אינסופיות (סדרות אינסופיות של אותיות מהאלפבית). ניתן להגדיר תנאים שונים להגדרת קבלת מילים במקרה זה. למשל, באוטומט בוקי (Büchi) ריצה תקרא מקבלת אם היא מבקרת במצב מקבל אינסוף פעמים.

## [עריכה] לקריאה נוספת

- שמואל זקס ונסים פרנסיז, אוטומטים ושפות פורמליות, פרקים 2-5 (כרך א'), הוצאת האוניברסיטה הפתוחה, 2000.

## [עריכה] ראו גם

- תורת האוטומטים - מונחים
- ההיררכיה של חומסקי
- אוטומט מחסנית
- מכונת טיורינג

מקור: http://he.wikipedia.org../../../%D7%90/%D7%95/%D7%98/%D7%90%D7%95%D7%98%D7%95%D7%9E%D7%98_%D7%A1%D7%95%D7%A4%D7%99.html

קטגוריה: חישוביות

##### Views

- ערך
- שיחה
- גרסה נוכחית

##### קהילה

- שער הקהילה
- עזרה
- דלפק ייעוץ
- מזנון
- יצירת קשר
- ספר אורחים

##### חיפוש

##### שפות אחרות

- English
- Български
- Česky
- Deutsch
- Español
- Suomi
- Français
- Italiano
- 日本語
- Nederlands
- Português
- Română
- Русский
- Svenska
- Українська
- 中文