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

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

מושגים יסודיים בשפות פורמליות

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

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

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

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

דוגמאות

דוגמאות לאלפבית

• האלפבית האונרי - מכיל סימן יחיד, למשל $\ \Sigma =\{1\}$
• האלפבית הבינארי - מכיל את הסימנים "0" ו-"1". $\ \Sigma =\{0,1\}$
• האלפבית האנגלי: $\Sigma =\{a,c,b,\ldots ,z\}$

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

דוגמאות למילים

נניח כי האלפבית הוא האלפבית הבינארי $\ \Sigma =\{0,1\}$. נבחן את הדוגמאות הבאות:

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

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

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

דוגמאות לשפות פורמליות

• השפה הריקה (אינה מכילה אף מילה). $L=\{\}=\emptyset$
• השפה שמילותיה הן בדיוק סימני האלפבית: $\ L=\Sigma$. למשל, עבור האלפבית הבינארי: $\ L=\{0,1\}$
• שפת כל הצירופים הסופיים מעל האלפבית. לשפה זאת מספר מילים אינסופי מכיוון שאין בה מגבלה על אורך המילים. מסמנים $\ L=\Sigma ^{*}$. סימון זה יוסבר בהמשך.
• השפה המכילה מילה יחידה - את המילה הריקה $L=\{\varepsilon \}$. יש לשים לב שזו אינה השפה הריקה, מכיוון ששפה זו מכילה מילה אחת, והשפה הריקה מכילה 0 מילים (אינה מכילה אף מילה).

פעולות על שפות

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

• שרשור שפות – יהיו $\ L_{1},L_{2}$ שפות מעל אלפבית כלשהו. השרשור של $\ L_{1}$ עם $\ L_{2}$ מסומן $L_{1}\circ L_{2}$ ולפעמים $\ L_{1}L_{2}$, ומוגדר ככל המחרוזות המתחילות במחרוזת מתוך $\ L_{1}$ אליה משורשרת מחרוזת מ-$\ L_{2}$. באופן פורמלי:

$L_{1}\circ L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$

• חזקה – חזקה של שפה היא שרשור השפה לעצמה מספר פעמים. למשל $L_{1}^{2}=L_{1}\circ L_{1}$.
• כוכב (כוכב קליני) – פעולת הכוכב מוגדרת באופן הבא:

$L^{*}=\{\varepsilon \}\cup L\cup L^{2}\cup L^{3}\ldots$

כלומר, השפה המכילה את המילה הריקה, את כל המילים של השפה $\ L$ ואת כל השרשורים של $\ L$ לעצמה.

נשים לב שאם השפה $\ L$ מכילה רק מילים באורך 1, אז השפה $\ L^{2}$ מכילה את כל המילים באורך 2 שמורכבות מהסימנים ב-$\ L$. באופן דומה, $\ L^{3}$ מכילה את כל המחרוזות באורך 3 וכך הלאה. לכן - הפעלת הכוכב נותנת למעשה את כל המחרוזות, בכל אורך שהוא (כולל 0), המורכבות מה"סימנים" המוכלים ב-$\ L$.

כעת ניתן להבין כי הסימון $\ \Sigma ^{*}$ מסמל את כל המחרוזות, בכל אורך שהוא, שמכילות אך ורק סימנים מ־$\ \Sigma$.

• השלמה – השפה המתקבלת מכל המילים ב־$\ \Sigma ^{*}$ שאינן ב־L. פורמלית,

${\overline {L}}=\Sigma ^{*}\smallsetminus L$

דוגמאות

• עבור האלפבית הבינארי: $\ \Sigma ^{2}=\{00,01,10,11\}$
• כאמור לעיל, $\Sigma ^{*}=\{\varepsilon ,0,1,00,01,10,11,000,\ldots \}$.
• עבור $\ L=\{a,bc\}$ נקבל $\ L^{2}=\{aa,abc,bca,bcbc\}$.
• עבור אלפבית בינארי ו־$L=\{\varepsilon ,0,00,000,\ldots \}$ השפה המשלימה היא ${\overline {L}}=\{1,01,10,11,001,010,011,\ldots \}$

הפרק הקודם: מבוא

שפות פורמליות

הפרק הבא: אוטומט סופי דטרמיניסטי