אוטומטים ושפות פורמליות/שפות פורמליות

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

שפה פורמלית היא קבוצה כלשהי של מחרוזות, כאשר כל אות במחרוזת היא מתוך קבוצה סופית , המכונה "האלפבית של השפה". את המחרוזות של השפה נהוג לכנות "מילים".

מושגים יסודיים בשפות פורמליות[עריכה]

א. אלפבית (פורמלי): קבוצה של סימנים, או אותיות, שמהם מייצרים את המילים בשפה. קבוצה זו היא סופית.

ב. מילה (פורמלית): רצף סופי של אותיות מהאלפבית. מקובל לומר שמילה המכילה רק אותיות מאלפבית מסוים היא מעל האלפבית המסוים. מילה מסומנת בדרך כלל באות .

ג. המילה הריקה: רצף אותיות באורך 0. למילה הריקה, המסומנת בדרך-כלל באות , יש מעמד זהה לכל מילה אחרת מעל האלפבית, והיא יכולה להיות שייכת או לא שייכת לשפה.

ד. שפה (פורמלית): קבוצה של מילים. למרות שהאלפבית הוא סופי ואורך כל מילה הוא סופי, השפה יכולה להיות אינסופית; זאת משום שמספר המילים אינו חסום. שפה מסומנת בדרך כלל באות .

דוגמאות[עריכה]

דוגמאות לאלפבית[עריכה]

  • האלפבית האונרי - מכיל סימן יחיד, למשל
  • האלפבית הבינארי - מכיל את הסימנים "0" ו-"1".
  • האלפבית האנגלי:

לרוב האלפבית מסומן באות יוונית גדולה כגון או .

דוגמאות למילים[עריכה]

נניח כי האלפבית הוא האלפבית הבינארי . נבחן את הדוגמאות הבאות:

  • 0000 - מילה באורך 4.
  • 1 - מילה באורך 1 (וגם אות באלפבית).
  • - המילה הריקה, אורכה 0.

דוגמאות למחרוזות שאינן מילים מעל :

  • 012 - מכילה את האות "2" שאינה באלפבית הבינארי.
  • - בעלת אורך אינסופי, ולכן אינה מוגדרת כמילה.

דוגמאות לשפות פורמליות[עריכה]

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

פעולות על שפות[עריכה]

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

  • שרשור שפות – יהיו שפות מעל אלפבית כלשהו. השרשור של עם מסומן ולפעמים , ומוגדר ככל המחרוזות המתחילות במחרוזת מתוך אליה משורשרת מחרוזת מ-. באופן פורמלי:
  • חזקה – חזקה של שפה היא שרשור השפה לעצמה מספר פעמים. למשל .
  • כוכב (כוכב קליני) – פעולת הכוכב מוגדרת באופן הבא:
כלומר, השפה המכילה את המילה הריקה, את כל המילים של השפה ואת כל השרשורים של לעצמה. נשים לב שאם הקבוצה מכילה רק מילים באורך 1, אז הקבוצה מכילה את כל המילים באורך 2 שמורכבות מהסימנים ב-. באופן דומה, מכילה את כל המחרוזות באורך 3 וכך הלאה. לכן - הפעלת הכוכב נותנת למעשה את כל המחרוזות, בכל אורך שהוא (לרבות 0), המורכבות מה"סימנים" המוכלים ב-.
כעת ניתן להבין כי הסימון מסמל את כל המחרוזות, בכל אורך שהוא, שמכילות אך ורק סימנים מ־.
  • השלמה – השפה המתקבלת מכל המילים ב־ שאינן ב־L. פורמלית,

דוגמאות[עריכה]

  • עבור האלפבית הבינארי:
  • כאמור לעיל, .
  • עבור נקבל .
  • עבור אלפבית בינארי ו־ השפה המשלימה היא


הפרק הקודם:
מבוא
שפות פורמליות הפרק הבא:
אוטומט סופי דטרמיניסטי