מבחן מסכם מס' 2
משך המבחן שעתיים.
2.
3. דקדוק חומסקי, אזי מספר המשתנים ב- הוא לפחות:
4.
5.M אס"ד בעל n מצבים. מספר המצבים המינימלי עבור:
6., חסרות הקשר ולא רגולריות.
A: בהכרח ח"ה .
B: בהכרח לא רגולרית.
7.
8.
מספר מחלקות שקילות של L הוא:
9.
1. ו- M רגולרית גורר ש-L רגולרית
2. רגולרית ו--רגולרית גורר רגולרית.
10.
1.L רגולרית גורר רגולרית
2.L לא רגולרית גורר לא רגולרית
11.
1. ח"ה ו- סופית גורר ח"ה.
2. ח"ה ורגולרית גורר ח"ה.
12. M אס"ק בעל n מצבים אם ורק אם
