Recent Forum Posts
From categories:
page 1123...next »

האם לדוגמא כאשר ציון הבחינה הוא 88.5 אז בחישוב שלכם עם ממוצע שיעורי הבית הוא נחשב כ88 או 89?
כנ"ל לגבי ממוצע שיעורי הבית, אם לדוגמא ציון הממוצע ב5 תרגילי הבית הטובים ביותר הוא 98 אזי כאשר מחשיבים 10 אחוז מתוך זה על מנת לשקלל את הציון הסופי אז 9.8 נלקח בתור 10 נקודות או 9 נקודות?
באופן כללי האם מעגלים כלפי מעלה?

Hello,

The scanning of Moed B are up, and the grades are expected soon.
The solution for the exam was also uploaded. Before you consider an appeal, please read it.
Also, appeals in the nature of "I know that my answer is not 100%, but I think you deduced more points that you should have" will
not be considered, and can only lower you grade.

Take care.

Moed B grades and solution by Dean DoronDean Doron, 15 Aug 2016 09:27

They will be delivered to the secretariat tomorrow morning.

Re: ציונים by Dean DoronDean Doron, 14 Aug 2016 14:30
ציונים
Student (guest) 14 Aug 2016 12:31
in discussion Discussions / Q&A Spring 2016 » ציונים

?מתי יתפרסמו הציונים למועד ב

ציונים by Student (guest), 14 Aug 2016 12:31

Hello,

A deterministic PDA (as was also defined in the lecture notes) is characterized by the fact that for every word there is a single computation path from the initial configuration.
One can then show that this property implies the fact that detCFL is closed under complement. Thus, if L was in detCFL then L-bar would also be in
detCFL, contradicting the fact that L-bar itself is not context-free at all.

However, the way that we re-defined it in the test today was flawed. As defined, it does not put restrictions on tuples that contain
epsilon, so the above property no longer holds. Nonetheless, if we forbid "reading epsilons" from the stack, obviously we cannot do anything
so detCFL consists only of the trivial languages.

And now for the practical part - the points for this sub-question will be given to all of you. Those who gave intelligible answers that addressed these issues will
be given a modest bonus.

Take care.

Question 2B of Moed B by Dean DoronDean Doron, 31 Jul 2016 12:22
sapir (guest) 29 Jul 2016 17:29
in discussion Discussions / Q&A Spring 2016 » שאלה 4ב מהבוחן הסמסטר

"and you can always add dummy states to get to 100." - Thanks! That's what I was missing

by sapir (guest), 29 Jul 2016 17:29

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

שפות חסרות הקשר - חלוקה משמאל by student (guest), 29 Jul 2016 13:31

If you start with an NFA with 6 states and construct the division automaton,
it becomes an *NFA* with 6 states. Every NFA with q states has an equivalent
DFA with 2^q states. So, L1/L2 has a DFA with 64 states, and you can always add
dummy states to get to 100.

by Dean DoronDean Doron, 29 Jul 2016 09:58

?

by student (guest), 29 Jul 2016 07:03
Q4 from moed a
Arik (guest) 28 Jul 2016 19:57
in discussion Discussions / Q&A Spring 2016 » Q4 from moed a

Hi, I wanted to ask a few questions related to question 4 in moed A
I've seen a convincing reduction that got all the points.
From HALT -the reduction outputs a TM M' that on X :
runs M on w x^2 steps. If M halts than M' enters an Infinite an infinite loop. If M doesn't halt than M' accepts.

Obviously something must be false with this reduction because it implies HALT is decidable. (Because the language is actually decidable)
My question is what is wrong with this reduction?

Another question is what is actually the definition of a step?
Suppose a TM during its run uses a computable function , do I need to consider the number of steps that function takes in computing something, or using that function equals 'one step'?
And when saying things like "M' runs M on w for x^2 steps", does that imply that M' runs actually in x^2 steps + the number of steps it takes to calculate x^2?

Thanks , Arik

Q4 from moed a by Arik (guest), 28 Jul 2016 19:57
2016ab q.4b
stud (guest) 28 Jul 2016 19:07
in discussion Discussions / Q&A Spring 2016 » 2016ab q.4b

g(L) = { x | x ∈ L and ∃y ∈ L such that |y| < |x|}

צריך להוכיח שאם L שייכת לRE אז גם g של L שייכת לRE.
בתשובות הפתרון הוא -
לבדוק אם x שייך לL באמצעות מ"ט שמקבלת את L.
אם כן, לסמלץ באופן סימולטני את אותה המ"ט על כל הקלטים שאורכם קטן מהאורך של x ואם אחד מהם התקבל, לקבל.
אי אפשר במקום השלב השני פשוט לשמור בהגדרת המכונה את אורך המילה הקצרה ביותר ששייכת לL?
(זה פתרון שהרבה יותר דומה לפתרון של סעיף אחר של השאלה, ולכן מוזר לי שלא השתמשו בו, ולכן אשמח לוודא שהוא בכלל נכון)

2016ab q.4b by stud (guest), 28 Jul 2016 19:07
remembering configurations
student (guest) 28 Jul 2016 18:02
in discussion Discussions / Q&A Spring 2016 » remembering configurations

hi,

1.can i remember my configurations which i have visited until now?

i mean history of all my visited configurations?

2. is this sentence only in one direction: "M visited a configuration twice -> m loops forever"

what i mean is that a TM can loop forever without visiting a configuration twice right?

thanks.

remembering configurations by student (guest), 28 Jul 2016 18:02
2011 b moed a, question 1.b
Daniel Volovik (guest) 28 Jul 2016 13:56
in discussion Discussions / Q&A Spring 2016 » 2011 b moed a, question 1.b

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

2011 b moed a, question 1.b by Daniel Volovik (guest), 28 Jul 2016 13:56
פארס (guest) 28 Jul 2016 13:30
in discussion Discussions / Q&A Spring 2016 » מבחן 2015 ab

אשמח לתגובה

by פארס (guest), 28 Jul 2016 13:30

Reduction from 4CNF to SET-SPLIT

Why is the reduction in the solution correct?

Exam 15/7/2012 Question 1(Open question) by student (guest), 28 Jul 2016 10:16
Co-NPC
student (guest) 28 Jul 2016 07:50
in discussion Discussions / Q&A Spring 2016 » Co-NPC

האם שאלות להוכחה ששפה ב CO_NPC בחומר שלנו?

Co-NPC by student (guest), 28 Jul 2016 07:50
sapir (guest) 27 Jul 2016 21:03
in discussion Discussions / Q&A Spring 2016 » שאלה 4ב מהבוחן הסמסטר

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

או שלא הבנתי נכון את השלילה…

by sapir (guest), 27 Jul 2016 21:03
sapir (guest) 27 Jul 2016 21:01
in discussion Discussions / Q&A Spring 2016 » שאלה 4ב מהבוחן הסמסטר

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

או שלא הבנתי נכון את השלילה…

by sapir (guest), 27 Jul 2016 21:01
sapir (guest) 27 Jul 2016 20:55
in discussion Discussions / Q&A Spring 2016 » חלוקה מימין

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

by sapir (guest), 27 Jul 2016 20:55

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

by student (guest), 27 Jul 2016 19:36
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License