Recent Forum Posts
From categories:
page 1123...next »
David (guest) 12 Mar 2015 20:10
in discussion Discussions / Q&A Fall 2015 » 2009 Semester B, Moed A, part2, q1

Notice that the algorithms I mentioned above decide what we need, since one formal definition of our problem can be:
{x in Sigma* : L is regular}
(this means that we have two "not related" things in the definition of the class: some x, and some requirement on L)

by David (guest), 12 Mar 2015 20:10
David (guest) 12 Mar 2015 20:02
in discussion Discussions / Q&A Fall 2015 » 2009 Semester B, Moed A, part2, q1

Your algorithm is correct.

Please notice that given a language L, the question whether it's regular is decidable (and doesn't "loop") since one of the following decides it:
1. on input x: accept
2. on input x: reject

Yes, you DON'T need to know WHO decides it. It's sufficient that you know that there exists some such algorithm. Notice that, in contrast, for the HALTING problem, for instance, you can't list a set of algorithm that one of which decides it, for cardinality reasons (too few TMs: only Alef zero) , as seen in class.

by David (guest), 12 Mar 2015 20:02
Ido (guest) 12 Mar 2015 16:06
in discussion Discussions / Q&A Fall 2015 » 2009 Semester B, Moed A, part2, q1

I can't understand /:
I still can't find the TM that decides L2.
I tried this:

On input (<A>):
if L(Mo) regular: return L(A) == L(M) #(checking whether two DFA's languages are equal)
else : reject # (L2 is empty)

but deciding if L(M0) regular or not may loop…
If i knew what was L2 - It was easy, but i don't..

can you please write for me the TM that decides L2 ?

by Ido (guest), 12 Mar 2015 16:06

This is not how I described M'. But I think I understand:

My description of M' was: run M on w, and after M finishes, if M accepted (had an accepting branch) then M' will reject. If M rejected (no branched accepted) then M' accepts.

But we there is no way to know in polynomial time if M (a non deterministic TM) reached an accepting branch or if all its' branches reject.
Correct?

Think of $\bar{L} = Clique$.
Then, M is the simple TM that guesses a clique and accepts if it is indeed a valid clique inside the input graph G.

Assume G is a graph with a single k-clique inside.
Now, there is a single accepting branch in M on G (the one with the correct clique). But all the other branches reject.
Therefore, in M', all those rejecting branches will now accept, and therefore G is in L(M') - and, of course, not in $L = Not-Clique$.

First of all, if L(M0) is not regular, then clearly L2 is empty and decidable.
Else, L2 contains all the DFA's A, whose language is equivalent to some regular language, this is also decidable (since checking whether two DFA's languages are equal is decidable).
In any case, L2 is decidable.

Edit: Peter beat me to the answer

Since M0 is a constant, we know its' language and we know that in order for L2 not to be empty L(M0) has to be a regular language.
So, now we are left with the question if a given DFA A has the same language as L(M0), since both languages are regular we saw an algorithm to compare if they are equal or not (check that each one is a subset of the other)

If there exists a rejecting branch in M(w) [after the flipping, meaning, originally it was an accepting branch] then $w \in \bar{L}$, and $w \notin L$.
But, if all branches in M(w) accept [before flipping, they were reject branches] then $w \notin \bar{L}$ therefore $w \in L$.

Also, if $w \in L$ there can't be an accepting branch in the original M(w), meaning all branches in M(w) [the original, before flipping] reject

So, why does L(M') not equal $L$?
Maybe there is an example?

*
$\bar{L}$ - is the NP lanagauge
$L$ - is the coNP language

Thanks!

M0 = TM
L2 = {<A> | A = DFA, L(A) = L(Mo)}
Why L2 is decidable?
Can you please tell us the basic idea of it's TM?

2009 Semester B, Moed A, part2, q1 by Ido (guest), 12 Mar 2015 10:34

According to your construction -
$w \in \bar{L}$ if there is an accepting branch in M(w)
and
$w \notin \bar{L}$ if there all possible branchs in M(w) reject.

This means that $L(M')$ is actually all $w$, such that there exists a rejecting branch in M(w) [since you simply flip the answer].
This language, $L(M')$, is not equal to L.

Hi,

I have an example for why coNP is in NP (and therefore coNP=NP):
Suppose L in coNP, therefore not(L) is in NP and has a non-deterministic TM which decides it in polynomial time: M.
Let us build M' which on input x runs M, accepts if M rejects and rejects if M accepts.

I don't think that what I said is correct, but I am not sure where is the problem.

Help? :)

Question about NP and coNP by peternafpeternaf, 12 Mar 2015 09:31
Alon (guest) 11 Mar 2015 19:27
in discussion Discussions / Q&A Fall 2015 » 2009a moed a q2

I have sent you an email with the exam.

by Alon (guest), 11 Mar 2015 19:27
gal_rotemgal_rotem 11 Mar 2015 17:00
in discussion Discussions / Q&A Fall 2015 » Loop in PDA

1. We already mentioned that the way to decide a CFL is using a context free grammar, specifically, convert your PDA into a CFG in CNF.
2. We didn't really formally define what a deterministic PDA is, you may assume though that a deterministic PDA never reads epsilon from the input

by gal_rotemgal_rotem, 11 Mar 2015 17:00

Can you put a link to the relevant test ? the language $\{ 0^{n^3} | n \in N \}$ is definitely not regular

Re: 2009a moed a q2 by gal_rotemgal_rotem, 11 Mar 2015 16:56
Ido (guest) 11 Mar 2015 14:18
in discussion Discussions / Q&A Fall 2015 » Loop in PDA

Tow things I don't understand:
1. If non-deterministic PDA can loop, why we say that all CFL are decidable? If L is CFL and P is non-deterministic PDA that : L(P) = L, on sum inputs it may loop.. (no accept branch)
2. why deterministic PDA cannot loop? It can read epsilon too… for example, if state q1 read epsilon it pop epsilon and push epsilon to it self…

by Ido (guest), 11 Mar 2015 14:18
2009a moed a q2
Alon (guest) 10 Mar 2015 19:06
in discussion Discussions / Q&A Fall 2015 » 2009a moed a q2

The solution in the exam mentions that the following language is regular {0^m: there exists n in N such that m=n^3}. It seems that the pumping lemma works here. What am I missing?

Thanks.

2009a moed a q2 by Alon (guest), 10 Mar 2015 19:06
gal_rotemgal_rotem 10 Mar 2015 18:22
in discussion Discussions / Q&A Fall 2015 » All_LBA

I think it would have benefited you far more to try and solve it by your own, everything can be deduced from the relevant lecture
Anyway, all languages are in co-RE\R

by gal_rotemgal_rotem, 10 Mar 2015 18:22
Dan (guest) 09 Mar 2015 19:04
in discussion Discussions / Q&A Fall 2015 » All_LBA

I search after this information all over the lecture slides, but only found statements like EMPTY_LBA not in RE. so if you could determine for the four above languages what minimal class they belong to, it would be great..

by Dan (guest), 09 Mar 2015 19:04

No, of course a deterministic PDA cannot loop - it always reads symbols from the input, and once it's done - the computation if finished.
A non-deterministic PDA can loop however, think of the following situation:
Assume that some state q1, upon reading epsilon from the input and epsilon top of the stack, pushes 'a' to the stack and moves to state q2
Now, assume that q2, upon reading epsilon from the input, reading 'a' from top of the stack, pushes epsilon to the stack and moves back to q1,
Thus, we get an infinite loop (we never read anything from the input, and just push and pop 'a').

Re: Loop in PDA by gal_rotemgal_rotem, 09 Mar 2015 16:51
Re: All_LBA
gal_rotemgal_rotem 09 Mar 2015 16:47
in discussion Discussions / Q&A Fall 2015 » All_LBA

I'm pretty sure it's all written in the relevant lecture slides

Re: All_LBA by gal_rotemgal_rotem, 09 Mar 2015 16:47
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License