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