במתמטיקה, לוגיקה ומדעי המחשב, שפה פורמלית היא קבוצה של רצפים סופיים של סימנים מתוך אלפבית סופי Σ. האלפבית (קבוצת סימנים) הוא המקור שממנו בונים את המילים. מילה היא רצף סופי של אותיות מהאלפבית. המילה הריקה היא רצף באורך 0 ומסומנת בדרך-כלל ε; היא יכולה להיות שייכת או לא שייכת לשפה. למרות שהאלפבית וסימניו סופיים, שפה פורמלית יכולה להיות אינסופית, מכיוון שאין גבול על אורך המילים. = מושגים יסודיים בשפות פורמליות = אלפבית: קבוצה סופית של סימנים שממנה מייצרים מילים. מילה: רצף סופי של סימנים מהאלפבית. המילה הריקה: רצף באורך אפס, מסומן ε. שפה פורמלית: קבוצה של מילים מעל אלפבית נתון; הקבוצה יכולה להיות אינסופית. = דוגמאות של שפות פורמליות = אחת הדרכים להגדיר שפה פורמלית היא באמצעות מילון - רשימה מפורשת של כל המילים השייכות לה. שיטה זו מתאימה רק לשפות סופיות. כדי לתאר שפות אינסופיות משתמשים בכלים אחרים. = תת-קבוצה של שפה פורמלית = אפשר להגדיר שפה גם בעזרת דקדוק פורמלי. דקדוק כזה מייצר כל מילה חוקית לפי חוקים תחביריים. כך אפשר, במובן עקרוני, לתאר משפטים של שפה טבעית בעזרת דקדוק פורמלי, גם אם מספרם אינסופי. דרך נוספת היא מבני-יצירה: מתחילים מתת-קבוצה סופית של מילים ומגדירים יחסים ופעולות שממנו בונים את שאר המילים. בגישה הזו משתמשים באלגברת יצירה חופשית כדי להגדיר פונקציות ברקורסיה על מבנה הבנייה ולהוכיח טענות על מילים. = כריעות וכריעות למחצה = שפה נקראת כריעה אם קיים אלגוריתם (תהליך ממוחשב) שמקבל כל מילה ומחליט בתוך זמן סופי אם היא שייכת לשפה או לא. שפה נקראת כריעה למחצה אם קיים אלגוריתם שעוצר באין-ספיק עבור כל מילה השייכת לשפה, אך על מילה שאינה שייכת לא בהכרח יעצור. כל שפה כריעה היא גם כריעה למחצה. במשפחת שפות מסדר ראשון יש משפט של צ'רץ' שאומר: אם השפה מכילה את שוויון והקבועים המתאימים, אז קבוצת הנוסחאות האמיתיות לוגית אינה כריעה.
שפה פורמלית היא אוסף של מילים. מילים הן רצפים של אותיות מתוך אלפבית. אלפבית הוא קבוצה קטנה של סימנים. יש גם מילה מיוחדת בלי אותיות, זו המילה הריקה. המילה הריקה מסומנת בדרך-כלל ב־ε. למרות שהאלפבית סופי, אפשר שיהיו הרבה מאד מילים בשפה. = מושגים יסודיים בשפות פורמליות = אלפבית = קבוצת סימנים. מילה = רצף של סימנים מהאלפבית. המילה הריקה = רצף שאינו מכיל אותיות, מסומן ε. = דוגמאות של שפות פורמליות = אחת הדרכים להגדיר שפה היא לרשום מילון. מילון הוא רשימה של כל המילים בשפה. שיטה זו עובדת כשיש מעט מילים. = תת-קבוצה של שפה פורמלית = אפשר גם לתאר שפה בעזרת חוקים, שנקראים דקדוק פורמלי. הדקדוק מראה איך להרכיב מילים ומשפטים. יש שיטה שנייה: מתחילים מקבוצה קטנה של מילים ובונים מהן מילים חדשות בעזרת פעולות חיבור. = כריעות וכריעות למחצה = אם יש אלגוריתם שתמיד עוצר ומגיד כן או לא, השפה נקראת כריעה. אם האלגוריתם עוצר רק כשהתשובה היא כן, אך לפעמים לא עוצר כשהתשובה לא, השפה נקראת כריעה למחצה. יש משפט מתמטי של צ'רץ' שאומר שלפעמים אי-אפשר לבנות אלגוריתם כזה לכל הנוסחאות (נוסחה = משפט מתמטי).
תגובות גולשים