Recent Forum Posts
 From categories: All categories News: Course News 2015 Discussions: Q&A Fall 2015
page 1123...next »

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)

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.

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 ?

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?

$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? :)

I have sent you an email with the exam.

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

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

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…

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.

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

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..

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').

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

page 1123...next »