אוטומטים ושפות פורמליות/שפות פורמליות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
פעולות על קבוצות |
מ ←פעולות על שפות: הגהה |
||
שורה 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 = \{ ab \mid a\in L_1, b\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>\Sigma^*</math> מסמל את כל המחרוזות, בכל אורך שהוא, שמכילות אך ורק סימנים מ-<math>\Sigma</math>.
| |||