Recent Forum Posts
From categories:
page »

Hi all,

Just a clarification - 10 points were added to the raw grade of MoedB, and then the calculation
was similar to MoedA.
That is, you could have failed the exam itself prior to the factor but still pass the course.

MoedB grade calculation by Dean DoronDean Doron, 10 Sep 2017 08:42

Hi all,

MoedB and its solution were uploaded to the Exam section.

MoedB solutions by Dean DoronDean Doron, 13 Aug 2017 17:54

in general, when we need to prove that a specific language is in co-re, should we prefere:
1. to use a verifier for NOT(L)
2. to build a TM that accepting NOT(L)?

-You should explain how to "derive from G1 words of length n".
-To check if a word w generated by G2 you should use the Derive algorithm.
-You can't stop at 2^pumpingLength (if it was true you just built a decider).
"Repeat the process switching the roles of G1 and G2 (G2 in CNF and PDA for G1)" - the two process should be done alternately.

For every T.M M exists x and y s.t $<M,x,y>\in L$.
Thus the decider should just check: "is M is a T.M?".

By definition- M accepts L(M).

Re: 2015 Moed B - Q5a by dafnasadehdafnasadeh, 08 Aug 2017 11:50

לא. כי יכול להיות שהשפה של המכונה המקורית לא ריקה אבל מקבלת קלט כלשהו אחרי יותר מ-2011^n צעדים.
במקרה כזה המכונה המקורית לא תהיה ב-EMPTY_TM אבל החדשה כן תיהיה ב-L.

הפתרון צריך להיות מוגדר כך:
ואז מקבלים כי $K_U(S_n)\geq n$ מהגדרת השפה.
כי $S_n$ היא מילה מתוך UC.

By definition - any language generated by a context-free grammar is a context-free language. For a formal proof, you need to prove that language generated by the context-free grammar is equal to the given language. In this specific question, they didn't ask for this proof.

1. The question is about DFA not NFA - how this NFA will help you? you should create automata s.t every accepting state is "a hole".
2. No. The claim is that "the hole languages" aren't closed under reverse, not that regular languages aren't closed under reverse.

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

Re: 2008 moed a sem a by al123al123, 08 Aug 2017 10:30

K(x) is simply an abbreviation of K_U(x), so the constant c is actually c_U. However, we can always use the same U so you can consider c as a global constant.

Re: kolmogorov complexity by Dean DoronDean Doron, 07 Aug 2017 23:01

We claimed that for every string x:

\begin{align} K_{U}(x)\leq K_{M}(x) + c_{M} \end{align}

But in lecture 10 slide 15 we want to prove that

\begin{align} K(x)\leq |x| + c \end{align}

So we use TM M that computes the identity, but suddenly the constant c loses the dependency in the TM M. Can you please explain why it is valid and is the constant c really not dependent in any TM?

kolmogorov complexity by yonatan vaineryonatan vainer, 07 Aug 2017 11:33

The solution shows a proof using a verifier. Would it also be possible to use the following proof (a TM that accepts the complement language)?

Convert G1 to CNF and G2 to PDA.
Derive from G1 words of length 1 and check if they are accepted by G2, continue this for lengths 2,.., until 2*pumpingLength. If at any point the PDA rejects - then accept.
Repeat the process switching the roles of G1 and G2 (G2 in CNF and PDA for G1).

The question : imgur dot com/aSPfp0r

Why is this in P? Isn't it possible that there are no x,y which are accepted and then the TM for L runs forever without halting?
That is, L isn't necessarily final.


imgur dot com/cHxJhyX

Why is it that for every TM encoding <M>, L(M) is in RE?


2015 Moed B - Q5a by JonathanG91JonathanG91, 06 Aug 2017 16:06

Rice is not applicable here. There can be two TMs M1 and M2, one which halts and one which doesn't, but L(M1)=L(M2).
Also, this language can be finite and every finite language is in R.

Re: 2008 moed a sem a by Gilad ApelsteinGilad Apelstein, 06 Aug 2017 12:23

נתון: L שפה אינסופית המכילה רק קידודים סטנדרטיים של מ"ט שעוצרות על כל הקלטים. בתשובות מסומן שייתכנו שתי אפשרויות: ייתכן ש-L כריעה וייתכן ש-L כריעה למחצה ולא כריעה. למה זה נכון? זה לא בהכרח מתקיים ש-L לא כריעה בגלל משפט Rice? (הרי לפי הגדרת L נראה שכל מ"ט שלה הן בעלות L(M) ב-R וזו תת-קבוצה של RE).


אסמן ב-L את השפה המכילה את כל קידודי מ"ט שהן אקספוננציאליות והמקבלות את השפה הריקה.
האם גם רדוקציה מ- EMPTY_TM ל- L תעבוד במקרה זה? (בלי קשר ל- LBA)

הרדוקציה: לכל מ"ט ב- EMPTY_TM נבנה מ"ט המסמלצת את המכונה המקורית, עד 2011 בחזקת n. אם המכונה לא עצרה עד אז, נדחה

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