אוטומטים ושפות פורמליות/שפות פורמליות: הבדלים בין גרסאות בדף

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

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

* האלפבית הבינארי,האונרי - מכיל אתסימן הסימניםיחיד, "0" ו"1".למשל <math>\ \Sigma=\{0,1\}</math>

* האלפבית האנגליהבינארי - מכיל את הסימנים "0" ו-"1". <math>\ \Sigma=\{a0,c,b, \ldots 1\}</math>

* האלפבית האונרי, מכיל סימן יחיד, למשלהאנגלי: <math>\Sigma=\{1a,c,b, \ldots,z \}</math>

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

* 0000 - מילה באורך 4.

* 1 - מילה באורך 1 (וגם אות באלפבית)...)

דוגמאות למחרוזות שאינן מילים מעל <math>\Sigma</math>:

* 012 - מכילה את האות "2" שאינה באלפבית הבינארי.

* <math>0000\ldots</math> - בעלת אורך אינסופי, ולכן אינה מוגדרת כמילה.

* השפה שמילותיה הן בדיוק סימני האלפבית.: <math>\ L= \Sigma</math>. למשל, עבור האלפבית הבינארי,: <math>\ L=\{0,1\}</math>

* שפת כל הצירופים הסופיים מעל האלפבית. לשפה זאת מספר מילים אינסופי מכיוון שאין בה מגבלה על אורך המילים. מסמנים <math>\ L=\Sigma^*</math>. סימון זה יוסבר בהמשך.

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

* '''שרשור שפות''' - יהיו <math>\ L_1, L_2</math> שפות מעל אלפבית כלשהו. השרשור של <math>\ L_1</math> עם <math>\ L_2 </math> מסומן <math> L_1\circ L_2</math> ולפעמים <math>\ L_1L_2</math>, ומוגדר ככל המחרוזות המתחילות במחרוזת מתוך <math>\ L_1</math> אליה משורשרת מחרוזת מ-<math>\ L_2</math>. באופן פורמלי:

<center><math>L_1\circ L_2 = \{ abw_1 w_2 \mid aw_1 \in L_1, bw_2 \in L_2\}</math></center>

* '''כוכב''' (כוכב קליני) - פעולת הכוכב מוגדרת באופן הבא:

:כלומר, השפה המכילה את המילה הריקה, את כל המילים של השפה <math>\ L </math>, וכלואת כל השרשורים של <math>\ L</math> לעצמה. נשים לב שאם הקבוצה <math>\ L</math> מכילה רק מילים באורך 1, אז הקבוצה <math>\ L^2</math> מכילה את כל המילים באורך 2 שמורכבות מהסימנים ב-<math>\ L</math>. באופן דומה, <math>\ L^3</math> מכילה את כל המחרוזות באורך 3 וכך הלאה. לכן - הפעלת הכוכב נותנת למעשה את כל המחרוזות, בכל אורך שהוא (לרבות 0), המורכבות מה"סימנים" המוכלים ב-<math>\ L</math>.

:כעת ניתן להבין, כי הסימון <math>\ \Sigma^*</math> מסמל את כל המחרוזות, בכל אורך שהוא, שמכילות אך ורק סימנים מ-<math>\ \Sigma</math>.

*עבור האלפבית הבינארי,: <math>\ \Sigma^2=\{00,01,10,11\}</math>

*עבור <math>\ L=\{a, bc\}</math> נקבל <math>\ L^2 = \{ aa, abc, bca, bcbc\}</math>.