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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
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 = \{ ab \mid a\in L_1, b\in L_2\}</math></center>
* '''חזקה''' - חזקה של שפה היא שרשור השפה לעצמה מספר פעמים. למשל <math>L_1^2 = L_1\circ L_1</math>.
שורה 46:
:כעת ניתן להבין, כי הסימון <math>\Sigma^*</math> מסמל את כל המחרוזות, בכל אורך שהוא, שמכילות אך ורק סימנים מ-<math>\Sigma</math>.
 
=== דוגמאות ===
*עבור האלפבית הבינארי, <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>.
 
[[קטגוריה:אוטומטים ושפות פורמליות]]