 |
|
|
|
|
| hw2 | | שתי הטענות בשקף |
hw2.pdf 66224 Bytes
|
| Due date: | 16/4/2012, 10:30 |
|
|
|
|
|
|
|
|
|
|
|
| hw2 | | L(^A)=L(A')L(A) |
hw2(1).pdf 13864 Bytes
|
| Due date: | 16/4/2012, 10:30 |
|
|
|
|
|
|
|
|
|
|
|
| hw 3 | בשקף הראשון- הוכחת הטענה
בשקף השני- להוכיח שאין אוטומט רגיסטרים דטרמיניסטי שמכריע את השפה |
hw3.pdf 86735 Bytes
|
| Due date: | 30/4/2012 |
|
|
|
|
|
|
|
|
|
|
|
| hw4 | האם המודל של אוטומט דו כיווני שקול למודל שבו כל מילה שנופלת מימין מתקבלת?
ניתן להניח שהמודל של אוטומוט דו כיווני דטרמינסטי שקול למודל דו כיווני לא דטרמינסטי |
| Due date: | 28/5/2012 |
|
|
|
|
|
|
|
|
|
|
|
| hw5 | | הוכח: בהינתן שתי שפות חסרות הקשר לא ניתן להכריע אם החיתוך שלהן ריק |
| Due date: | 11/6/2012 |
|
|
|
|
|
|
|
|
|
|
|
| hw6 | :הוכח
בהנתן דקדוק חסר הקשר לא ניתן להכריע האם השפה של הדקדוק שווה לסיגמא סטאר
(לא ניתן להכריע אוניברסליות של דקדוק חסר הקשר)
|
| Due date: | 18/6/2012 |
|
|
|
|
|
|
|
|
|
|
|
| hw7 | הוכח כי בעיית הריקנות לאוטומט 3-פבל חלש חד כיווני לא ניתנת להכרעה
הוכח כי כל שפה שמתקבלת על ידי אוטומט רגיסטרים היא סמי-לינארית |
|
|
|
|
|
|
Technion - Israel Institute of Technology 
