2010 סימסטר א' מועד א'
Maya (guest) 23 Jun 2015 16:42
שאלה 14 בחלק הסגור של 2010 סימסטר א' מועד א': באיזו מחלקה נמצאת שפת הזוגות <M,w> כך של-M יש פחות מ-100 מצבים והיא עוצרת על w.
שאלה 2 בחלק הסגור של 2008 סימסטר א' מועד א': באיזו מחלקה נמצאת שפת המכונות <M> כך של-M יש יותר מ-1000 מצבים או M עוצרת על כל הקלטים.
אם מסתכלים על השפה השניה (של שאלה 2) זה בעצם איחוד של: L1 = כל המכונות שיש להן פחות מ-1000 מצבים וגם עוצרות על כל קלט ו-L2 = כל המכונות שיש להן יותר מ-1000 מצבים. השפה שתיארתי L1 נראית כמו השפה בשאלה 14 (למעט שכאן מדובר בכל קלט ובשאלה 14 זה w ספיציפי).
לפי התשובות השפה משאלה 14 היא ב-RE\R והשפה משאלה 2 היא ב-R. אני לא מבינה ממש מה ההבדל…
