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

ראשי>סיכומים>מילון מונחים

הגדרות בסיסיות

הגדרות:

א"ב - קבוצה סופית לא ריקה של סימנים, מסמנים ב- .

מחרוזת/מילה - סידרה סופית של סימנים מעל נתון.

אורך של מילה - מס' הסימנים שבמילה, מסמנים ב- .

מס' מופעים של אות במילה מסמנים ב-#, למשל מס' המופעים של a ב-w יסומן ע"י .

מילה ריקה - מילה באורך 0, מסמנים ב- .

שפה - קבוצה של מילים מעל נתון. שפה יכולה להיות סופית או אינסופית. שפה ריקה מסמנים ב- . הבחנה: .

פעולות על מילים:

שרשור - שרשור של שתי מילים הוא המילה הנוצרת ע"י הדבקת השניה לראשונה. למשל, אם ו- , אז . שרשור פעולה אסוציאטיבית אך לא קומוטטיבית, אלא אם או - במקרה כזה .

חזקה - תהי w מילה, ויהי . אזי, מכפלה של w בעצמה i פעמים. אם , אז .

היפוך - אם , כאשר סימנים, אז . למשל, אם , אז .

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