שפה פורמלית

שפה פורמלית היא אוסף של מילים. מילים הן רצפים של אותיות מתוך אלפבית. אלפבית הוא קבוצה קטנה של סימנים. יש גם מילה מיוחדת בלי אותיות, זו המילה הריקה. המילה הריקה מסומנת בדרך-כלל ב־ε. למרות שהאלפבית סופי, אפשר שיהיו הרבה מאד מילים בשפה. = מושגים יסודיים בשפות פורמליות = אלפבית = קבוצת סימנים. מילה = רצ...