User Frank

3 votes

1 answer

490 views

If $A$ is context-free then $A^*$ is regular

asked Jul 22, 2020 at 9:04

1 vote

1 answer

627 views

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

asked Jul 25, 2020 at 15:45

1 vote

1 answer

64 views

CFG for a given languague

asked May 23, 2020 at 12:02

1 vote

2 answers

299 views

Solving T(n) = 2*T(n-1)+4 witht the Master Theorem

asked Nov 29, 2020 at 15:02

1 vote

1 answer

50 views

Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$

asked Nov 29, 2020 at 16:44

0 votes

2 answers

247 views

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

asked Nov 29, 2020 at 18:43

0 votes

2 answers

76 views

Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

asked Dec 2, 2020 at 14:32

0 votes

1 answer

210 views

Is the languague L={<M>, M accepts a finite amount of words} decdidable?

asked Jul 17, 2020 at 10:08

0 votes

2 answers

77 views

Equivalence between a TM and a changing TM

asked Jun 13, 2020 at 13:10

0 votes

0 answers

43 views

$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$

asked Jul 25, 2020 at 17:27

0 votes

0 answers

50 views

Is a or free SAT formula NP complete?

asked Jul 26, 2020 at 10:32

0 votes

2 answers

642 views

Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular

asked Jul 23, 2020 at 14:59

-1 votes

1 answer

18 views

Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?

asked Jun 27, 2020 at 12:42

-1 votes

1 answer

26 views

Determine if the following problem is decidable or not : Does the read–write head of a TM with the input w leave the word w?

asked Jun 27, 2020 at 13:33

-2 votes

1 answer

515 views

Grammar with a long derivation generates an infinite language

asked May 23, 2020 at 13:22

Stack Exchange Network

15 Questions

If $A$ is context-free then $A^*$ is regular

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

CFG for a given languague

Solving T(n) = 2*T(n-1)+4 witht the Master Theorem

Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

Is the languague L={<M>, M accepts a finite amount of words} decdidable?

Equivalence between a TM and a changing TM

$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$

Is a or free SAT formula NP complete?

Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular

Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?

Determine if the following problem is decidable or not : Does the read–write head of a TM with the input w leave the word w?

Grammar with a long derivation generates an infinite language