שפה חופשית הקשר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
|||
שורה 30:
מספר שאלות הקשורות לשפות חופשיות הקשר לא [[כריעות]], בהן:
*שקילות: נתונים שני דקדוקים A ו-B, האם שתי השפות שהם מגדירים שוות, כלומר {<math>L(A)=L(B)</math>?
* זרות: נתונים שני דקדוקים A ו-B, האם שתי השפות שהם מגדירים
*הכלה: נתונים שני דקדוקים A ו-B, האם שפה אחת מוכלת בשנייה, כלומר <math>L(A)\subseteq L(B)</math>?
הערה: כל הבעיות האלה כריעות כשמדובר בשפות רגולריות.
| |||