Recent Forum Posts
From categories:
page »

Regarding Q2a in MoedA: Those of you who wrote that we proved in class that AllCFG is not in RE and lost 1-2 points due to that (and not due to other claims) can submit an appeal to bring these points back. Please make sure to submit them on time.

Have a nice weekend.

Q2a in MoedA by Dean DoronDean Doron, 20 Jul 2017 10:12

Hi all,

The MoedA grades are published.
Exam grades in the range 55-59 became 60. You needed to pass the exam in order for the HW and midterm to affect the grade.

For those of you who got HW exempts - disregard the Moodle average, it does not take it into account but we did.

Grades published by Dean DoronDean Doron, 18 Jul 2017 21:13

The solution is published in the exams section.

Best of luck.

MoedA Solution by Dean DoronDean Doron, 04 Jul 2017 15:04
HW6 Q3
YuvalWYuvalW 04 Jul 2017 09:40
in discussion Discussions / Q&A Spring 2017 » HW6 Q3

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

HW6 Q3 by YuvalWYuvalW, 04 Jul 2017 09:40

you are right there are n!/(n-5)!5! options which is O(n5)…

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

Re: עצירה by amosengelamosengel, 03 Jul 2017 14:27

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

במקרה זה נגיע למצב בו הראש רואה רווח למשך |Q|+1 צעדים ואז נקבל

Re: 2012 SEM B MOED A Q.5 by dafnasadehdafnasadeh, 03 Jul 2017 13:20

The question:

A CFG is symmetric if for any rule A->w we have w=w^R.
It says the solution is: every symmetric CFG creates a symmetric language. What about this refuting example then:

A-> 010 | AB
B -> 0

It generates A->0100 which is clearly not symmetric, but every rule of form A->w is symmetric.

Also - an unrelated general question - if a question doesn't specifically state whether a TM is deterministic or not, but it mentions something about run-time (polynomial) - should we assume it's a deterministic TM?


צודק. תודה!

A TM halts when it reaches $q_a$ or $q_r$.

Re: עצירה by Yuval MoskovitchYuval Moskovitch, 03 Jul 2017 10:17

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

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

Mw will not be in L' in the situation you described.
Membership in L' implies that for all x with |x| > 2, M(x) runs for the specified number of steps.
But if |x| is bigger than the number of steps that Mw performs until M stops on w (and there is such x, because that number is finite),
then Mw will enter an infinite loop, thus running more than 4*|x|2 steps.
In that case, we will get that Mw is not in L'.

Re: 2016 SemB MoedeA Q4b by Daniel JerafiDaniel Jerafi, 03 Jul 2017 09:04
amosengelamosengel 03 Jul 2017 08:52
in discussion Discussions / Q&A Spring 2017 » עצירה

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

עצירה by amosengelamosengel, 03 Jul 2017 08:52

I'm still not convinced. The number of times you check if there's an IS in size of n\2 is limited as you said.
But there are
options for possible subsets(possible clicks) and that depends on n obviously.
So it's not deterministic in poly time, as I understand.
Can someone please explain this to me?

You question is not clear. If P=NP then any polynomial-time reduction (let alone mapping reduction) can use a polynomial-time algorithm that solves SAT,
but then if P=NP there is no much use in polynomial-time reductions. If you are given that P=NP, then there exists such an algorithm, obviously it is not constructive.

page »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License