שפה פורמלית
מתוך ויקיפדיה, האנציקלופדיה החופשית
במתמטיקה, לוגיקה ומדעי המחשב, שפה פורמלית היא קבוצה כלשהי של רצפים סופיים של סימנים מקבוצה סופית A. לקבוצה A קוראים האלפבית של השפה, ומסמנים אותה לרוב באות היוונית Σ. והפריטים בקבוצה L נקראים מילים בשפה.
תוכן עניינים |
[עריכה] מושגים יסודיים בשפות פורמליות
א. אלפבית (פורמלי): קבוצה של סימנים, או אותיות, שמהם מייצרים את המילים בשפה. קבוצה זו היא סופית.
ב. מילה (פורמלית): רצף סופי של אותיות מהאלפבית. מקובל לומר שמילה היא מעל אלפבית מסוים.
ג. המילה הריקה: רצף אותיות באורך 0. למילה הריקה, המסומנת בדרך-כלל באות 
, יש מעמד זהה לכל מילה אחרת מעל האלפבית, והיא יכולה להיות שייכת או לא שייכת לשפה.
ד. שפה (פורמלית): קבוצה של מילים. למרות שהאלפבית הוא סופי ואורך כל מילה הוא סופי, השפה יכולה להיות אינסופית; זאת משום שאורך כל מילה אינו חסום.
כאשר מתייחסים לשפה טבעית, האלפבית לעתים מכונה מכונה "לקסיקון" או "אוצר מילים", והרצפים מעליו, כלומר הפריטים בשפה, נקראים "משפטים". כדאי לשים לב שלפי מוסכמה זו האלפבית מכונה "מילים", והמילים מכונות "משפטים" – כך שהטרמינולוגיה הנ"ל אינה עושה חסד עם בהירות המינוח.
[עריכה] דוגמאות
- השפה הריקה (אינה מכילה אף מילה).
- השפה שמילותיה הן בדיוק סימני האלפבית.
- שפת כל הצירופים הסופיים מעל האלפבית.
[עריכה] תת-קבוצה של שפה פורמלית
העניין בשפות פורמליות מתעורר בעיקר בנוגע לקושי לאפיינן. בהנתן אלפבית Σ, קל למצוא מייד כמה שפות פורמליות המוגדרות מעליו. שלוש מהן כבר ראינו: את השפה-הריקה (שאינה מכילה אף מילה), את השפה המכילה אך ורק את סימני האלפבית או את השפה המכילה את כל הביטויים הסופיים מעל האלפבית. איך כיצד ניתן לאפיין שפות אחרות, שאינן אחת מאלה?
הדרך הישירה היא באמצעות "מילון", רשימה מפורשת של רציפי אותיות, אשר הן (ורק הן) יהוו את המילים השייכות לשפה. למשל, את השפה הפורמלית "המילים התקניות של השפה העברית" מעל האלפבית, אין ברירה אלא לאפיין בדרך זו (כל זאת מנקודת מבט פורמלית. מבחינה בלשנית, המילים בשפה טבעית אינן מאופיינת באמצעות מילון). בדרך כלל שיטה זו אינה טובה, ואף אינה אפשרית (כך למשל, בכל מקרה בה השפה מכילה מספר אינסופי של מילים).
דרך נוספת לאפיין שפה פורמלית, היא באמצעות דקדוק פורמלי. כאשר נתונות כמה שפות אשר כולן מוגדרות מעל אותו האלפבית (ואותן אנו יודעים לאפיין, למשל בעזרת מילון), הדקדוק הפורמלי מאפשר לאפיין באמצעותן שפה חדשה, אף היא מעל אותו אלפבית. כך למשל ניתן להגדיר (באופן עקרוני ומקורב, לפחות) "דקדוק פורמלי" של השפה העברית, שיפשר להרכיב את כל המשפטים בשפה העברית (אשר מספרם אינסופי) באמצעות "שפת השורשים בעברית" (קבוצה סופית ובת-אפיון באמצעות מילון).
דרך דומה לאפיון שפה פורמלית, המקובלת מאוד במתמטיקה, היא באמצעות מבני-יצירה. בדרך זו נעזרים בתת-קבוצה של מילות השפה אותה רוצים לאפיין (תת-קבוצה סופית, בדרך כלל), ומגדירים אוסף של יחסים על תת-קבוצה הזו, אשר באמצעותו ניתן לאפיין את כל המילים בשפה.
לבסוף, נשאלת השאלה הכללית: בהנתן שפה, האם בכלל ניתן לאפיינה באופן "מועיל"? שפה עבורה התשובה חיובית, מכונה "שפה כריעה".
[עריכה] אפיון באמצעות דקדוק פורמלי
ראה דקדוק פורמלי.
[עריכה] אפיון באמצעות מבני-יצירה
באמצעות מבני-יצירה ניתן לאפיין שפה, כך שהעצמים הנוצרים הם מילים בשפה. דרך זו מקובלת בלוגיקה המתמטית, בשל האפשרות לאפיינם באמצעות אלגברת יצירה חופשית, המאפשרת להגדיר היטב פונקציות ברקורסיה על הפעולות של מבנה-היצירה, ולהוכיח טענות הנוגעות למילים ברקורסיה על עץ הבנייה שלהם. דוגמאות רלוונטיות אפשר למצוא, למשל, בערכים תחשיב הפסוקים ו-תחשיב היחסים.
[עריכה] כריעות וכריעות למחצה
על שפה A נאמר שהיא "כריעה" אם ורק אם קיים אלגוריתם המקבל כל צירוף סופי של סימנים מעל האלפבית של השפה, ועוצר כעבור מספר סופי של צעדים עבור כל מילה השייכת ל-A בהכרזה "המילה שייכת ל-A", ועבור כל מילה שאינה שייכת ל-A בהכרזה "המילה אינה שייכת ל-A".
על שפה A נאמר שהיא "כריעה למחצה", אם ורק אם קיים אלגוריתם, שעוצר עבור מספר סופי של צעדים עבור כל מילה השייכת ל-A בהכרזה "המילה שייכת ל-A", אם ורק אם המילה שייכת ל-A (אך אם הוא מקבל מילה שאינה שייכת ל-A, ייתכן שלא יעצור כלל).
כל שפה שהיא כריעה, היא גם כריעה למחצה.
עבור משפחת שפות תחשיב היחסים, משפט צ'רץ' קובע ששפה מסדר ראשון המכילה, בנוסף לקבוע השוויון, קבוע יחס או קבוע פעולה בעל שני מקומות לפחות, אז קבוצת הנוסחאות של השפה שהן אמיתיות לוגיות, אינה כריעה.
