PDA

צפה בגרסה המלאה : שלה- האם שפה לא רגולרית היא בהכרח חופשית הקשר?



elixvx
15-05-2012, 10:34
כותרת?
ואם לא, זה מה ההבדל בין שפה שהיא לא רגולרית לשפה שהיא חופשית הקשר?
(רגולרית - אס"ד מקבל, חופשית הקשר - אוטמטת מחסנית. כל השאר - טיורינג נכון?)
מישהו יכול להביא לי הגדרות מדויקות לכל סוגי השפות?

תודה.

odp
29-05-2012, 22:52
העמוד הראשון בחוברת הזאת מתאר את המצב די טוב - http://www.kadman.net/modelim.pdf
אז שפה שהיא לא רגולרית, היא לא בהכרח חופשית הקשר, בגלל שיכול להיות שלא קיים אוטומט מחסנית שמקבל אותה, אלא רק מכונת טיורינג.
שפה רגולרית - קיים אוטומט סופי דטרמיניסטי שמקבל אותה.
שפה ח"ה - קיים אוטומט מחסנית שמקבל אותה.
שפה תלויית הקשר - קיים סוג של מכונה שהיא מכונת טיורינג עם כל מיני מגבלות שמקבלת את השפה.
שפה כללית - מתאימה למודל של מכונת טיורינג.

מה שתיארתי עכשיו, ידוע בתור ההיררכיה של חומסקי, רק שבדר"כ מציגים את זה באמצעות מושג שנקרא דקדוק, ושאני די בטוח שלא לומדים אותו בבית הספר.