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