Finite state machine example with comments.gif בתורת החישוביות במדעי המחשב, אוטומט סופי הוא מכונה מופשטת בעלת זכרון מוגבל המגדירה שפה פורמלית.

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

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

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

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

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

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

לקריאה נוספת

• "אוטומטים ושפות פורמליות", הוצאת האוניברסיטה הפתוחה.

ראו גם

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

Finite state machine | Краен автомат | Konečný automat | Endlicher Automat | Autómata finito | Äärellinen automaatti | Automate fini | Automa a stati finiti | 有限オートマトン | Eindige toestandsautomaat | Máquina de estado finito | Automat finit | Конечный автомат | Ändlig automat | 有限状态自动机