תורת האוטומטים - מונחים

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

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

מושגי יסוד[עריכת קוד מקור | עריכה]

  • א"ב פורמלי: קבוצה סופית של סימנים ("אותיות").
  • מילה פורמלית: סדרה סופית של אותיות השייכות לא"ב נתון.
  • המילה הריקה: מילה שאורכה 0, נהוג לסמן את מילה זו על ידי .
  • שפה פורמלית: קבוצת מילים פורמליות.

פעולות על מילים[עריכת קוד מקור | עריכה]

  • אורך של מילה: האורך של מילה שווה למס' האותיות שבה. אורכה של מילה מסומן ב.
  • מס' מופעי אות במילה: מס' מופעי במילה יסומן ב.
  • היפוך מילים: תהי . היפוכה יסומן ב ויתקיים .
  • שרשור מילים: יהיו שתי מילים כך ש שרשורן יסומן על ידי או ויוגדר כ-.
  • חזקה של מילה: מוגדרת רקורסיבית כשרשור של לעצמה פעמים - .

פעולות על שפות[עריכת קוד מקור | עריכה]

  • איחוד/חיתוך/השלמה: פעולות אלו זהות לפעולות איחוד חיתוך והשלמה מתורת הקבוצות, רק שאלו פועלות על שפות (כאשר העולם הוא ).
  • שרשור שפות: שרשור של שתי שפות מוגדר כקבוצת כל המילים הנוצרות משרשור מילה אחת מהשפה הראשונה ומילה אחת מהשנייה. כלומר, יהיו שפות, שרשורן יסומן ב-.
  • חזקה של שפה: החזקה ה--ית של שפה מוגדרת כשפת כל המילים הנוצרות על ידי שרשור של מילים מאותה שפה. כלומר, תהי שפה פורמלית. חזקתה תוגדר כך - ולכל יתקיים .
  • סגור קלין: סגור קלין של שפה יסומן ב ויוגדר כך - .
  • סגור חיובי: הסגור החיובי של שפה מוגדר בדומה לסגור קלין שלה - הסגור החיובי מסומן ב ומוגדר כך - .

ההיררכיה של חומסקי[עריכת קוד מקור | עריכה]

ההיררכיה של חומסקי מחלקת את השפות הפורמליות ל-4 סוגים לפי הדקדוקים היוצרים אותן (כל אחד מהדקדוקים בהיררכיה מוגבל יותר מאלו שמעליו):

דרכים להצגת שפה פורמלית[עריכת קוד מקור | עריכה]

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

משפטים[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]