שיחה:שפה פורמלית

מתוך ויקיפדיה, האנציקלופדיה החופשית

[עריכה] הערות

1. לא ברור מדוע לכתוב "MU system" ולקשר לדגלאס הופשטטר אומר משהו למי שלא קרא את "גדל, אשר, באך". זו דוגמה מאוד גרועה, לטעמי, ואנסה לנמק: דוגמה שכתובה בערך הזה צריכה להיות ברת הסברה במסגרת הערך הזה - או לפחות מקשרת לערך שעוסק בה בצורה ישירה, ולא באדם שכתב ספר (עב כרס ולא נגיש לכולם) שבו היא מופיעה כדוגמה.
2. בערך נאמר: "לבסוף, נשאלת השאלה הכללית: בהנתן שפה, האם בכלל ניתן לאפיינה באופן "מועיל"?". המשפט הזה לא ברור כי לא ברור מה הכוונה ב"מועיל" כאן (וזה כל הקטע). יתר על כן, "מועיל" מופיע במרכאות, כאילו כדי לציין שגם בערך עצמו מחפף בנקודה הזו - נראה לא רציני.
3. נחמד שה"ידה ידה ידה" הועף מתת הפרק של דקדוק פורמלי. השאלה היא למה לא נכתב במקום זה שום דבר מועיל. רצוי לעשות יותר מאשר לקשר לערך אחר - לפחות לתת משפט אחד או שניים שמסביר מה הולך כאן. נכון, זה טוב שקורא של ערך ייכנס גם לערכים המקושרים ויקרא גם אותם - אבל לפני שאנחנו שולחים אותו לקרוא ערך גדול ומקיף (וכרגע, לא כזה שעוסק ממש בדקדוקים פורמליים) עדיף שלא נשבור לו את רצף הקריאה ונתייחס לנושא גם בעצמנו.
4. כל החלק של כריעות וכריעות למחצה לא ברור:
   1. "על תת-קבוצה B של שפה A נאמר שהיא "כריעה" אם ורק אם קיים אלגוריתם העוצר כעבור מספר סופי של צעדים עבור כל ביטוי השייך ל-B בהכרזה "הביטוי שייך ל-B", ועוצר כעבור מספר סופי של צעדים עבור כל ביטוי השייך ל-A בהכרזה "הביטוי אינו שייך ל-B"." - מכיוון ש-A היא קבוצה שמכילה את B, נובע מהמשפט שהאלגוריתם אמור לעצור על מילים ששיכות ל-B ולהגיד "הביטוי שייך ל-B" וגם להגיד "הביטוי אינו שייך ל-B". צריך לתקן כאן - אני מניח שיש להוסיף "...עבור כל ביטוי השייך ל-A אך אינו שייך ל-B...".
   2. "על תת-קבוצה B של שפה A נאמר שהיא "כריעה למחצה", אם ורק אם קיים אלגוריתם, שעוצר עבור מספר סופי של צעדים, עבור כל ביטוי השייך ל-A בהכרזה "הביטוי שייך ל-A", אם ורק אם הביטוי שייך ל-A." - זה כבר ממש לא ברור לי. איך B נכנסת לעניין כאן?
   3. לי נראה שעיקר הבעיה בשני המשפטים הוא השימוש ב-A. הסיבה שאיני מתקן אותם בעצמי היא שאני סבור שכדאי להיפטר לגמרי מה-A (או ליתר דיוק, מה-B) ולדבר רק על כריעות של שפות, לא של תת קבוצות של שפות (שהן בעצמן שפות אם איני טועה, אז מה ההבדל?)
5. מה קרה להיררכייה של חומסקי? לא חשובה? גדי אלכסנדרוביץ' 23:40, 27 באוקטובר 2006 (IST)

1. זו דוגמא משעשעת, ולמיטב ידעתי, ידועה. אתה מוזמן לפרט יותר, אם לדעתך יש בזה צורך, או למחוק אותה בכלל. הוספתי אותה על תקן טיזר.
   1. מה ז"א, "למיטב ידיעתי"? מה גורם לביטחון הזה? לדעתי כדאי להסיר את הדוגמה ולתת דוגמאות יותר "סטנדרטיות", עם כל אהבתי (הרבה מאוד) ל-GEB. הדוגמה אולי משעשעת, אבל אין בה טעם רב אם היחידים שיבינו אותה הם אלו שקראו את הספר. גדי אלכסנדרוביץ' 00:18, 28 באוקטובר 2006 (IST)
2. תיאור פורמלי יותר מ-"מועיל" (אם כי לא מקיף דיו, עדיין) מופיע בסעיף "כריעות". נראה לי סביר וקריא-יותר "לחפף", כלשונך, בסעיף הכללי, ולדייק יותר בתת-הסעיף הרלוונטי.
   1. לא צריך הסבר פורמלי. צריך הסבר כלשהו איך מתבטאת ה"מועילות". למשל, האם זה במהירות הזיהוי, או בכך שהזיהוי מובטח. גדי אלכסנדרוביץ' 00:18, 28 באוקטובר 2006 (IST)
3. אני לא יודע מספיק על דקדוק פורמלי בשביל לפרט. כנ"ל לגבי ההירככיה של חומסקי ש-(כנראה) מקומה הראוי הוא בערך על הדקדוק הפורמלי.
4. אכן, הצדק עימך. אתקן. בכלל, לנושא של כריעות מגיעה יותר תשומת לב משנתתי לו ("to whom it may concern". זה כולל אותי).עומר ש. 00:11, 28 באוקטובר 2006 (IST)

[עריכה] בהמשך, בנוגע לשאלת האפיונים

כשעוסקים בדקדוקים יש שני סוגי דקדוק: מה שנקרא Generative Grammar, ש"מייצר" מילים בשפה, ומה שנקרא Analytic Grammars, שנבנים מראש מתוך מחשבה על זיהוי המילים. לכן אולי כדאי לבצע הפרדה שכזו: בצד אחד לשים את כל המנגנונים שמאפשרים ליצור מילים (מבני יצירה, דקדוקים, ביטויים רגולריים ואולי עוד דברים אם מישהו מכיר) ובצד השני את המנגנונים שמשמשים לזיהוי שפות (אוטומטים סופיים, אוטומטי מחסנית ומכונות טיורינג - ועוד, אם מישהו מכיר). זו גם ההזדמנות להתייחס לסיווגים של השפות הפורמליות למחלקות שונות, על פי הכוח של המנגנון שיוצר/מזהה אותן (מה הכוח של מבני יצירה?) גדי אלכסנדרוביץ' 09:07, 28 באוקטובר 2006 (IST)