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

תוכן שנמחק תוכן שנוסף
Crazy Ivan (שיחה | תרומות)
מאין תקציר עריכה
Gran (שיחה | תרומות)
שורה 38:
כאמור, שפה היא קבוצה של מילים, ולכן ניתן לבצע עליה על פעולה שניתן לבצע על קבוצות, למשל איחוד, חיתוך, החסרה וכו'. נשים דגש על מספר פעולות חשובות:
 
* '''שרשור שפות''' - יהיו <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 = \{ w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\}</math></center>
* '''חזקה''' - חזקה של שפה היא שרשור השפה לעצמה מספר פעמים. למשל <math>L_1^2 = L_1\circ L_1</math>.
* '''כוכב''' (כוכב קליני) - פעולת הכוכב מוגדרת באופן הבא:
<center><math> L^* = \{\varepsilon\} \cup L \cup L^2 \cup L^3 \ldots</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^*</math> שאינן ב־L. פורמלית,
<center><math>\overline{L} = \Sigma^* \smallsetminus L</math></center>
=== דוגמאות ===
*עבור האלפבית הבינארי: <math>\ \Sigma^2=\{00,01,10,11\}</math>
*כאמור לעיל, <math>\Sigma^* =\{\varepsilon, 0,1,00,01,10,11,000,\ldots \}</math>.
*עבור <math>\ L=\{a, bc\}</math> נקבל <math>\ L^2 = \{ aa, abc, bca, bcbc\}</math>.
* עבור אלפבית בינארי ו־<math>L=\{\varepsilon, 0, 00, 000, \ldots \}</math> השפה המשלימה היא <math>\overline{L}=\{1, 01, 10, 11, 001, 010, 011, \ldots \}</math>
 
{{אוטומטים ושפות פורמליות|מוגבל}}