[-]
by - Thursday, 1 January 1970 02:00:00
[-] P
by davel - Monday, 18 January 2010 22:56:46
אינטואיטיבית,
למה כאשר ה"קבוצה הריקה" שייכת ל P
אז לא קיימת מכונת טיורינג שתקבל את השפה LP.
ראיתי כבר את ההוכחה הפורמלית.)

תודה.
[-] Re: P
by gilamor - Tuesday, 19 January 2010 16:15:39

This looks slightly complicated, but...

Assume that the empty language satisfy the property P.
As P is non-trivial, then there exists a language L (in RE) which does not satisfy the property P,
and denote by A the turing machine for which L(A)=L.

till now we have:
1)  EmptyL is in P
2) L(A) is not in P

Assume to the contrary that L_P is in RE, and let M_P be the t.m. that accepts L_P.

Now, given an input x=<M>,<w> we can decide whether M does not accept w :
(contradicting the fact that we cannot decide such a thing)

Consider the following t.m. M_c:

1. M_c gets input y.
2. M_c simulates M over the input w and if M reject w then M_c loops.
3. M_c simulates A over the input y and answer the same.

Note that in case M accepts w, then M_c gets to line 3 and hence L(M_c)=L(A).
otherwise, M_c loops, namely L(M_c)=EmptyL.
All in all, we have that either L(M_c)=L(A) or L(M_c)=EmptyL.

As L(A) is not in P and EmptyL is in P, we can now use M_P:
 
If M_P accepts <M_c> then it must be that L(M_c)=EmptySet, but then we know that M does not accept w (which is impossible to decide).

Re: P
by davel - Wednesday, 20 January 2010 11:48:48
toda.
[-] מועד א' 2004 שאלה 2 סעיף א
by maximkir - Monday, 18 January 2010 23:12:10
ראיתי את הפתרון שמפורסם פה באתר, אני פתרתי בדרך אחרת ואשמח אם תאשרו כי זו דרך נכונה

הראתי שלשפה הנתונה יש אינסוף מחלקות שקילות, התבוננתי במילים  הבאות:
x=a^k   , y= b^k      (k>=0)

לכל 2 מילים שונות מהצורות הללו  המילה הריקה  היא סייפא מפרידה.... מכיוון שיש אינסוף מילים כאלו הרי לשפה הנתונה יש אינסוף מחלקות שקילות ולכן אינה רגולרית.



Re: מועד א' 2004 שאלה 2 סעיף א
by taig - Tuesday, 19 January 2010 11:13:51

No!

Your example shows only 2 equivalence classes - all the words of the first kind are in one class and all the other words in the second class.
Please see your mistake: in order to prove irregularity in this method you have to present an infinite number of words where each of these words is in a separate class so there are infinite number of words : technically - you must give "SEIFA MAFRIDA" to each pair of these words - see the relevant p.s.

[-] F is computable - reduction
by ariels - Tuesday, 19 January 2010 21:37:56
When can we write that it is trivial that F is computable and when can't we, while proofing a reduction?
Can you please give an example for a reduction where it isn't trivial.
Thanks
Re: F is computable - reduction
by taig - Tuesday, 19 January 2010 23:16:43
As long F is actually computable - meaning it always (on all possible inputs) Halts and Accept!  and as long you shortly describe how it computes F(x) then on most (if not all) cases a short description as we saw many times in class will be sufficient.
if you give a function when one might think , on a brief look , that there is a chance it might lead the machine into infinite loop or reject the input than a detailed description will be needed but once again, these situations (if you know what you're doing) are not common at all.
of course, you should be sure that the function can be computed by a turing machine which can't do anything (be reasonable).
[-] איך משתמשים ב ENUMURATE בדיוק
by eitanco - Tuesday, 19 January 2010 22:46:15
אנו יודעים ש ENUMRATE
זוהי מכונה שלא מפסיקה לרוץ

עכשיו אי רוצה למשל ברדוקציה לההשתמש בפלט של אינומרייט
ועבור כל מילה אפשרית לעשות פעולה כלשהי או לרוץ ולבדוק
איך אני עושה את זה ...? אני מניח שיש לי פשוט סרט עם כל המילים או שאני צריך להסביר איך אני מפעיל את המכונה עוזב אותה וחוזר אליה כל כמה זמן
?
האם צריך להסביר שיש סרט אינסופי ושאף פעם לא מפסיקים לרוץ על הסרט כי לא יודעים אם הוא נגמר...?
איך בדיוק משתמשים בזה ברדוקציה בכלל
תודה!!!
[-] Re: איך משתמשים ב ENUMURATE בדיוק
by erantom - Wednesday, 20 January 2010 12:57:11
ראשית, אינומרטור אינו בהכרח לא עוצר. הדרישה היחידה עבורו הוא שכל מילה בשפה תודפס בזמן כלשהו, עבור שפה סופית ייתכן כי פעולת האינומרטות תעצר לאחר הדפסת כל המילים שבשפה.
לגבי השאלה שלך, לא, אינך יכול להניח כי כל המילים נמצאות על הסרט, כיוון שיש אינסוף כאלו.
מה שכן ניתן לעשות זה לסמלץ את פעולת האינומרטור למשך מספר צעדים סופי
ובכל איטרציה נוכל להגדיל את מס' הצעדים הנל.
[-] Re: איך משתמשים ב ENUMURATE בדיוק
by galaf - Wednesday, 20 January 2010 22:22:22
ציטוט מתרגול מספר 11:

אפילו עבור שפה נל"ר סופית, המונה שלה חייב לפעול באופו אינסופי.



סותר..
מה נכון?

[-] Re: איך משתמשים ב ENUMURATE בדיוק
by gilamor - Wednesday, 20 January 2010 22:33:58

זה לא ממש משנה במקרה הזה.
התכונה החשובה של אנומרטור היא שהוא כותב את כל המילים של השפה על סרט-המונה ורק אותן.

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

[-] Re: איך משתמשים ב ENUMURATE בדיוק
by eitanco - Thursday, 21 January 2010 14:03:59
כעקרון אין דרך לדעת שהאינומרטור היגע לסוף..
אז אני לא אדע שכל המילים נכתבו.
תמיד יכולה להיות מילה כלשהי שעדיין לא נכתבה
ואני אמשיך להריץ את האינומרטו על מספר גדול יותר של צעדים שוב ושוב ושוב
בתקוה לקבל עוד מילה
ואני לעלום לא אפסיק
אז זה גם יהיה אין סופי למרות שהשפה עצמה סופית.

או שאני מבולבל?


Re: איך משתמשים ב ENUMURATE בדיוק
by gilamor - Thursday, 21 January 2010 14:41:17

נכון. אין דרך לדעת אם האנומרטור כתב כבר את כל המילים (מה שממילא אפשרי רק אם השפה סופית) או לא.

באופן יותר ספציפי, עבור מילה
W
אם עד שלב מסויים האנומרטור עדיין לא כתב על סרט המונה את המילה
W,
אז אין לדעת אם זה משום שהיא לא בשפה או שהיא כן בשפה ועוד מעט היא תיכתב על הסרט.

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

[-] מועד א 2009
by miripe - Wednesday, 20 January 2010 14:05:38

שאלה 1 סעיף ג :

למה בתוצאת האיחוד לא כוללת את Lacc?

תודה

Re: מועד א 2009
by taig - Wednesday, 20 January 2010 16:35:08

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

אפשר בבקשה להוסיף פתרון למועד ג' 2007
by itaisil - Wednesday, 20 January 2010 16:00:50
תודההה
[-] 2009 מועד ב
by miripe - Wednesday, 20 January 2010 19:58:13

אפשר בבקשה הסבר מפורט לשאלה 1 א במועד ב של 2009?

[-] Re: 2009 מועד ב
by gilamor - Thursday, 21 January 2010 10:07:42

למשל
L1
היא השפה
  L_\SIGMA*
כלומר אינה ב-
RE
וגם לא ב-
CO-RE

עכשיו נסתכל על השפה
 L
שהיא איחוד של
 L_1
עם כל המילים באורך 1 (היחידונים)
ברור ש-
L
 לא ב
 RE 
וגם לא ב-
 .CO-RE

אבל
 *L
היא רגולרית מפני שהיא  למעשה
סיגמא*.

[-] Re: 2009 מועד ב
by alom - Wednesday, 20 January 2010 22:51:19
שלום! אפשר בבקשה לפרט יותר למה
L
אינה ב
RE
וגם לא ב
CO-RE
??

ומדוע צריך לבחור את
L1
להיות השפה הזו דווקא?
תודה!
[-] Re: 2009 מועד ב
by gilamor - Thursday, 21 January 2010 07:55:37

לא חייבים לבחור
-ד-ו-ו-ק-א-
את השפה הזו.
יש עוד דוגמאות

[-] Re: 2009 מועד ב
by alom - Thursday, 21 January 2010 09:45:24
לא ענית לי על השאלה הראשונה ששאלתי...
אשמח לקבל תשובה,
 תודה!
Re: 2009 מועד ב
by gilamor - Thursday, 21 January 2010 10:08:51
סליחה, טעיתי.
הכוונה הייתה ל-
L_\SIGMA*
ולא ל-
L_\emptyset.

L_\emptyset.
היא ב
CO-RE



אם
L
הייתה
נניח ב
RE
אז בגלל שמאד קל לבדוק שמילה אינה יחידון
זה היה אומר שגם
L_\SIGMA*
ב
RE
[-] שאלה לגבי רדוקציה
by evgenim - Wednesday, 20 January 2010 22:16:41
האם בהכרח קיימת רדוקציה משפה למשלימה שלה ?
ואם קיימת רדוקציה משפה למשלימה שלה, האם בהכרח יש רדוקציה הפוכה (מהמשלימה לשפה המקורית) ?

Re: שאלה לגבי רדוקציה
by gilamor - Wednesday, 20 January 2010 22:27:42

אני אענה קודם על השאלה השניה-
אם
A<=B
אז
comp(A)<=comp(B)
ולכן
L<=comp(L)
זה גם
comp(L)<=L


לשאלתך הראשונה, התשובה היא בהחלט לא.
אם
L
ב-
RE\R
אז לא תתכן כזו רדוקציה
משום שבמקרה כזה
comp(L)
אינה ב-
RE

ואז נקבל
L<=comp(L)
שמשמעו גם
comp(L)<=L

אבל זה לא ייתכן אם
comp(L)
אינה ב
RE
ו
L
כן ב
RE

[-] 2009 מועד ג
by vadimlia - Wednesday, 20 January 2010 23:55:51
שאלה 3 (רדוקציה)...
מה הכיוון? כלומר אני מנסה לבנות רדוקציה מ אל סיגמה כוכב לשפה הנתונה
הבעיה היא איך אני יודע האם מ"ט נתונה מקבלת את כל המילים או לא?
כי המ"ט שאני אמור להחזיר ברדוקציה תלויות בתשובה לשאלה זו
[-] Re: 2009 מועד ג
by gilamor - Thursday, 21 January 2010 07:59:57
הרמז הנתון בשאלה הוא רמז טוב, כדאי ללכת לפיו.
נרחיב אותו טיפונת:
אם קובעים את המכונה הראשונה להיות מכונה שמקבלת את השפה הריקה אז הקידוד של השניה לא נמצא בשפה של הראשונה.אם קובעים את המכונה השניה להיות מכונה שמקבלת את סיגמא* אז הקידוד של הראשונה כן נמצא בשפה של השניה.
[-] Re: 2009 מועד ג
by vadimlia - Thursday, 21 January 2010 13:34:29
למען האמת למסקנה הזאת הגעתי עוד לפני שפירסמתי כאן את השאלה,
השאלה היא מה הלאה?..
תודה
[-] Re: 2009 מועד ג
by taig - Thursday, 21 January 2010 14:10:10
נסה לחשוב על רדוקציה לשפה המשלימה של שפת העצירה כאשר אחת המכונות מקבלת את כל המילים והשנייה מריצה
M
על
W
ואם היא עוצרת - המכונה מקבלת

אפשרות נוספת - רדוקציה ל - Ld

שים לב ששימוש בשפות אלו דורש שתי רדוקציות לצורך פתרון התרגיל - אחת לשפה ואחת למשלימתה
[-] Re: 2009 מועד ג
by amirja - Saturday, 23 January 2010 17:09:25
למה צריך 2 רדוקציות ?
אני מראה:
Ld < L
אז
L not belongs to RE

וזה משליך על
_      _
Ld < L
אז
_
L not belongs to CO_RE

לא ככה?
Re: 2009 מועד ג
by abuaffas - Saturday, 23 January 2010 18:03:37
So, how could you conclude that L does not belong to CO_RE?
Also, see this.
[-] Lacc* ועוד
by goltshiy - Thursday, 21 January 2010 00:46:29

שלום, אם תוכלו להסביר
מה זה Lacc*  או Lhalt*?

כמו כן , מס' מחלקות השקילות של שפה הן בדיוק כאורך של המילה הכי ארוכה ועוד 2?
(מס' סייפות מפרידות + מחלקת זבל)

אם תוכלו לרשום דוג' לרדוקציות של שאלה 1 ה' במועד ג' 2009

תודה רבה,

Re: Lacc* ועוד
by gilamor - Thursday, 21 January 2010 08:06:21
א-י-ן  כ-ז-ה  ד-ב-ר  מ-ח-ל-ק-ת  ז-ב-ל.

יש שפות שבהן אף מילה איננה "אבודה" ואפשר להשלים אותה למיה בשפה. בשפות כאלה גם אין "מילה הכי ארוכה".
מילה ארוכה ביותר קיימת רק בשפות סופיות ואז מספר מחלקות השקילות הוא ל-פ-ח-ו-ת כאורכה ועוד 2 אבל לא בגלל "מספר סיפות מפרידות" כי יש אינסוף סיפות.
אלא בגלל שכל רישא של המילה הארוכה ביותר חייבת להיות במחלקה אחרת משאר הרישות
וייתכנו רישות שונות למילים שונות שנמצאות בשפה.
[-] Re: Lacc* ועוד
by gilamor - Thursday, 21 January 2010 08:08:00

L*
זו שפת כל השרשורים של מילים מ
L
אז כנראה ש
Lacc* 
היא שפת  שרשורי מילים
מ
Lacc.

איפה ראית כזה דבר?

[-] Re: Lacc* ועוד
by miripe - Thursday, 21 January 2010 11:07:56
אוקיי תודה

תוכלי לרשום דוג' לרדוקציות של שאלה 1 ה' במועד ג' 2009

 ובנוסף למה בשפות סופיות מספר מחלקות השקילות הוא ל-פ-ח-ו-ת כאורכה ועוד 2

למה דווקא 2 ? במבחנים ראיתי שזה ועוד 1..

תודהה רבה :)
Re: Lacc* ועוד
by auto101 - Thursday, 21 January 2010 11:43:16

אם המילה הכי
ארוכה היא באורך
K
אז כל רישא שלה היא במחלקה נפרדת. יש לה
K+1
רישות.
בנוסף,
מילים שאינן רישות שלה נמצאות במחלקה נוספת.

אין סתירה, אם המספר הוא לפחות
X+2
אז הוא גם לפחות
X+1

[-] 2007 שאלה קצרה-מועד א' שאלה 1 סעיף ד
by rotemams - Thursday, 21 January 2010 00:54:14

האם נכון או לא נכון?
אפשר לקבל קווים כללים לפתרון ?
רייס? דוגמא נגדית?

תודה..

[-] Re: 2007 שאלה קצרה-מועד א' שאלה 1 סעיף ד
by shayas - Thursday, 21 January 2010 07:57:43
ממה שאני הגעתי התשובה היא כן
אפשר להוכיח באמצעות רייס שהשפה לא ב
R
ואפשר להראות בנייה של מ"ט
M1
  שתקבל את השפה  ואז השפה ב
RE
 ניתן ל
M1
 קלט היא תקבל אותו אם הקלט הוא הקידוד ידוע של המכונה
MA
שמכריעה את שפה
A
או במקרה השני שהקלט הוא קידוד של מכונה
<M>
 ששפתה
L(M)
 לא מוכלת ב-
A
<=
אז קיימת לפחות מילה אחת בשפה
L(M)
שלא שייכת ל
A
לכן נסמלץ את המכונה
U
לפי הסדר על המכונות
MA  .1
 M   .2
עם המילים בסדר לקסיקוגרפי מאורך קטן או שווה מ
T

ונקבל רק אם המילה
נדחתה ב
MA
אבל התקבלה ב
M
אם קיימת מילה מהאורך הכי קטן ששיכת ל
L(M)
 שמתקבלת ב
K
צעדים אז אנחנו נגיע ונקבל אותה ב
T=K

בכל פעם  נגדיל את
T
באחד
עד שנמצא את המילה הזאת

זהו ,נראה לי רק נשאר להוכיח את זה ואני מקווה שיש פיתרון אחר יותר קצר ומיידי ,כי זה דורש פה הוכחה וארוכה ובכל מקרה אם אתה רוצה לקבל תשובה כמה שיותר מהר ואפילו מסטודנטים בלי קשר למתרגלים אז עדיף לפעמים להדביק גם את השאלה כדי שמי שרואה את זה יוכל לתת לך תשובה במקום
Re: 2007 שאלה קצרה-מועד א' שאלה 1 סעיף ד
by rotemams - Thursday, 21 January 2010 20:46:13

תודה..

[-] הקשר שלא קיים שבין מ"ט לשפה ב-CO-RE
by shayas - Thursday, 21 January 2010 08:52:12
שאלה 1:
האם המשפטים\דוגמאות הבאות נכונות:
 א. ניתן לומר שלעולם לא קיימת מ"ט
בין אם דטרמיניסטית או א"ד (למדנו בכיתה שלכל מ"ט א"ד יש מ"ט דטר' שקולה)לשפה שנמצא ב
 CO-RE
ולא נמצאת ב
R

לדוגמא :
ב.
לא קיימת מ"ט לשפות ב

Ld-

comp(LACC)-

השפות הללו נלמדו בכיתה ושייכות
ל
CO-RE -R

ג.
וגם אין מ"ט לשפות שנלמדו בכיתה
  Lsigma*-
-
שנלמדו בכיתה ושאינן שייכות לא ל -
RE
ולא ל
CO-RE


שאלה 2:

במידה והתשובה היא כן,אז בשאלה 2ב' מהמבחן ב-2009 מועד א'
{< M1 >,< M2 >: L(M1 )∩L(M2 )=φ}היכן נמצאת
משתמשים בשפה
Lφ {< M >: L(M)=φ}
ועושים ממנה רדוקציה לשפה בשאלה
אבל למדנו ש

אינה נמצאת ב
CO-RE
כלל
 
אז מה פתאום שהשפה בשאלה גם אם הוכחנו את נכונות הרדוקציה שתהיה ב

?CO-RE

ולא ברור לי כל כך מהתשובה מה הקשר בין המ"ט הא"ד בשאלה והאם קשורה לשפה בשאלה או לרדוקציה שהם לא הוכיחו?

שאלה 3:
RE
מתייחס לסיגמא ככוכב
אבל סיגמא שלנו יכול להשתנות,אז האם זה אומר שיש לנו הרבה
"מרחבים " כאלו של
RE
לכל סיגמא שונה
איפה נכנס הנושא של הקידוד לתוך הסיגמא
אנחנו קודדנו בכיתה מכונות ומילים עם
I,C
וברור שאפשר לקודד עם שני תווים אחרים,האם זה אומר שיש דרישה שסיגמא בגודל 2 תווים לפחות?
Re: הקשר שלא קיים שבין מ"ט לשפה ב-CO-RE
by gilamor - Thursday, 21 January 2010 10:18:28

1+2

ראשית,
L_\emptyset
היא ב
CO-RE
מ"ט שמקבלת את השפה המשלימה תקבל כקלט
X
ואם הוא קידוד של מ"ט
<M>
אז היא פשוט תעבור במקביל, תוך שימוש ב
U^T
על כל הקלטים האפשריים ואם היא תמצא אחד ש-
M
מקבלת, היא תקבל את
<M>



1)
אם שפה
L
היא ב-
co-RE
אז משמעות הדבר היא ש-
compL
ב-
RE

עכשיו, אם הייתה מ"ט שמקבלת את
L
אז יכולנו להריץ במקביל את המכונות של
L, compL
וכך להכריע את
L
.
אבל זה לא ייתכן, כי יודעים ש
L
איננה ב
R.

כלומר- אין מ"ט שמקבלת שפה שנמצאת ב
co-RE\R

לשפות שאינן ב
RE
כמו למשל
L_emptyset
בוודאי שאין מ"ט שמקבלת אותן. זוהי המשמעות של "לא להיות ב
RE".

Re: הקשר שלא קיים שבין מ"ט לשפה ב-CO-RE
by gilamor - Thursday, 21 January 2010 10:25:14

3)

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

אבל המסקנות לגבי קושי של חישוב אינן תלויות בא"ב.
לכל א"ב אפשרי, יש שפות ש"מקבילות" לכל השפות המוכרות לנו כמו
Ld, Lacc, L_\emptyset, L_\SIGMA*, ...
אפשר להסתכל על קידודי המכונות כעל מספרים בבסיס 2
ואז להסתכל על השפה של המספרים האלה בבסיס אחר כלשהו,
עם אות אחת או עם כל מספר סופי אחר של אותיות

אם תסתכל על הסעיף האחרון בשאלה האחרונה בתרגיל 5, זו בדיוק המסקנה שמתוארת שם...



(הערה למי שמטרידים אותו ה"אפסים המובילים" -
אפשר להזסתכל על המספרים שמתאימים לקידודים כאשר מוסיפים תמיד בתחילת הקידוד את האות שהחלטנו שהיא "1").



[-] שעות קבלה של אריאל
by malkov - Thursday, 21 January 2010 12:48:45

תוכלו בבקשה להגיד
איכן המשרד של אריאל
כי הוא לא מופיעה ב
course info

תודה

Re: שעות קבלה של אריאל
by taig - Thursday, 21 January 2010 13:59:11
37/-110
[-] רדוקציות
by hilaas - Thursday, 21 January 2010 13:34:34

יש שאלות בהן צריך לבדוק האם שפה מסויימת שייכת למשל ל-RE ,
ורק אז להוכיח ברדוקציה.
איך בודקים? יש איזושהי אינטואיציה לכך?

Re: רדוקציות
by taig - Thursday, 21 January 2010 14:05:22

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

[-] שאלה ברדוקציה
by niram - Thursday, 21 January 2010 13:55:41
does L1<=L2<=L3 implies that L1<=L3?
למשל על ידי פונקצית ההרכבה אולי?
השאלה אם זה באופן מידי או שצריך לנמק שם משהו?
[-] Re: שאלה ברדוקציה
by gilamor - Thursday, 21 January 2010 14:45:00
יחס הרדוקציה הוא אכן טרנזיטיבי.

וכמו שציינת,
אם
f
היא פונקצית רדוקציה
A<=B
ו-
g
היא פונקצית רדוקציה
B<=C
אז ההרכבה של
g
על
f
היא פונקצית רדוקציה
A<=C.
[-] Re: שאלה ברדוקציה
by niram - Thursday, 21 January 2010 15:31:23

עוד שאלה:
האם
Lacc
מוכלת בתוך
Lhalt
?
זה הגיוני אבל אף פעם לא אמרנו את זה.

Re: שאלה ברדוקציה
by taig - Thursday, 21 January 2010 17:22:29
זו עובדה נכונה אך לא מעניינת במיוחד לכן לא דיברנו על זה אף פעם , כן מעניין ששתי השפות "קשות" במידה שווה
[-] Lacc עם גג רק על acc ולא על הכל
by wassemic - Thursday, 21 January 2010 15:25:42
באחד המבחנים מופיע שימוש בשפה Lacc עם גג רק על acc ולא על כל השפה...
השפה מוגדרת כ: {<M>,<w> : w not belongs to L(M)}
לא זכור לי שלמדנו את השפה הזאת...
למדנו רק לגבי המשלימה ל Lacc שהיא לא בדיוק מה שיש כאן...

השימוש בה עוזר לפתור שאלה ממש בקלות.
בנוסף מניחים שהיא לא ב RE בדומה למשלימה של Lacc

 האם אפשר להשתמש בשפה זו?
תודה.
Re: Lacc עם גג רק על acc ולא על הכל
by taig - Thursday, 21 January 2010 17:26:19
די מבובלבל הדברים שלך - נסו לכתוב באנגלית
בכל אופן - ניתן להשתמש רק בשפות ששייכותם למחלקה מסוימת הוכחה בתרגול/כיתה , כל שפה אחרת - יש להוכיח תחילה ואז ניתן להשתמש בה במבחן.

ניתן לצפות בראש העמוד בעמוד הראשון של הבחינה בו מפורטות הוראות אלו
בכל מקרה , השפה כאן דומה מאוד למשלימה של
Lacc
סביר שניתן לבצע רדוקציות שהצלחת לעשות ממנה גם עבור המשלימה של
Lacc
[-] עצירה של מכונת טיורינג.
by gabaev - Thursday, 21 January 2010 15:51:04

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

דבר שני,
אם מכונה טויורינג "נתקעת" (כלומר, לא יכולה להמשיך את הריצה) האם ניתן לומר שהיא עוצרת, והאם ניתן לומר שהיא דוחה?

Re: עצירה של מכונת טיורינג.
by taig - Thursday, 21 January 2010 17:35:00
שים לב ששפה של מכונה היא אוסף כל המילים שהיא "מקבלת" - מה קורה לשאר המילים זה לא חלק מההגדרה - כלומר המכונה יכולה לדחות אותם , לא לעצור עליהם או (במקרה הא"ד) להיתקע עליהם

על מנת לדחות מילה מ"ט חייבת להיכנס למצב דוחה ובהיכנסה למצב דוחה היא עוצרת בהגדרה
תעבור על ההגדרות בתחילת תרגול 10 ואחר כך על ההגדרות בתחילת תרגול 11 - בכל מוסבר שם בפירוט
[-] מספר שאלות לקראת המבחן
by evgenim - Thursday, 21 January 2010 16:09:18
האם
 L-halt
מקבלת מכונה ומילה כך שהמכונה נתקעת על המילה?

האם ניתן להגיד ש
L-acc
מוכלת ב
L-halt?

האם כל השפות חסרות ההקשר שייכות ל
R?
[-] Re: מספר שאלות לקראת המבחן
by taig - Thursday, 21 January 2010 17:21:17

1. לא נתקעת על המילה - עוצרת על המילה
2.כן
.3כן - זה בסיסי מאוד, נסה לצייר את יחסי ההכלה בין על משפחות השפות שלמדנו - חשוב מאוד להכיר אותם ערב הבחינה

[-] Re: מספר שאלות לקראת המבחן
by niram - Thursday, 21 January 2010 19:56:16
רן לא ברור מה רשמת לו לגבי השאלה הראשונה שלו
Lhalt
לא אמורה לקבל מכונה ומילה כך שהמכונה נתקעת על המילה?
נכון או לא?
[-] Re: מספר שאלות לקראת המבחן
by gilamor - Thursday, 21 January 2010 18:14:32

Lhalt

זו שפה של קידודי מכונה ומילה כך שהמכונה עוצרת על המילה.

[-] Re: מספר שאלות לקראת המבחן
by evgenim - Thursday, 21 January 2010 18:37:52
זו לא הייתה השאלה. השאלה היא האם מכונה שנתקעה על מילה נחשבת ככזו שעצרה עליה?
בהרצאה נאמר שכן, ובתרגול נאמר שלא. לכן אנחנו שואלים.
Re: מספר שאלות לקראת המבחן
by auto101 - Thursday, 21 January 2010 20:16:28

מכיוון שאפשר לוודא שמכונה
M
נתקעת על מילה
W
אז אפשר לומר שכאשר מכונה נתקעה היא עצרה.

[-] תכונה של שפה
by sheinart - Thursday, 21 January 2010 17:04:14
איך אני יכול להגדיר תכונה של
L = {<M> : L(M) ={} }
?
תודה
Re: תכונה של שפה
by taig - Thursday, 21 January 2010 17:28:57
השאלה לא לגמרי ברורה , נא לחדד.
השפה שתוארה כאן היא
Lp
עבור התכונה
P- השפה הריקה
כלומר כל השפות ב
RE 
שלא מכילות אף מילה.
[-] רדוקציות למיניהן
by evgenim - Thursday, 21 January 2010 18:44:30
האם ניתן לעשות רדוקציה בין כל שפה ב
RE
לבין כל שפה אחרת ב
RE?

האם ניתן לעשות רדוקציה בין כל שפה ב
R
לבין כל שפה ב
RE?

האם ניתן לעשות רדוקציה בין כל שפה ב
RE
לבין כל שפה שאיננה ב
RE?

תודה!
[-] Re: רדוקציות למיניהן
by auto101 - Thursday, 21 January 2010 20:21:50

(*)
אין רדוקציה בין כל שתי שפות מ
RE
.
הרי כל שפה מ
R
היא ב-
RE
ולא תתכן רדוקציה משפה ב
RE\R
לשפה ב
R

(*)
יש רדוקציה מכל שפה ב-
R
לכל שפה ב
RE
חוץ מהשפה הריקה או סיגמא*
הרדוקציה פשוט בודקת אם
X
מהשפה או מהמשלימה ומחזירה
משהו קבוע בכל אחד משני המקרים.


(*)
לא. לא תתכן רדוקציה משפה ב
RE\R
למשלימה שלה (והרי המשלימה אינה ב
RE)

Re: רדוקציות למיניהן
by evgenim - Thursday, 21 January 2010 21:03:01
אוקיי, נכון. ננסה לדייק יותר:
האם ניתן לעשות רדוקציה מכל שפה ב
RE
לכל שפה ב
RE\R
?

למה שלא תהיה רדוקציה מסיגמא* או מהשפה הריקה לשפות אחרות ב
RE?


[-] מועד א שאלה 2 ב
by dannysi - Thursday, 21 January 2010 19:53:37
פתרו את זה בצורה שאני לא בטוח נכונה
האם ניתן להגיד כפי שכתבו בפתרון
"בוחרת באופן א"ד מחרוזת
W
"
??
אחרי הכל ישנם אין סוף אפשרויות ל
W
והאוטומט הא"ד בחיים לא יעצור

Re: מועד א שאלה 2 ב
by auto101 - Thursday, 21 January 2010 20:23:21
איזו שנה??

אין בעיה לבחור מילה באופן א"ד. בוחרים מילה אחת, סופית, וזהו. לא עוברים על כל המילים האפשריות.
Re: מועד א שאלה 2 ב
by shayas - Thursday, 21 January 2010 20:58:08
,יכול להיות שזה לא מדויק אבל ממה שאני הבנתי
ממה שגילה אמרה פה הדגש על
מ"ט א"ד
עפ"י הגדרה -מקבלת מילה אם קיים! מסלול אחד  לפחות מקבל למילה

ממה שאני הבנתי
בשאלה מהמבחן אם לא תנחש מילה ותריץ מילים בסדר קבוע אז יכול לקרות שהמ"ט
M1
או
M2
בפרט שהן יכולות להיות דטרמיניסטיות
לא יעצרו על המילה ופשוט לא ימשיכו הלאה לבדיקה של המילה הבאה
וזו יכולה להיות בעיה אם קיימת מילה שמתקבלת ע"י
שתי המכונות
M1
ו-
M2
כי אתה לא תגיע למילה הזאת אף פעם !
ברגע שקיים ניחש של המילה והמכונה היא א"ד ,אז לפי המשפט אם קיימת מילה ששיכת לשפות
M1
ו-
M2
קיים מסלול
מקבל בו ננחש את המילה הזאת מיידית ונריץ אותה והיא תתקבל בשני המכונות,אם המכונה הייתה סתם א"ד בלי ניחוש אז עדיין לא היה קיים מסלול מקבל בהכרח כי היא תמיד מתחילה באותה מילה
ויכולה הייתה להמשיך לבדוק עד אינסוף את אותה מילה

בכללי השאלות הן:
אם אנחנו רוצים שהמכונה תעצור על מילה שהיא מקבלת ויכולות להיות מילים אחרות שהמכונה רצה עליהן אינסוף
אז למה שלא נתקע על מילה כזו בלולאה?ולמה שנגיע למילה שמתקבלת בכלל?ואיך הניחוש פותר את הבעיה?


ראשית הסריקה במ"ט א"ד היא לרוחב לכן אם קיימת מילה שמתקבלת בשפה אז קיים לה מסלול מקבל ולכן אנחנו נגיע אליו ואל המילה ונקבל אותה
אז איך הניחוש פותר את הבעיה?
ברגע שאנחנו מבצעים ניחוש אנחנו כביכול מוסיפים  "למסלולים " המ"ט הא"ד
את כל האפשרויות כבר בתחילת הפעולה של המכונה,ככה שאם קיימת מילה בשפה של המ"ט הא"ד קיים מקרה שננחש אותה מיידית בתחילת הפעולה של המ"ט ואז גם נקבל כי המכונה מקבלת אותה
אם לא ננחש מילה,אז זה אומר שקיים סדר מסויים בבחירת המילים ואז המכונה יכולה להתחיל עם מילה שהיא לא עוצרת עליה והיא פשוט לא תנחש את המילה הבאה כי היא בודקת את כל המסלולים האפשריים על  אותה המילה שרצה לאינסוף וגם אם היא עושה את זה לרוחב היא לא תסיים אף פעם
2006 מועד ב
by tamirha - Thursday, 21 January 2010 20:33:30
שלום
קצת נתקענו על שאלות
1:
ד
ה
יש מצב לקבל עזרה איתן ?
[-] Lacc < Ld
by babamura - Thursday, 21 January 2010 20:48:24

 אפשר בבקשה עזרה ברדוקציה
Lacc < Ld
כלומר מ
Lacc
ל
 Ld
תודה.

Re: Lacc < Ld
by halpertc - Thursday, 21 January 2010 21:00:28
לדעתי זה טעות. כי אם הייתה קיימת כזאת רדוקציה אז היה מתקבל שהמשלים של
Ld
לא ב-RE
וראינו בשיעור ש-Ld
ב-Co-RE
[-] ?למה צריך לדעת את ההוכחה לסגירות רגולריות בהומומורפיזם
by shayas - Thursday, 21 January 2010 21:06:15
והאם גם שפות ח"ה ו\או שפות ב
RE
סגורות תחת הומומורפיזם?
והאם אפשר להניח של מה שסגור תחת הומומורפיזם סגור תחת איזומורפיזם כי זו תת מקרה של הומומורפיזם?
Re: ?למה צריך לדעת את ההוכחה לסגירות רגולריות בהומומורפיזם
by taig - Thursday, 21 January 2010 22:26:10

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

[-] 2007 מועד א
by miripe - Thursday, 21 January 2010 21:14:05

שלום
מכיוון שאין פתרונות למבחנים 2007 רציתי להיות בטוחה שנתשובה שלי נכונה :

בשאלה 3 ב' היה צורך להראות רדוקציה מהשפה
Lacc משלים
 לשפה L
 השפה הזו היא כל המכונות שהשפה שלהם לא ריקה וגם כל המילים בהם ארוכות או שוות ל100.

הרדוקציה שלי היא כזו :
כאשר הקידוד הוא חוקי אז f(x)=M1
וכאשר הקידד לא חוקי f(x)=M2

כך ש M1
זה מכונה שהשפה היחידה שהיא מקבלת היא a^100

וM2
מכונה שמקבלת y
בודקת אם האורך של y
גדול שווה 100
אם כן - מקבלת
אחרת - מתעלמת ומפעילה את M על W


ועוד שאלה קטנה
באותו מבחן סעיף 1 ד
האם קיימת שפה כזו ?
קצת מכשיל אבל נראה לי שהשפה היא הקבוצה הריקה
כי אז נקבל ש La
זו השפה של המכונות שהשפה שלהם היא לא ריקה וכבר ראינו שהיא ב
 RE ולא ב R
נכון?

תודה רבה רבה
ושבת שלום
!!

Re: 2007 מועד א
by taig - Thursday, 21 January 2010 22:46:50
הרדוקציה נראית בסדר , על אף שלא נכנסתי לעומק ,, העקרונות דומים לרדוקציה שפתרנו בתרגול 13 , שימי לב רק שהחלפת בתפקידים בין המכונות:  כשהקידוד לא חוקי את רוצה את המכונה הראשונה - הקבועה וכשהקידוד חוקי את רוצה את המכונה תלוית הקלט

לגבי הסעיף השני - נכון
[-] מועד 2008 ב' שאלה 1.ג
by ashrov - Friday, 22 January 2010 00:07:25
למה ההפרש הוא הקבוצה הריקה?
Re: מועד 2008 ב' שאלה 1.ג
by gilamor - Friday, 22 January 2010 13:52:46
כי
L1
היא סיגמא*
[-] מועד ג' 2009, שאלה 2
by evgenim - Friday, 22 January 2010 01:01:44
ע"פ התשובה לשאלה, למיטב הבנתי המכונה הבאה לא תתקבל:
לכל אות שנמצאת מתחת לראש קורא/כותב ולמצב נוכחי
q1,
המכונה תזיז את הראש שמאלה, לא תשנה את האות שהייתה כתובה, ותעבור למצב
q2.
לכל אות שנמצאת מתחת לראש קורא/כותב ולמצב נוכחי
q2,
המכונה תזיז את הראש שמאלה, לא תשנה את האות שהייתה כתובה, ותעבור למצב
q1.

לכל קלט שהמכונה תקבל, היא תכנס ללולאה אינסופית ולא תעשה אף צעד ימינה.

המכונה אמורה להיות שייכת לשפה המתוארת בשאלה, אולם היא לא מתקבלת במכונה שתוארה בתשובה.
תוכלו להסביר?
Re: מועד ג' 2009, שאלה 2
by gilamor - Friday, 22 January 2010 14:05:13
נראה לי שאתה צודק. יפה.

תיקון אפשרי של המכונה שמתוארת בתשובה:
אם
M
לא מקבלת או דוחה במשך
K
צעדים אז:
אם יש קונפיגורציה שחוזרת על עצמה במהלך ריצת
M
על
W
והיתה לפחות הזזה אחת ימינה בין שתי הקונפיגורציות הזהות, דחה.
אחרת קבל.

נראה לי שזה יסגור את הפינה שמצאת.
[-] מבחן 2007 מועד א שאלה 3 ב
by galaf - Friday, 22 January 2010 02:18:42
אני חושבת שיש לי בעיה בהבנת הרדוקציה:

זו הרדוקציה שחשבתי עליה, תגידו לי מה לא בסדר בה.. (אלא אם כן היא בסדר)  :

נראה שהשפה Lacc משלים ניתנת לרדוקציה לשפה L שבשאלה:

f(x) = { if x is in the form <M><w> then return <M'>
if x is NOT in the form <M><w> then return <M-empty> }

L(M-empty) = הקבוצה הריקה

L(M') = { if w belongs to L(M) then return {a^200}
if w does NOT belong to L(M) then return L(M-empty)  }

<!-- @page { margin: 2cm } P { margin-bottom: 0.21cm } --> ואז מתקיימת הרדוקציה..

בכל הרדוקציות האחרות שראיתי על השאלה הזו, ראיתי שהגדירו את המכונה
M'
תוך התייחסות לריצת
M
על
w
ולא הבנתי למה חייבים להשתמש בזה..

תודה רבה
Re: מבחן 2007 מועד א שאלה 3 ב
by gilamor - Friday, 22 January 2010 14:09:19
ראשית, צריך לעשות רדוקציה אל
L
ולא
מ
L

M'
לא יכולה לבדוק אם
W
שייכת או לא שייכת ל
L(M)
כי
L(M)
לא בהכרח ניתנת להכרעה.

אי אפשר
[-] Reduction and Co-RE
by omergold - Friday, 22 January 2010 04:13:05
האם נכון לומר שאם קיימת רדוקציה
L1<L2
ואנו יודעים ש
L1 is not in Co-RE, then L2 is not in Co-RE ?

and also if L2 belongs to Co-RE means that L1 belongs to Co-RE?

Re: Reduction and Co-RE
by gilamor - Friday, 22 January 2010 14:17:16
L1<=L2 implies that comp(L1)<=comp(L2).

Now, if L1 is not in co-RE, then comp(L1) is not in RE.
but then, as comp(L1)<=comp(L2), we get that comp(L2) is not in RE, thus comp(comp(L2))=L2 is not in co-RE.

same way, if L2 is in co-RE the comp(L2) is in RE and so does comp(L1), thus L1 is in co-RE.
[-] RE \ R
by amirja - Friday, 22 January 2010 11:02:38

האם 
RE \ R
סגורה תחת איחוד וחיתוך?

בהתאמה
CO_RE \ R

[-] Re: RE \ R
by yanivpar - Friday, 22 January 2010 12:57:34
No , if you take (Lacc U Lacc Complement) = sigma * , which belong to R.
[-] Re: RE \ R
by gilamor - Friday, 22 January 2010 14:32:50

אתה צודק שהתשובה היא "לא" אבל הדוגמא אינה נכונה כי המשלימה של
Lacc
אינה
ב-
RE\R.

[-] Re: RE \ R
by eitanco - Friday, 22 January 2010 15:58:45
אז מה התשובה באמת?
אפשר להגיד שאם
L1,L2 שייכות ל
RE\R
אז שחיתוך ואיחוד בניהם שייך ל
RE\R
או לא?
[-] Re: RE \ R
by egozie - Friday, 22 January 2010 17:59:32
שמע, דבר ראשון, תשנן את הטבלא הזו אם אתה מסתבך
http://en.wikipedia.org/wiki/Formal_language#Operations_on_languages

דבר שני,
אתה לא יכול להגיד שהקבוצה,
RE\R
סגורה תחת איחוד או חיתוך, זה ברור.
אם דוגמא זה מה שאתה מחפש, קבל:
חיתוך:

L1={<M> | L(M) = הקבוצה הריקה}  => coRE את ההוכחה למשלימה (פחות או יותר) יש בתרגול 11
L2={<M> | L(M) = {a} השפה שהיא} => coRE ההוכחה דומה מאוד לזו של השפה הקודמת

אתה כבר יכול לראות שהחיתוך נותן קבוצה ריקה, שהיא שפה רגולרית בכלל.

איחוד:

L1={<M> | L(M) != הקבוצה הריקה}  => RE את ההוכחה יש בתרגול 11
L2={<M> | L(M) != {a} השפה שהיא} U {w | הוא מהצורה של שפת מכונה w} => RE ההוכחה דומה לקודמת

וכמובן האיחוד הוא סיגמא כוכב.

Re: RE \ R
by gilamor - Sunday, 24 January 2010 10:16:06

דוגמא טיפה "טריקית"

L1- שפת כל המכונות שהשפה שלהן לא ריקה ויש להן מספר זוגי של מצבים איחוד עם כל המכונות שיש להן מספר אי-זוגי של מצבים.

L2- שפת כל המכונות שהשפה שלהן לא ריקה ויש להן מספר אי-זוגי של מצבים איחוד עם כל המכונות שיש להן מספר זוגי של מצבים.

(תרגיל- רדוקציה פשוטה מראה שהשפות הנ"ל ב
RE\R)

האיחוד של שתי השפות הוא כל המכונות, שהיא שפה ב
R

[-] מועד ג' 2009 שאלה 3
by eladtam - Friday, 22 January 2010 11:16:41
לא ממש הצלחנו לבנות את הרדוקציה שם...ניסינו מL
וגם מLd
וזה לא עבד..

[-] Re: מועד ג' 2009 שאלה 3
by gilamor - Friday, 22 January 2010 15:32:15

נראה לי שהשאלה הזו יותר מורכבת מאשר רדוקציה משפה מוכרת כלשהי ואולי לכן היא שווה 25 נקודות.

אני אנסה לכוון אתכם לפתרון שיש לי בראש, אם כי אני חוששת שאולי הוא יותר מורכב ממה ש"המשורר התכוון אליו":

ראשית, נגדיר איזושהי מכונה קבועה כלשהי שמקבלת תמיד ונקרא לה
M_all
עכשיו, נתייחס לקבוע
<M_all>
ונגדיר את שפת כל המכונות שלא מקבלות את
<M_all>
נקרא לשפה הזו
L_nMall
אפשר להראות שהשפה הזו אינה ב
RE
(לשמחתנו אין צורך ברדוקציה, אפשר להסתמך על משפט רייס)

ולבסוף, כדי להראות שהשפה שבשאלה אינה ב
RE
יש להראות רדוקציה אליה מ
L_nMall


[-] Re: מועד ג' 2009 שאלה 3
by barashd - Saturday, 23 January 2010 00:00:45
יש לי הצעה לפתרון, מקווה שזה נכון

L_not_accept-
הכוונה היא לשפה המשלימה את
L_accept
L_not_accept וידוע ש
RE-  איננה ב
 
רדוקציה:
L_not_accept <=  L

על מנת להקל על הקריאה אני אדלג על בדיקת צורת הקלט בפונקציה.
פונקציית הרדוקציה:
F(X)
If X=<M><w>
F(X)=<M1>,<M2>

המכונה הראשונה זוהי מכונה שמריצה את
<M><w>
 ועונה כמוה
(מתעלמת מהקלט)
המכונה השנייה היא  מכונה שמקבלת את הקידוד של המכונה הראשונה.
____________________________________________________________
עכשיו עבור המשלימה של
L
נסמן אותה
comp(L)
תאור במלים:
המשלימה שלה היא השפה שמכילה
}
1. כל המלים שאינן זוג קידודי מכונה
2. זוג קידודים כך ש
הקידוד של השנייה שייך לשפה של הראשונה
או
הקידוד של הראשונה, לא שייך לקידוד של השנייה
}

הרדוקציה עבורה היא בדיוק אותה רדוקציה ממקודם,
אבל צריך להחליף בין המכונה הראשונה והשנייה.
 
רדוקציה:
L_not_accept <= comp( L)

פונקציית הרדוקציה:
F(X)
If X=<M><w>
F(X)=<M1>,<M2>

המכונה הראשונה היא  מכונה שלא מקבלת את הקידוד של המכונה השנייה.
המכונה השנייה היא  מכונה שמריצה את
<M><w>
ועונה כמוה.
(מתעלמת מהקלט

Re: מועד ג' 2009 שאלה 3
by abuaffas - Saturday, 23 January 2010 01:57:39

A) comp(Lacc)<=L
if x=<M>,<w>  then F(x)=<Mw>,<MSigma*>

B) Lacc<=L                   ( implies comp(Lacc)<=comp(L))
if x=<M>,<w>  then F(x)=<Mempty>,<Mw>

[-] רדוקציות בתוך מחלקות
by rotemams - Friday, 22 January 2010 13:56:08

ייתכן שהתשובות אמורות להיות ברורות אבל לא איכפת לי: 

האם לכל שתי שפות ב
R
חוץ מהקבוצה הריקה וסיגמא כוכב ניתן לעשות רדוקציה אחת לשניה?

האם לכל שתי שפות ב
RE/R
 ניתן לעשות רדוקציה אחת לשניה?

האם לכל שתי שפות ב
CO-RE/R
 ניתן לעשות רדוקציה אחת לשניה?

Re: רדוקציות בתוך מחלקות
by gilamor - Wednesday, 10 February 2010 17:45:22
רדוקציה משפה ב
R
היא פשוטה משום שאין צורך ב"התחכמויות" כדי לקבל את "התוצאה הרצויה".
אפשר פשוט לבדוק אם
X
נמצא בשפה או לא ואז לחשב בהתאם איבר שנמצא בשפה שאליה עושים רדוקציה או במשלימה שלה.

לשאלותיך האחרות-
 יש מה שנקרא "שפות שלימות ב-RE"
שהן שפות מ
RE
שניתן לעשות אליהן רדוקציה מכל שפה ב
RE
 יש שפות מ-
RE\R
שהן אכן "שלימות".
בכל אופן, זה כמובן דורש הוכחה (לא קשה) שלא ראיתם  בקורס הנוכחי.

[-] 2009 מועד ג שאלה 2א
by niram - Friday, 22 January 2010 14:54:18

שתי שאלות:
1) הם רשמו שם את הנקודה השלישית באלגוריתם שאם אין דחיה או קבלה במשך קיי צעדים אז אנחנו נדחה
אז עבור איזה קלט השורה הזאת תורמת לדחות אותו?
2)
עבור קידוד של מכונות שעושות פחות מ127 הזזות ימינה של הראש קורא/כותבואז רק עושות
LEFT
אז תמיד המכונה נכנסת ללופ אין סופי כי אם זזים שמאלה בתו הכי שמאלי אז אתה נשאר במקום וכך נמשיך בלופ אין סופי,
אבל המכונה הזאת עדיין שייכת לשפה ולמרות זאת אנחנו נדחה את המכונה הזאת בשורה שרשמתי ב1 כי לא קיבלנו דחייה או קבלה במשך קיי צעדים.

Re: 2009 מועד ג שאלה 2א
by gilamor - Friday, 22 January 2010 15:15:12
[-] רדוקציה : אם ורק אם????‏
by eitanco - Friday, 22 January 2010 16:01:58
האם רדוקציה היא משפט אם ורק אם?
זאת אומרת אני יודע כי
אם קיימת רדוקציה בין
L1
ל
L2
אז אני יודע ש
 L1<=L2

השאלה היא אם אני יודע ש
L1<=L2
(למשל 1 שייכת ל
RE\R
ו 2 לא שייכת ל
R)
אז האם אני יכול לומר כי קיימת רדוקציה (פונקציה) בין 1 ל 2.‏
[-] Re: רדוקציה : אם ורק אם????‏
by abuaffas - Friday, 22 January 2010 18:08:59

"Reduction" is not a theorem. It is a definition.
Definition:
We say that a language A is reducible to a language B if there exists a function F such that:
1) F is computable.
2) For every input x: x in A if and only if F(x) in B.

[-] Re: רדוקציה : אם ורק אם????‏
by barashd - Friday, 22 January 2010 21:42:57
מצטרף לשאלה על רדוקציה:
באחד המבחנים מופיעה השאלה

נכון או לא נכון:
קיימת שפה
L
עבורה מתקיים
L<=L_accept
אבל לא מתקיים
L<=L_halt

בתשובות מסומן כי המשפט אינו נכון-
אני יכול לחשוב על שתי סיבות-
אחת - בין כל שתי שפות באותה מחלקה קיימת רדוקציה כלשהי, גם אם קשה מאוד למצוא אותה.
שתיים- התשובה לא נכון נובעת מכך שהשפה
L_accept
מוכלת בתוך השפה
L_halt

אני חושב שהסיבה הראשונה היא מה שהבחור שרשם את תחילת השרשור התכוון
Re: רדוקציה : אם ורק אם????‏
by abuaffas - Saturday, 23 January 2010 01:22:16

הסיבה יותר פשוטה. זה נובע מטרנזטיביות הרדוקציות, כי ראינו שקיימת רדוקציה
Lacc<=Lhalt.

[-] L_empty set
by evgenim - Friday, 22 January 2010 16:27:46
לפי הבנתי זו השפה שמכילה את כל המכונת שהשפה שלהן ריקה. מדוע היא ב-
CO-RE?
(איך בונים מכונה למשלימה שלה?)
Re: L_empty set
by egozie - Friday, 22 January 2010 17:07:36
תסתכל על שאלה רביעית בתרגול 11...
זו אותה שפה רק שהיא כן מקבלת את כל המילים שהם לא מהצורה של שפת מכונה.
[-] מועד ג 2007, שאלה א
by tetinger - Friday, 22 January 2010 16:52:01

האם יש שפה מעל הא"ב של "0", שאיננה ב
RE
?

[-] Re: מועד ג 2007, שאלה א
by egozie - Friday, 22 January 2010 17:23:57
זו שאלה שבאה בכוונה לבזבז לך זמן חשיבה יקר בבחינה, כי זה הרי ברור שתנסה לחשוב על שפה כזו,
לעומת זאת התשובה פשוטה מאוד.
עוצמת כל השפות מקבלות הטיורינג,
RE,
היא א אפס, שכן, לפי מה שלמדנו, לכל שפה כזו קיימת מכונת טיורינג שמקבלת אותה, ז"א שכל מכונה היא מילה, ומספר המילים הוא בן מניה, סיגמא כוכב בכלל היא קבוצה בת מניה, כלומר אפשר למצוא לה פונקציה חח"ע ועל לטבעיים (אתה בטח זוכר את זה מסמסטר א').
עוצמת כל השפות מעל סיגמא כוכב היא א, למה? כי שים לב שאם תיקח את סיגמא כוכב, שהיא קבוצה אינסופית בעוצמה א אפס, כמו שאמרתי מקודם, ותעשה עליה קבוצה חזקה, תקבל בעצם את כל השפות, שהן בעוצמה א, גם את זה הוכחנו איפהשהו עם אורי אברהם באיזה שיעור משלים ב-8 בערב..

קיצר מסקנה
אם יש לך מספר שפות בעוצמה א, אך רק מספר שפות מתקבלות טיורינג בעוצמה א אפס, אז ברור שקיימת שפה שלא ב-
RE,
לכל סיגמא גדול מאפס.
(ברור שזה לא יעבוד אם אין לך אותיות בסיגמא)
[-] Re: מועד ג 2007, שאלה א
by tetinger - Friday, 22 January 2010 17:58:49

איפה אמרו שמספר המכונות המתקבלות טיורינג הוא בן מנייה ?
אולי יש שם גם מילים שאינן מכונות ..

[-] Re: מועד ג 2007, שאלה א
by egozie - Friday, 22 January 2010 18:12:41
יש מילים שאינן קידוד, וגם הן בנות מניה...
תסתכל על זה ככה:
Sigma = {a,b,c,...,n} - קבוצה סופית, חובה!!
Sigma* = P(Sigma) x קבוצה בת מניה - מספר האפשרויות לסידור כל קבוצה
אני יודע שזה קצת ערבוב של בדידה ולוגיקה, אבל ככה זה... חכה לקורס המשך של אוטומטים, חישוביות, או איך שלא קוראים לו, זה רק ילך ויסתבך ויערבב בתוכו את מבני נתונים...

[-] Re: מועד ג 2007, שאלה א
by tetinger - Friday, 22 January 2010 18:29:45

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

[-] Re: מועד ג 2007, שאלה א
by egozie - Friday, 22 January 2010 19:13:36
טוב גל, נקווה שהפעם תבין, כי אני כבר חופר..

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

*אם זה לא עונה על השאלה שלך, אני כנראה לא מבין אותה.
[-] Re: מועד ג 2007, שאלה א
by tetinger - Friday, 22 January 2010 21:02:04

שלא תבין אותי לא נכון .. אני מסכים עם מה שאמרת, אבל אני התכוונתי לזה שיכולים להיות ב 
RE
שפות שהם בכלל לא קשורים לקידודים של מכונות, הכוונה היא שאף אחד לא אמר שב
RE
יש רק קידודים של מכונות..

Re: מועד ג 2007, שאלה א
by gilamor - Sunday, 24 January 2010 10:10:01
זה נכון שהמילים בתוך שפה אינן בהכרח קידודים של מכונות,
אבל לכל שפה ב
RE
בהכרח מתאימה מכונת טיורינג- המכונה שמקבלת אותה.
[-] מועד ג 2009 שאלה 2ב'
by olgasib - Friday, 22 January 2010 17:23:51
מה לא בסדר ברדוקציה?
הרי אפסילון לא שייך לקבוצה הריקה?...
תודה
Re: מועד ג 2009 שאלה 2ב'
by abuaffas - Friday, 22 January 2010 17:41:53
Is F(x) computable?
[-] a^nb^nc^nd^n
by eladgoo - Friday, 22 January 2010 17:49:54

לפי הדף שפרסמתם a^nb^nc^nd^n  היא ב-R , אבל זה לא נכון שהשפה אפילו לא ח"ה ?

[-] Re: a^nb^nc^nd^n
by abuaffas - Friday, 22 January 2010 18:13:21
a^nb^nc^nd^n is not CF language.
[-] Re: a^nb^nc^nd^n
by eladgoo - Saturday, 23 January 2010 11:27:27

so way do you say that it's in R ?

Re: a^nb^nc^nd^n
by erantom - Saturday, 23 January 2010 13:12:13

The 2 claims are independent. R is the collection of all Turing decideble languages, CF is the collection
of lenguages that are acceptible by a context free grammar.

[-] האם הוכחנו בכתה סגירות תחת reverse
by amirelu - Friday, 22 January 2010 18:07:34
אני זוכר שעבור רגולריות כן. האם הוכחנו עבור חסרות הקשר?
מה לגבי R וRE?

עבור R
זה דיי ברור שכן אבל מותר להגיד את זה או שצריך להסביר\להוכיח?
Re: האם הוכחנו בכתה סגירות תחת reverse
by abuaffas - Friday, 22 January 2010 18:15:57

All classes we have seen are closed under "reverse". the proof is quite simple.

[-] 2008 מועד ב', שאלה 1 סעיף ד
by evgenim - Friday, 22 January 2010 20:03:27
האם הפונקציה המתוארת היא הומומורפיזם?
(מספיק להגדיר שזו פונקציה שמעבירה אות בא"ב אחד לאות בא"ב אחר?)
[-] Re: 2008 מועד ב', שאלה 1 סעיף ד
by abuaffas - Saturday, 23 January 2010 01:37:32
זה יכול לעזור?
Re: 2008 מועד ב', שאלה 1 סעיף ד
by barashd - Saturday, 23 January 2010 13:00:44
אז בעצם, לא ניתן להשתמש בשאלה זאת במשפט-
"השפות הרגולריות סגורות תחת הופכיים של הומומורפיזם"
כי אנחנו לא יודעים בוודאות שלפונקציה בשאלה יש
פונקציה הופכית?

(אחרת התשובה לשאלה הייתה צריכה להיות נכון


[-] Re: 2008 מועד ב', שאלה 1 סעיף ד
by shayas - Saturday, 23 January 2010 05:47:33
כן היא הומומורפיזם
ומה שאמרת הוא מספיק ,היא יכולה גם לעבור מאות אחת למילה ארוכה

[-] Re: 2008 מועד ב', שאלה 1 סעיף ד
by charchma - Saturday, 23 January 2010 17:35:55
אם היא הומומורפיזם, וידוע שהשפות הרגולריות סגורות תחת הומומורפיזם והופכי של הומומורפיזם, מדוע
הטענה בשאלה לא נכונה?
האם פונקצית ההומומורפיזם חייבת להיות חח"ע, ע"מ שניתן יהיה להגיד שהשפות הרגולריות סגורות תחת ההופכית שלה?
(וע"מ שתהיה לה פונקיה הופכית?)


Re: 2008 מועד ב', שאלה 1 סעיף ד
by shayas - Saturday, 23 January 2010 18:21:32
כי המשפט אומר שאם קיימת שפה רגולרית ופונ' הומומורפית אז השפה שתתקבל תהיה גם רגולרית
אבל אם יש שפה לא רגולרית ופונ' הומומורפית אז השפה שתתקבל גם יכולה להיות רגולרית,כי אין שום מגבלה כזאת לפי המשפט
[-] שאלה מ 2006
by tetinger - Friday, 22 January 2010 23:25:14
http://www.cs.bgu.ac.il/~auto101/wiki.files/auto061%20exam%20moed%20a%202006.doc
שאלה 2, האם היחס הוא
L reg מוכל ב Lincrease
בכלל ש
L increase
היא סופית ?
[-] Re: שאלה מ 2006
by barashd - Saturday, 23 January 2010 01:33:44
Lincrease
איננה סופית-
 מפני היא משפחת שפות שעבורן קיים דקדוק ח"ה עולה, ובקלות אפשר
לחשוב על אינסוף דקדוקים כאלו.

אולי התכוונת לכך שכל מילה בשפה שנגזרת מדקדוק כזה היא סופית
וזה לדעתי מה שקורה כאן- מספר כללי הגזירה שאפשר להשתמש בהם מהמשתנה ההתחלתי עד לסוף הגזירה חסום
על ידי מספר האותיות הלא סופיות
לכן מספר האפשרויות לגזור מילה סופי, ולכן השפה רגולרית
[-] Re: שאלה מ 2006
by tetinger - Saturday, 23 January 2010 12:37:58

התכוונתי שכל שפה בקבוצה הזו היא סופית, ולכן היא מוכלת ברגולריות..

[-] Re: שאלה מ 2006
by abuaffas - Saturday, 23 January 2010 15:32:46
That's right.
[-] Re: שאלה מ 2006
by zahavl - Saturday, 23 January 2010 16:37:11
לא הצלחתי להבין למה כל שפה בקבוצה זו היא סופית?
 הרי אפשר להגדיר ביטוי אינסופי בצד ימין של הדקדוק משהו כמו
 S->D*
D->a
אשמח להסבר נוסף
Re: שאלה מ 2006
by abuaffas - Saturday, 23 January 2010 18:12:00

R is a finite set of rules.
(S->D*) is not a legal rule.It means S->D|DD|...|Dk|...., whish is infinte.

[-] חיתוך בין שפות חסרות הקשר ושפות רגולריות
by galaf - Friday, 22 January 2010 23:41:51
בפתרון של מבחן 2009 מועד א שאלה 1 סעיף ב כתוב:
חיתוך של שפה רגולרית עם שפה חפשית הקשר יוצר שפה חפשית הקשר

אבל מה בנוגע לחיתוך בין:

a^n b^n c* - CFL

a^n b* c* - reg

בחיתוך בינהן מתקבלת שפה שאינה חסרת הקשר.. לא?
[-] Re: חיתוך בין שפות חסרות הקשר ושפות רגולריות
by barashd - Saturday, 23 January 2010 00:11:11
אני חושב ש
a^n b* c*
היא לא מה שהתכוונת...
האות
n
לא יוצרת שום אילוץ על השפה השנייה, בניגוד לשפה הראשונה שבה שני ההופעות של
n
מאלצות מספר זהה של
a,b
בכל מקרה, השפה הראשונה מוכלת בשנייה, החיתוך שלהן הוא השפה הראשונה
והיא חסרת הקשר

נכון או לא ?

[-] Re: חיתוך בין שפות חסרות הקשר ושפות רגולריות
by galaf - Saturday, 23 January 2010 01:00:28
סליחה טעיתי! התכוונתי ל:

a* b^n c^n - CFL

a^n b* c* - reg

עכשיו החיתוך יוצא:
a^n b^n c^n

לא?
Re: חיתוך בין שפות חסרות הקשר ושפות רגולריות
by barashd - Saturday, 23 January 2010 01:14:29
לא
אין משמעות לאות
n
בשפה הרגולרית, היה יותר נכון לרשום שם פשוט כוכבית קליני
אין קשר בין ה-
n
בשפה הראשונה, לבין זה שבשפה השנייה

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

[-] Re: חיתוך בין שפות חסרות הקשר ושפות רגולריות
by abuaffas - Saturday, 23 January 2010 01:16:57
n in the second language is meaningless. If n>=0 then the language is a*b*c* and the intersection is a* b^n c^n.
Re: חיתוך בין שפות חסרות הקשר ושפות רגולריות
by galaf - Saturday, 23 January 2010 02:28:19
תודה! :)
נראה לי שהבנתי..


[-] רדוקציה בין 2 שפות באותה מחלקה
by vadimlia - Saturday, 23 January 2010 00:51:27
האם בהכרח קיימת רדוקציה בין כל שתי שפות הנמצאות באותה מחלקה?
RE\R, RE, R, CO-RE
לא למדנו כזה דבר, אבל כל האינטואיציה וההגיון, וגם כמה מהפתרונות של מבחנים רומזים על זה
Re: רדוקציה בין 2 שפות באותה מחלקה
by abuaffas - Saturday, 23 January 2010 01:26:09

ענינו על זה בשרשורים קודמים.

[-] תיקון - מבחן 2009 מועד א שאלה 2 ב
by galaf - Saturday, 23 January 2010 14:21:32
בפתרון לסעיף זה כתוב:
נגדיר:
L = { <M> : L(M) = empty group}l

ממשפט רייס נובע שהשפה אינה ב
RE


לא הבנתי איך מסיקים את זה ממשפט רייס? איזו תכונה אפשר להגדיר על השפה הזו?

בנוסף, באותו סעיף כתוב:
צריך למצוא מ"ט אי דטרמיניסטית שמקבלת אותה
בכדי להראות ששפה ב
CO-RE

אם ככה - אז לכל השפות ב
CO-RE
יש מ"ט אי דטר' שמקבלת אותה?
[-] Re: תיקון - מבחן 2009 מועד א שאלה 2 ב
by galaf - Saturday, 23 January 2010 14:29:52
האם אפשר באמצעות רדוקציה להוכיח שהשפה
L
אינה ב
RE
?
אני עדיין לא מבינה איך זה נובע ממשפט רייס, פשוט הייתי שמחה להבין גם איך לפתור לפי רדוקציה..

תודה רבה
Re: תיקון - מבחן 2009 מועד א שאלה 2 ב
by abuaffas - Saturday, 23 January 2010 15:30:40
P={L in RE : L=empty_set}={empty_set}.
P is not trivial and contains empty_set. Hence LP=L is not in RE.

You can also show that by simple reduction from comp(Lacc).
if x=<M>,<w> then F(x)=<Mw>.
[-] מועד א 2005 שאלה 3
by vhava - Saturday, 23 January 2010 11:00:27
האם ניתן להוכיח באמצעות משפט רייס כי השפה אינה שייכת לRE
ניתן לבנות תכונות המתייחסת לחיתוך שפות סופי
ומכאן להשתמש ברייס?
Re: מועד א 2005 שאלה 3
by abuaffas - Saturday, 23 January 2010 15:55:04
No, you cann't.
If you difine a property P, later, you should claim that LP is equal to L. How could you do that if LP={<M> : ....}?
[-] Re: מועד א 2005 שאלה 3
by egozie - Saturday, 23 January 2010 16:45:56
המפתח להבנת משפט רייס באמת הוא זה:
RE -את התכונה שצריך להגדיר ועליה לעבוד צריך לבדוק בראש ובראשונה, האם מדובר בתכונה המוכלת ב
דרך עבודה מומלצת היא לעשות שני שלבים פשוטים:
  •  לקחת בדיוק את התנאי הנתון, ולהפוך אותו לתכונה
  •   RE -לבדוק האם התכונה קיימת רק ב
לדוגמת השאלה שהצגת:
L={<M1><M2>  :  |L(M1) intersection L(M2)|  is finite}
  • שלב ראשון - נהפוך את התנאי לתכונה
P={L1,L2  :  |L1 intersection L2|  is finite}
  • RE -שלב שני - נבדוק האם התכונה קיימת רק ב
וכמובן שלא.
 שמקיימות את התנאיRE -כי אני יכול למצוא שתי שפות מחוץ ל
L1 = L Sigma*
L2 = (L Sigma*)'        (משלים = ' )
|L1 intersection L2| = 0    => סופי

ולכן אי אפשר להשתמש במשפט רייס פה
Re: מועד א 2005 שאלה 3
by gilamor - Sunday, 24 January 2010 10:07:05

התכונה שהגדרת מתייחסת לזוגות של שפות ולא לשפות!

by - Thursday, 1 January 1970 02:00:00
[-] שייכות שפות ל RE
by hofitel - Saturday, 23 January 2010 16:22:38
האם נכון:

אם שפה בRE
ומשלימתה לא ב RE
אז השפה אינה ב R
[-] Re: שייכות שפות ל RE
by seidnerj - Saturday, 23 January 2010 16:25:53
אם L נמצאת ב-RE והמשלימה שלה לא ב-RE לא יתכן שהשפה ב-R כי אז המשלימה שלה גם ב-R ובפרט ב-RE
Re: שייכות שפות ל RE
by abuaffas - Saturday, 23 January 2010 18:18:43
If L is in R then comp(L) is also in R and, in particular, comp(L) is in RE.
[-] מועד ב 2006 שאלה 1 ה
by gshir - Saturday, 23 January 2010 17:24:09

מישהו יכול להסביר בבקשה את התשובה לשאלה הבאה-

"קיימת שפה
L
שלא שייכת ל-
R
המקיימת את תנאי למת הניפוח לשפות רגולריות."

[-] Re: מועד ב 2006 שאלה 1 ה
by abuaffas - Saturday, 23 January 2010 17:57:16
תגדיר שפה דומה לשפה משאלה 2 בתרגול 5.
Re: מועד ב 2006 שאלה 1 ה
by gshir - Saturday, 23 January 2010 18:24:46
אפשר להניח שקידוד תמיד יתחיל ב-
CI
?
[-] סגירות תחת הפרש - ועוד שאלה
by moshedem - Saturday, 23 January 2010 18:44:57
האם משפחת השפות הרגולריות סגור תחת הפרש (והפרש סימטרי)
ומה בנוגע ל R?

ועוד שאלה
2007 מועד א'

מישהו יכול להסביר את קיום הקבוע שסדרת ההפרשים של שפה ח"ה חסומה על ידו?
(ראיתי את ההסבר מתרגול 9 - לא הצלחתי לרדת לסוף דעתו)

Re: סגירות תחת הפרש - ועוד שאלה
by benezrab - Sunday, 24 January 2010 00:00:57
משפחת השפות הרגולריות סגורה תחת הכל- איחוד חיתוך, משלים כוכב קליני ושרשור, וכן מש' השפות הכריעות טיורינג.
 לא סגורה תחת משליםRE , לעומת זאת
Re: סגירות תחת הפרש - ועוד שאלה
by egozie - Sunday, 24 January 2010 01:29:08
תשנן את הטבלא הזו
http://en.wikipedia.org/wiki/Formal_language#Operations_on_languages

ותשתמש קצת במשפט דה מורגן
הפרש והפרש סימטרי זה בעצם משחק עם חיתוך ומשלים, לא יותר מזה...
[-] Mw המכונה
by caspiy - Saturday, 23 January 2010 19:27:02

in class we talked about a TM called Mw which ignores any input and simulates M on w and answers the same as M.

what happens if M doesnt stop on w?

[-] Re: Mw המכונה
by shayas - Saturday, 23 January 2010 19:37:47
אז


Mw

  לא תקבל שום מילה לכן השפה שלה
 L(Mw)
היא השפה הריקה
שים לב שיש פה שני מ"ט שונות
הראשונה היא
M
השניה היא
Mw
,
ויכול להיות ש

L(M)!=השפה הריקה

מצד שני
אם
M
מקבלת W
אז השפה של
Mw
היא סיגמא כוכב
ובשפה של
M
יהיה לפחות את המילה
W
Re: Mw המכונה
by abuaffas - Saturday, 23 January 2010 19:38:12
Iif M doesn't stop on w then Mw dosen't stop on any input.
Questions that Ronen was asked
by abuaffas - Saturday, 23 January 2010 19:34:05
Q. Does the definition of a computable function require that the machine be deterministic?
A. The definition we used in class implicitly assumes that the machine computing the function is deterministic.   However, this is not necessary. For non-deterministic TM, the definition would require that there is a computation in which an accepting state is reached, and that whenever an accepting state is reached, F(x) is written on the tape.

Q.  Show L1 and L2 in RE\R such that L1 U L2 is in R.
A. Let L1= {x: (x= <M>,<w> and M accepts w) or x  has even length}.
     Let L2= {x: (x= <M>,<w> and M accepts w) or x  has odd length}.
     L1 and L2 are in RE\R, but L1 U L2 is in R.

Q.  Is {<M> | L(M) = {<M>} }=empty_set??
A. No. This can be shown using the recursion theorem, which was not covered in all classes.
[-] איך פעולות בין שפות רגולריות משפיעות על ה RANK
by shayas - Saturday, 23 January 2010 19:49:40
כידוע השפה הרגולרית סגורה תחת כל הפעולות,אבל כיצד כל פעולה יכולה להשפיע על מס' מחלקות השקילות זה לא תמיד ברור,לכן אני אשמח אם תוכלו לתת תשובה קצרה או אפילו הסבר למה למקרים הבאים:
א. יהיו שפות רגולריות
L1
עם RANK(L1)=k
ו-L2
RANK(L2)=m
אז יכול להתקיים
איחוד:
RANK(L1UL2)<k+m?
RANK(L1UL2)>k+m?
שירשור:
RANK(L1ְL2)>k+m?
RANK(L1ְL2)<k+m?
משלים:
:
RANK(comp(L1))<k?
RANK(comp(L1))>k?
חיתוך:
:
RANK(L1^L2)<k+m?
RANK(L1^L2)>k+m?
[-] Re: איך פעולות בין שפות רגולריות משפיעות על ה RANK
by yanivpar - Saturday, 23 January 2010 22:04:01
אני חושב ש :

Rank(L1UL2) = Rank(comp(comp(L1) ^ comp(L2))) = Rank ( L1 ^ L2)

אם זה יכול לעזור....
[-] Re: איך פעולות בין שפות רגולריות משפיעות על ה RANK
by taig - Saturday, 23 January 2010 22:54:17
please see p.s 6 , page 10 to get answer to some of these questions and a very good intuition for the rest.
another hint : for unification think about the case : L2 = comp (L1);
Re: איך פעולות בין שפות רגולריות משפיעות על ה RANK
by shayas - Saturday, 23 January 2010 23:18:28
זה בכלל לא קרוב אפילו למה ששאלתי
אינטואיציה יש לי ,רציתי לוודא שהיא לא רק שלי כי אין לי הוכחה לשאלות כמו ההוכחה של המשלים שרשמו פה וזה גם לא קשור לשאלה שלי
אני שואל על מס' מחלקות השקילות אחרי פעולה בין שתי שפות רגולריות ביחס סדר קווי
אפשר גם להגיד כן ,לא או לא מתכוון\יכול לענות על זה,
אני יודע שיש תרגול וקראתי והייתי בו לפני ששאלתי
[-] שאלה
by berda - Saturday, 23 January 2010 20:47:43
האם לכל 2 שפות  ב
RE\R
יש רדוקציה אחת לשנייה(לשני הכיוונים)
ואם לא, אפשר לקבל דוגמא ל2 שפות שאין רדוקציה בין האחת לשנייה

תודה
[-] Re: שאלה
by egozie - Saturday, 23 January 2010 20:59:56
זה בדיוק כל העניין ברדוקציה
המשפט אומר:
L1<=L2   => L1 חזקה לפחות כמו L2
יש להן בדיוק את אותו החוזק RE\R -לכן אם שתי השפות ב
משמע ניתן לעשות גם רדוקציה וגם רדוקציה הפוכה.

ואפילו יותר לעומק מזה,
כלשהי f(x) נניח וברדוקציה עשית פונקציה
אז ברדוקציה ההפוכה תהיה הפונקציה
f -1(f(x))
[-] Re: שאלה
by yanivpar - Saturday, 23 January 2010 22:35:32
אז למה במחלקה R
ניתן למצוא דוגמה נגדית ?
נניח..
משפה כלשהי לאל סיגמא כוכב
Re: שאלה
by taig - Saturday, 23 January 2010 23:08:56

you can find a reduction between any 2 languages in RE/R.
please note that this is not true for any group of languages and specifically not true for a trivial language as sigma star .

[-] Re: שאלה
by yaariy - Saturday, 23 January 2010 22:57:16
כן אבל לא הוגדר מה זה קושי, וגם אם כן הוגדר לא הוכיחו באף מקום שאם 2 שפות הן באותה דרגת קושי יש ביניהן רדוקציה דו כיוונית. רק אמרו שיש רדקוציה משפה קשה לשפה קלה יותר (או שלהפך, לא משנה) ולראייה באמת שב2 שפות באר לא תמיד יש רדוקציה
Re: שאלה
by taig - Sunday, 24 January 2010 00:03:35
don't worry , you don't have to know nothing that wasn't proved or defined in class , this was just an answer to the above question.
you might be asked questions that will ask you to conclude the relations between languages based on the knowledge and theorems we proved in class. no panic(:
[-] מועד ג' 2007
by shmuelku - Saturday, 23 January 2010 21:38:09
אני יודע שזה קצת צמוד למבחן אבל יש אפשרות שאחד המתרגלים יעלה תשובות ל חלק של הנכון לא נכון במבחן של 2007 מועד ג
פשוט השאלות שם יחסית ברמה גבוהה ונראה לי שיעזרו לענות לחלק מהנוכחים בפרום על הרבה שאלות שהיו
ובכמובן גם לי
Re: מועד ג' 2007
by taig - Saturday, 23 January 2010 23:11:26

some of the solutions and general intuition:

1/ correct - we talked/saw on Ex. 5 that we can encode turing machines over one-latter sigma.
2/ correct - proved at p.s.
3/ true - R is closed both under reverse and unification.
4/ false - CFL are closed under reverse but not necessarily under intersection.
5/ false - think about the meaning of this reduction on the complement languages.
7/ false - see some similar answers in the forum.

good luck

[-] 2006.. טייסים?
by goltshiy - Sunday, 24 January 2010 00:11:01
TypeError: Cannot read property 'document' of undefined
[-] Re: 2006.. טייסים?
by goltshiy - Sunday, 24 January 2010 00:12:43

א.      קיימת שפה רגולרית  כך שבכל אוטומט מחסנית המקבל את יש שלשה מצבים לפחות.

Re: 2006.. טייסים?
by gilamor - Sunday, 24 January 2010 10:03:26
מה השאלה שלך לגבי זה?

התשובה היא כן- למשל השפה שמכילה רק את המילה 00.
זה שמדובר באוטומט מחסנית לא מעלה ולא מוסיף.
[-] מועד ב 2006
by tamirha - Sunday, 24 January 2010 10:45:54
נתקענו קצת עם שאלות 1 ד וה במבחן 2006 טייס מועד ב
אפשר בבקשה לקבל עזרה איתן?
Re: מועד ב 2006
by egozie - Sunday, 24 January 2010 14:41:32
אלו שתי שאלות קשות, אני מודה, הפיתרון לא טריוויאלי בכלל אני אשמח לשמוע פתרון רשמי
סעיף ד'

התשובה היא לא נכון,
אבל אני לא בטוח שהנימוק הוא הוכחה פורמלית לכך!
נניח בשלילה שאכן קיימת שפה רגולרית כך ש-
LA={ <M> | L(M)=A } שייך  RE\R
המקבלת אותה <MA> אזי קיימת מכונה
על כל סיגמא כוכב, באיטרציות לפי סדר לקסיקוגרפיM תריץ את <MA> המכונה ,<M>אם כך, בהינתן מילה
(הכל על מנת שהיא לא תיתקע כמובן)
בסופו של דבר, יכולים להיות שני מקרים:

   1. השפה היא סופית, ולכן החל ממילה מסויימת, המכונה צריכה לדאוג שלא תקבל אף מילה יותר
   2. השפה היא אינסופית, והמכונה תמשיך לחפש מילים תמיד

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

סעיף ה'
טוב ההוכחה שכתבתי מלאה בחורים, אני מעדיף לשמוע פתרון מרצה
דקדוק לינארי
by shayas - Sunday, 24 January 2010 10:47:36
סעיף ב' לא ממש מובן
תהי מילה שנוצרה מדקדוק ליניארי
יהיה הפירוק

 UVXYZ
בלמת הניפוח "המיוחדת "של הדקדוק הלינארי
אז
 |UVYZ|<=K
על מה ולמה העלימו את
X
מהמשוואה
ואם הכניסו את
U
Z
אז למה שלא יכניסו אותם גם בלמת הניפוח לשפות ח"ה רגילות
[-] פתרון רשמי למועד א'
by khmelnik - Monday, 25 January 2010 08:33:03
אפשר לפרסם פתרון רשמי למועד א' , לטובת אלו שניגשים גם למועד הבא ?
תודה מראש
[-] Re: פתרון רשמי למועד א'
by mazov - Monday, 25 January 2010 19:45:21
תודה על הפתרון.

אבל אפשר בבקשה להוסיף את הפתרון של 2 ג ו3א לפתרון?
[-] Re: פתרון רשמי למועד א'
by hico - Monday, 25 January 2010 20:26:16
מצטרפת לבקשה..

בתודה מראש...
Re: פתרון רשמי למועד א'
by auto101 - Tuesday, 26 January 2010 07:19:48
בטעות העלנו גרסא ראשונית של הפתרון. עכשיו הועלתה הגרסה המלאה.
[-] עבודות
by noakad - Tuesday, 26 January 2010 13:35:38
שלום
מתי יפורסמו ציוני העבודות האחרונות?
תודה
Re: עבודות
by shayas - Wednesday, 27 January 2010 16:55:36

תשלחי מייל אולי יענו לך שמה ,לפחות בסבירות יותר גבוהה

ואולי אפילו תקבלי תשובה מהבודק בכבודו
[-] בפתרון המבחן שאלה 1 סעיף ה
by igortroy - Thursday, 28 January 2010 12:47:04
(the NFA with K states)

assume K is a constant. let L be the language which includes only the word a^K, over the alphabet {a,b}.

the NFA for L includes K states (with "a" passages between them), and L is not empty.

moreover, w of length K that is w=a^K, is in L. but every word of length less than K is not in L.

my answer to this part was "WRONG", while the solution stats "RIGHT".

where is my mistake?
Re: בפתרון המבחן שאלה 1 סעיף ה
by eitanyar - Thursday, 28 January 2010 14:23:07
Your mistake is that you assumed that an NFA with K states accepts the word a^k,
you have K states but only K-1 passages between the states, of "a" in your case.
So it means your NFA accepts a^(k-1) and not a^k.
[-] שעות קבלה לקראת מועד ב'
by khmelnik - Friday, 29 January 2010 11:14:39

שלום ,

לקראת מועד ב'  , האם יש שינוי בשעות הקבלה של הסגל ? או

ששעות הקבלה הן השעות קבועות לשבוע הבא ?

תודה

מראש
[-] Re: שעות קבלה לקראת מועד ב'
by hico - Monday, 1 February 2010 20:22:06
נשמח לתשובה.. זה חשוב ממש

תודה רבה!
Re: שעות קבלה לקראת מועד ב'
by auto101 - Tuesday, 2 February 2010 13:08:50
אנחנו נפרסם הודעה לגבי המועדים של שעות הקבלה.
[-] פקטור שלילי?!
by gabaev - Wednesday, 3 February 2010 17:21:31
זה נראה לכם הגיוני שהפקטור הוריד לי יותר מ-10 נקודות?!
Re: פקטור שלילי?!
by egozie - Wednesday, 3 February 2010 17:23:40
גם לי!
זה כאילו קיבלתי 0 על השאלה השלישית!!
[-] חישוב הציון הסופי
by cgal - Wednesday, 3 February 2010 18:13:57
בתחילת הסמסטר נאמר לנו שהחישוב הוא:
12.75 * ציון בוחן ראשון
12.75 * ציון בוחן שני
15 * עבודות
השאר (59.5) * ציון המבחן

החישוב שמפורסם באתר זה הוא לא בדיוק אותו דבר אבל הוא דומה.
בכל אופן שני החישובים נותנים לי את אותו ציון (בהפרש של 0.3 נקודות).
שמתי לב שלא כך הם חישבו את הניקוד. יש למישהו מושג מה היה החישוב?
[-] Re: חישוב הציון הסופי
by caspiy - Wednesday, 3 February 2010 17:33:54

מקומם.. זה התגמול על השקעה בקורס?
ממש מעודד אותנו להמשיך ללמוד באוניברסיטה.

Re: חישוב הציון הסופי
by eitanyar - Wednesday, 3 February 2010 17:36:34
מה אתם כולכם בלחץ זה בטח טעות חישובית שתתוקן בהקדם
[-] Re: חישוב הציון הסופי
by itayfai - Wednesday, 3 February 2010 18:08:02

החישוב שציינת רשום כך גם באתר הקורס
מוזר.....

[-] Re: חישוב הציון הסופי
by kaplanyo - Wednesday, 3 February 2010 18:12:41
לא הבנת את הבעיה ,זה לא איך מחשבים את הציון לפי המרכיבים אלא ציון הבחינה עצמה.
הם הורידו מציון הבחינה.
אם קיבלת 80 הציון של המבחן הוא 68 בערך.
ז"א שהורידו לך 12 מהציון הגולמי.
ברור שזה נראה מאוד מאוד לא הוגן ולא בסדר.
[-] Re: חישוב הציון הסופי
by cgal - Wednesday, 3 February 2010 18:15:47
זה משהו אחר, נירמול זה נירמול ולפעמים זה בא לרעתנו, אבל אין מה לעשות (לפחות לא נראה לי).
אני מדבר על חישוב הציון הסופי בעזרת המרכיבים לאחר הנרמול.

[-] Re: חישוב הציון הסופי
by shayas - Wednesday, 3 February 2010 18:17:35
 cgal איך אתה מדבר ככה
אתה מאלו שקיבלו 100 והנירמול לא הוריד להם נקודה נכון?
[-] Re: חישוב הציון הסופי
by cgal - Wednesday, 3 February 2010 18:19:20
קיבלתי 97 ונרמלו ל94
אל תדאג מצבי פחות טוב ממה שאתה חושב
[-] Re: חישוב הציון הסופי
by shayas - Wednesday, 3 February 2010 18:29:06
תשמע אתה לא אמיתי
אם היו מורידים לך 12 נק' כמו מי שקיבל באזור  85 היית משתולל עכשיו
עכשיו אחרי שהורידו לי כמעט 10 נק' גם אני קונה -3 ו 94
אבל אפילו ה
-3
 זה משהו שלא צריך להיות
אם היו אומרים שיש נירמול מראשאז הייתי דורש שיהיה נירמול על כל המבחנים שהייתי בהם ושייכים למחלקה למדעי המחשב ולא רק לזה
אי אפשר לעשות רק כשנוח
וגם אי אפשר להפתיע אנשים' ככה
חבל שבכלל השקעתי למועד הזה הייתי ישר ניגש למועד הבא  ולומד למקצועות אחרים כי מסתבר ש-90 לא מספיק גם אם אתה יודע את החומר ובינינו מה ההבדל הגדול בין מי שקיבל 90 לבין מי שקיבל 97 לבין מי שקיבל 80,זה לא תמיד הבדל גדול אז למה שאתה תזכה מההפקר וחלק יענשו יותר
[-] Re: חישוב הציון הסופי
by kaplanyo - Wednesday, 3 February 2010 18:32:01

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

[-] Re: חישוב הציון הסופי
by shayas - Wednesday, 3 February 2010 18:35:14
אתה צודק אבל מבחינת ההרגשה
 עדיף לקבל 50 ולקבל את מה שמגיע לך בסוף
מאשר לקבל 90-80 ושיורדו לך 10 נק'
[-] Re: חישוב הציון הסופי
by egozie - Wednesday, 3 February 2010 18:52:36
מילא הייתם מנרמלים ב-5 נקודות לכולם, אבל איך זה שמי שקיבל 90+ מקבל איזה 0-5 נקודות פחות ומי שקיבל 70-90 מקבל 8-12 נקודות פחות?!
אפילו מי שקיבל 60 הורידו לו פחות נקודות!!
Re: חישוב הציון הסופי
by shayas - Wednesday, 3 February 2010 18:53:56
מה מילא מנרמלים?לא צריכים לנרמל בכלל ברגע שאתה אומר שצריך לנרמל לכולם שווה אז יבואו מי שקיבל 100 ומי שקיבל 50 ויגיד אני ככה ואני ככה
אפשר בבקשה לקבל איזושהי התייחסות מצוות הקורס לגבי הציון בבחינה? על מה הנירמול השלילי בדיוק?...
by digmia - Wednesday, 3 February 2010 18:25:10
תודה.
[-] נשמע מאוד לא הוגן מה שקרה פה. הנרמול פשוט לא סביר
by kaplanyo - Wednesday, 3 February 2010 18:28:34

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

Re: נשמע מאוד לא הוגן מה שקרה פה. הנרמול פשוט לא סביר
by egozie - Wednesday, 3 February 2010 18:46:56
הפסקתי ללמוד להיום, אני לא מסוגל להתרכז בכלום.
כבר חשבתי אולי להעלות את הממוצע שלי, טעיתי!
במינוס 11 נקודות טעיתי!!!
[-] אכזבה
by miripe - Wednesday, 3 February 2010 19:09:37

 כשפנינו אליכם ע"מ להקל עלינו עם החישוב הסופי של הבחנים
התעקשתם שלא משנים את חוקי המשחק באמצע!!!

" It's impossible to change the rules of the
> game in the middlle.
"

דבקת בזה לאורך כל הדרך ולא הסכמת להגן עלינו עם הבחנים
אבל לתת פקטור שלילי זה בסדר??!!!
אני המומה וכולנו המומים איך יתכן מעשה שכזה??
הורדתם לי 10 נקודות מהמבחן ! על מה ולמה?

אנחנו לא מקבלים את הדרך הזו ואני באופן אישי אגש בכל הכוח לכל מי שאפשר ע"מ לתקן את העוול שנגרם פה
זה פשוט לא יאומן! נדמה שאנחנו שק חבטות ממש,
למה אנחנו צריכים להרגיש שהולכים איתנו ראש בראש?!
בכוח להכשיל? באנו ללמוד לא באנו למשחקי כוחות!
באנו למוסד אקדמאי שמכבד את עצמו, תכבדו אותנו גם!
אנחנו סהכ רוצים את מה שמגיע לנו!
לא מספיק הבחנים הסיברים שנועדו שחור על גבי לבן להכשיל אותנו
גם עכשיו במבחן משנים פתאום את החוקים?! אין יותר 105?! פקטור שלילי?!
תעמדו אחרי המילה שלכם, לא יעלה על הדעת שתביאו מבחן יחסית לא קשה ואחכ תתחרטו על זה!
על זה נאמר עם כל הכובד של המילה - הרצחתם וגם ירשתם!

ואני מבקשת מכל חברי המחלקה לא לשבת בחיבוק ידיים, גם אלו שה"נרמול" לא פגע בהם.
זו זכותנו!
[-] Re: אכזבה
by shayas - Wednesday, 3 February 2010 19:13:35
הסיבה היחידה שאנשים קיבלו פה ציונים בשמיים זה כי העבודות היו מאוד מאוד קשות בכמה רמות מעל לעבודות
בשנים שעברו
ואנשים השקיעו את כל הזמן שלהם על העבודות
וזה יבוא לידי ביטוי בציונים נמוכים יותר במקצועות אחרים בדר"כ הממוצעים בהם היו בשמים כמו
\
 SPL
זה היה מועד א' סטנדרטי
ואי אפשר להגיד שהוא קל ואם לא הציונים האלו הוא אפילו מעל  לממוצע
[-] Re: אכזבה
by abumokhz - Wednesday, 3 February 2010 19:24:20

סיבה אחרת ... למה אני שקבלתי 78 מקבל סופי 66..
אך מי שקבל מעל 90 מורידים לו 2-3 נק'
12 נק' מול 2 נקודות ... זה הגיוני???????????

Re: אכזבה
by shayas - Wednesday, 3 February 2010 19:26:36
אני קיבלתי בדיוק 90 והורידו לי 8 נק' אז אני לא יודע על מה אתה מדבר מי שקיבל 95 קיבל מעל 90 
ואתה צודק יש עוד סיבות
גם זה שהיו שני בחנים
תרמו לידע של סטודנטים
כנראה שעדיף לא ללמוד גם ככה יפתיעו אותך ויקחו לך נקודות
[-] אסור לוותר
by ohadas - Wednesday, 3 February 2010 19:58:23
בדיוק שרציתי לשלוח מייל למרצים להודות להם על קורס, שלפי דעתי נוהל באופן מושלם.
שבאמת המתרגלים והמרצים נתנו בו הכל, העלו ישר פתרונות לתרגילים, העלו את התרגולים לפני כל שיעור. הכל היה מסודר....
עד שהם החליטו לשנות את חוקי המשחק...
אני טוען שאם הייתי יודע על ה"נירמול" הזה הייתי מתייחס למבחן הזה אחרת, אולי הייתי משקיע יותר בבחנים, אולי יותר בעבודות.
הם לא יכולים להגיד לנו לאחר מעשה, אנחנו משנים אתחוקי המשחק, מתי??? שנגמר הסמסטר??.
בנוסף,הם צריכים להתייחס באופן שווה לכל הסטודנטים, אזי הם צריכים לנרמל את כל הציונים, כולל אלו שקיבלו 100
אבל כאן נכנס פרדוקס, איך מישהו שפתר הכל נכון לא יקבל 100?

אני אציין ואומר שלא היה מבחן יותר קל משנים קודמות...
הסיבות שכולם הצליחו במבחן הן:
1.היו עבודות ברמה גבוהה והבדיקה הייתה קפדנית, כך שידעת באיזה חומר את פחות שולט טוב.
2.אולי שכחתם, אבל עשינו 2 בחנים שהיו לא קלים.
3.המרצים ובמיוחד המתרגלים היו מצויינים והכינו אותנו למבחן באופן מושלם.
4.החומר היה מעניין

אנחנו לא אשמים שהכנתם אותנו טוב למבחן, האשמה היא עליכם, אולי פעם הבאה תלמדו פחות טוב.
אסור לנו לוותר
חייבים לעשות משהו עם הנירמול המוזר הזה!!!


Re: אסור לוותר
by egozie - Wednesday, 3 February 2010 21:19:45
אמת ויציב!
מועד א' של שנה שעברה היה קל בהרבה מהמבחן שלנו, ולא ראיתי שום פקטור שלילי באתר של שנה שעברה,
חבל שלא התחלתי ללמוד שנה קודם!
[-] נרמול ציונים הוגן
by caspiy - Wednesday, 3 February 2010 21:42:18

על מנת לנרמל בצורה הוגנת יש לנרמל גם את הבחנים
שם הממוצע נמוך יותר מ75 וגם להם יש משקל רב..
תתחשבו בסטודנטים ..
רובנו השקענו בקורס הזה והתוצאות מתבטאות במבחן הסופי..

במחלקות אחרות ממוצע 75 הוא שערורייה.

Re: נרמול ציונים הוגן
by olgasib - Wednesday, 3 February 2010 23:02:44
זה באמת לא פלא שהצלחנו במבחן להגיע לכאלה תוצאות.
חווות הגשת תרגילים ו-2 בחנים הכריחו אותנו להשאר בעניינים מבחינת החומר, ככה שלמבחן הסופי לא היינו צריכים ללמוד דברים מהתחלה. בעצם רק חידדנו נקודות וסגרנו פינות.
כמו כן, היה מספיק זמן ללמוד לבחינה, שלא כמו לבחנים, ולכן התוצאות בהתאם...
אז אני לא בטוחה  שאנחנו יודעים את החומר פחות טוב מסטודנטים בשנים קודמות...
Re: נרמול ציונים הוגן
by egozie - Thursday, 4 February 2010 11:19:41
אם אתם עושים נרמול ציונים, שיהיה לפחות הוגן!!!

זה נראה לכם הוגן שמי שקיבל 100 ישאר עם 100
אבל מי שקיבל 80 ירד לו ל-69?!

איך זה משקף את הידע של הסטודנט בדיוק?
איך אתם מוצאים את זה הוגן?
למה תלמידים ממוצעים צריכים להדרדר לרמת תלמידים חלשים?

אם אתם מגיעים לרמה של לנרמל למטה, אל תתנו מבחנים של 105 נקודות!
זה פוגע בנו!!!
[-] you said:"We want the grades to reflect as accurately as possible the student's knowledge in the course,"
by kaplanyo - Thursday, 4 February 2010 09:05:23

זה פשוט לא נכון.
לא יתכן שאתם מחשיבים שני בחנים ולא הופכים אותם למגן . זה הרי לא משקף באמת את הידע בסיום הקורס.
 זה משקף ידע בנקודת זמן שבה לחלק מהסטודנטים או שיש לחץ שנובע משיקולים שונים בהם גם שיקולים כלכלים או שלוקח זמן להפנים את החומר.
אם סטודנט למד באינטנסיביות לקראת המבחן המסכם ושיפר את רמת הידע שלו באופן ניכר ,הרי שזוהי רמת הידע שלו בסיום הקורס ולכן טענתכם פשוט לא נכונה
:)אינני עו"ד ולא רוצה להיות אבל ברור שלא הייתם עוברים בג"ץ עם זה.
חבל כי סך הכל אני חושב שצוות הקורס מעולה וגם פרופ' ברנד הנכבד היא דמות נערצת על ידי רבים מאיתנו.

Re: you said:"We want the grades to reflect as accurately as possible the student's knowledge in the course,"
by shayas - Thursday, 4 February 2010 11:08:51
אין לנו ועד מסודר וזה קל יותר להעביר החלטה כזו
אף אחד לא חושב שזה נעשה מתוך רוע כי בסה"כ יש לנו את הסגל הכי טוב אולי מכל הקורסים במדעי המחשב
גם מבחינת אנשים וגם מבחינת רצון לעזור
אבל יש דברים מלמעלה שקשה להתמודד איתם ואני בטוח שיש מרצים שלא מסכימים לזה ,זה צריך להיות ישירות מול אורי ומול יו"ר ועדה פקולטית ואם צריך מול כל מי שלמעלה מזה
יכול להיות שזה חוקי לעשות נירמול אבל המינימום זה להגיד את זה לפני המבחן ובתחילת הסימסטר ולעשות את זה בשווה לכל המבחנים
רק לצורך השוואה הממוצע לבוגרים במחלקה במדעי המחשב בת"א הוא מעל ל-90
אז אם שיש ממוצע 80 אצלנו במבחן ומורידים אותו בנירמול ל-75
אתם יכולים להבין מה המשמעות של זה,אתם עובדים יותר קשה ונכון להיום אין לבוגר מאב"ג יתרון ממשי ואפילו הוא מגיע במינוס שהוא מחפש עבודה,והיוקרה של ת"א לא פחות משל בן גוריון
לא הבנתי דבר אחד
by barakdav - Thursday, 4 February 2010 18:20:44
למה זה הוגן ךתת אותו ציון למי שקיבל 100 ולמי שקיבל 105???

אם אתם משקללים בצורה כזאת למה ביכלל לתת אופציה ל105?!?!
[-] CFL
by ariels - Thursday, 4 February 2010 18:54:58
Let L = {a^n : where n isn't prime}, does L belong to the CFL group?
Re: CFL
by auto101 - Wednesday, 10 February 2010 09:57:23
L is not CFL by an argument similar to the one used for a^prime.
רצינו לפתוח "דף חדש"...
by auto101 - Wednesday, 10 February 2010 09:58:29

חשבנו שיהיה יותר נוח אם נפתח פורום חדש, לבקשתכם החזרנו את הפורום הקודם.

[-] האם Lnot-reg שייכת לRE
by halabid - Thursday, 11 February 2010 10:56:57

או לאן היא שייכת ?
אם היא ניתנת לקבלה, אז מה הרעיון לכך ? מהי הסיבה ??
תודה מראש לעוזרים,
. Lnotreg = {< M >: L(M) is not regular}


Lnotreg = {< M >: L(M) is not regular}


[-] Re: האם Lnot-reg שייכת לRE
by hico - Thursday, 11 February 2010 11:56:11
Lnotreg
לא שייכת ל R
לא שייכת ל RE ,
וגם המשלימה שלה לא שייכת ל RE
היא נמצאת באותו מקום ש
LSigma*
נמצאת..

הסבר ממש מפורט יש בתרגול 13, שאלה 2

:)
Re: האם Lnot-reg שייכת לRE
by halabid - Thursday, 11 February 2010 12:31:03
thanks
[-] 2009 מועד ג
by hofitel - Thursday, 11 February 2010 23:46:44
שאלה 3
מהו הפתרון?
אם אינדוקציה אז איזו
אם אחר אז רעיון כללי בבקשה

תודה
Re: 2009 מועד ג
by gilamor - Friday, 12 February 2010 10:02:07

כבר ענינו על זה:
http://www.cs.bgu.ac.il/~auto101/Exams?action=show-thread&id=8a7405b40a2813fbda320557ecbf2c17

אינדוקציה לגמרי לא רולוונטית כאן. התכוונת לרדוקציה?

[-] CO-RE
by khmelnik - Friday, 12 February 2010 10:12:10

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

חוק דמורגן לא עובד פה :(

Re: CO-RE
by hico - Saturday, 13 February 2010 20:30:19
לפי מה שנאמר בשעות קבלה, התשובה היא כן-
כלומר, הקבוצה הנ"ל סגורה תחת אותם פעולות ש-
RE
סגורה תחתם.

אבל... הוכחה:
לא ראינו הוכחה בכיתה אפילו עבור סגירות בשרשור/*-קליני
ב- RE,
אלא רק רעיון,
אז אין לי שמץ להגיד לך מה קורה עם המשלים...
[-] שאלה 3 מועד ב 2005
by maximkir - Friday, 12 February 2010 10:54:25
הדרישה בשאלה היא לבנות אוטומט אי- דטרמיניסטי עבור
MAX(L)
מאוטומט דטרמיניסטי  עבור
L

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

ובכך עדיין לקבל אוטומט דטרמיניסטי.... כי הרי סה"כ הפכתי מצבים מקבלים למצבים לא מקבלים.

או שאלי אני מפספס משהו?
Re: שאלה 3 מועד ב 2005
by gilamor - Friday, 12 February 2010 13:48:59

אין סתירה, DFA הוא מקרה פרטי של NFA.

ייתכן שמי שכתב את השאלה חשב על פתרון נוסף אחר שבו מתקבל אוטומט שאני DFA והוא לא רצה להגביל את תשובות הסטודנטים דווקא לפתרון שלו.

[-] שאה לגבי רדוקציות
by mariasm - Friday, 12 February 2010 12:34:32
האם קימת רדוקציה בין
Lacc
ל-
Ld
?

ידוע כי שנהם לא שיכות ל R
תודה!

Re: שאה לגבי רדוקציות
by khmelnik - Friday, 12 February 2010 12:51:46
I guess no ..

Assume that there is "f" such reduction between Lacc and Ld , so "f" is also reduction from comp(Lacc) and comp(Ld) , and we know that comp(Lacc) does not belong to RE , it means that comp(Ld) doesnot bellongs to Re , and that is false !
Re/R
by khmelnik - Saturday, 13 February 2010 20:55:24
האם הקבוצה הנ"ל סגורה תחת שרשור ?
מה האינטואיציה להוכחה כאן ?

תודה מראש ..
שאלה 2 סעיף 1 מועד ב
by shmuelku - Wednesday, 17 February 2010 18:05:06

משהו הבין למה אם 2 בחזקת א זו התשובה אז כל התשובות נכונות
יכול להיות שפשוט הכוונה הייתה לקבוצת שפות כלשהיא?
כי אחרת נראה מוזר שבתשובה לשאלה כמה? יש יותר מתשובה אחת נכונה

רדוקציה
by oritka - Monday, 22 February 2010 11:36:39
רוצים לבדוק האם קיימת רדוקציה:
A<B
אם מתקימים כל 4 הטענות שהן:

. A שייך RE <- B שייךRE - ו A <B

A שייך RE <- B שייךRE - ו A <B

. AשייךR <- BשייךR - ו A <B

. B לא שייך RE <- A לא שייךRE - ו A< B

B לא שייך RE <- A לא שייךRE - ו A< B

. B לא שייך<- Aלא שייך R - ו < B

אם כל התנאים מתקימים האם ניתן להגיד שבהכרח קיימת רדוקציה כלשהי?
אם זה לא נכון אשמח לראות דוגמא נגדית