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