User Anwar

6 votes

Accepted

How does the 'proof' of the Cook-Levin theorem, actually prove the Cook-Levin theorem?

answered May 1, 2022 at 13:22

4 votes

Accepted

How can I show that this language is context sensitive?

answered Nov 9, 2020 at 19:53

3 votes

Accepted

$\mathrm{MON} = \{\langle M\rangle : \text{$M$ is monotone}\}$ is undecidable

answered May 1, 2022 at 8:18

3 votes

Accepted

Difficulty understanding the CANYIELD function in the Sipser text's proof of Savitch’s theorem

answered May 2, 2022 at 14:57

3 votes

Accepted

Question about stack permutations

answered May 2, 2022 at 20:02

2 votes

Enumerating through Turing Machines That Solve Same Problem

answered May 25, 2022 at 5:08

2 votes

Maximum difference between maximum and minimum frequency in a subarray

answered May 1, 2022 at 9:35

2 votes

Accepted

Proving some subsets of a regular languages to be regular languages

answered Nov 12, 2020 at 0:44

2 votes

Is the language of words having same number of a's and b's context-free?

answered Nov 8, 2020 at 17:56

1 vote

Accepted

Cardinality of formal languages

answered Nov 16, 2020 at 17:17

1 vote

Accepted

Turing machine state transition diagram vs finite state machine state transition diagram

answered Nov 19, 2020 at 2:45

1 vote

Accepted

Solving $T(n) = 16T(n/2) + n$

answered Nov 19, 2020 at 23:36

1 vote

Accepted

What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?

answered Nov 20, 2020 at 0:44

1 vote

Failing to solve a recurrence by induction

answered Nov 20, 2020 at 22:25

1 vote

Conv Net dimensions misunderstanding?

answered Nov 21, 2020 at 3:42

1 vote

How can I prove that the language is not CFL?

answered Nov 11, 2020 at 22:33

0 votes

Accepted

How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?

answered May 1, 2022 at 12:34

0 votes

How to show that language is Turing-recognizable and Turing-decidable?

answered May 1, 2022 at 14:11

0 votes

Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

answered Apr 30, 2022 at 8:03

0 votes

Regular language is closed given transposition of rightmost character to leftmost

answered Nov 20, 2020 at 23:27

0 votes

Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$

answered Nov 20, 2020 at 0:00

0 votes

Accepted

{a^n b^n c^n | n>=1} - PDA

answered Nov 17, 2020 at 2:03

0 votes

Undecidability of closure under reverse of language accepted by TM

answered Nov 8, 2020 at 19:24

0 votes

Conversion of nfa with self-loop to one without self-loop

answered Nov 9, 2020 at 15:03

0 votes

Accepted

How to check if a language is not regular?

answered Nov 8, 2020 at 13:57

0 votes

how to prove that a language is regular?

answered Nov 8, 2020 at 14:36

0 votes

Need help understanding what co-recursively enumerable means

answered Nov 8, 2020 at 15:08

0 votes

DFA to accept a String containing even number of both A and B, but rejects empty String

answered Nov 15, 2020 at 17:33

0 votes

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

answered Nov 16, 2020 at 2:42

0 votes

Accepted

Create a PDA that accepts the following language

answered Nov 11, 2020 at 21:54

Stack Exchange Network

30 Answers

How does the 'proof' of the Cook-Levin theorem, actually prove the Cook-Levin theorem?

How can I show that this language is context sensitive?

$\mathrm{MON} = \{\langle M\rangle : \text{$M$ is monotone}\}$ is undecidable

Difficulty understanding the CANYIELD function in the Sipser text's proof of Savitch’s theorem

Question about stack permutations

Enumerating through Turing Machines That Solve Same Problem

Maximum difference between maximum and minimum frequency in a subarray

Proving some subsets of a regular languages to be regular languages

Is the language of words having same number of a's and b's context-free?

Cardinality of formal languages

Turing machine state transition diagram vs finite state machine state transition diagram

Solving $T(n) = 16T(n/2) + n$

What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?

Failing to solve a recurrence by induction

Conv Net dimensions misunderstanding?

How can I prove that the language is not CFL?

How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?

How to show that language is Turing-recognizable and Turing-decidable?

Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

Regular language is closed given transposition of rightmost character to leftmost

Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$

{a^n b^n c^n | n>=1} - PDA

Undecidability of closure under reverse of language accepted by TM

Conversion of nfa with self-loop to one without self-loop

How to check if a language is not regular?

how to prove that a language is regular?

Need help understanding what co-recursively enumerable means

DFA to accept a String containing even number of both A and B, but rejects empty String

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Create a PDA that accepts the following language