edited by
346 views

1 Answer

Best answer
1 votes
1 votes
the answer cis right .
4th statement if a->b in polynomial time means that b complexity can't be higher than a . so if b is undecidable a will be anything lower than undecidable , so it may be decidable .

and for 2 take example . a^p where p is prime and sigma * which is regular , and now pull out intersection .
selected by

Related questions

0 votes
0 votes
1 answer
2
learncp asked Jan 26, 2016
843 views
$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$(C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$(D) $L^R$ is decidable
2 votes
2 votes
1 answer
4
aditi19 asked Mar 24, 2019
1,886 views
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything?answer is 20 o...