Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel
  • Member for 5 years, 11 months
  • Last seen this week
  • Paris, France
2 votes

Why there can't be two instances of a "reverse" program in the Halting problem?

0 votes

How is $\{a^m b^n c^p d^q \mid m*n=p+q\}$ context sensitive?

2 votes
Accepted

Is { a^nb^na^n} a context-sensitive language?

0 votes

Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$

0 votes
Accepted

AVL tree with balance factor equal to depth

5 votes
Accepted

When converting a epsilon NFA to NFA to DFA, how to handle the start state?

1 vote

Prove if $A,B$ are NP-complete then $((a, b) \mid a \in A \lor b \in B)$ is also NP complete

16 votes

False proofs that look correct

0 votes

Prove (p → ¬q) is equivalent to ¬(p ∧ q)

1 vote
Accepted

L = {⟨M⟩ : there does not exist w ∈$Σ^*$ such that M rejects w } is in coRE?

0 votes
Accepted

NP-completeness of graph problem

0 votes
Accepted

Markov algorithm for words of the form $ww$, $w\in \{a,b\}^*$

4 votes

Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

2 votes
Accepted

Designing a DFA with nth character condition for any integer n

1 vote
Accepted

Proving $L=\{wvw|v\in \{0,1\}^*, w\in \{0,1\}^+\}$ is not regular using the myhill-nerode and pumping lemma

15 votes
Accepted

Can we transfer every DFA to DFAs with start state having no in edge?

0 votes
Accepted

Why is this proof that CHESS is in EXPTIME correct?

1 vote
Accepted

If P=NP then all languages in P are NP-complete?

1 vote

Time complexity of T(n) = 1600T(n/4) + n!

0 votes

Question about $L$ = { $ww$ | $w$ ∊ $ca^*c$}

2 votes
Accepted

What is the right name for a "map" data structure?

2 votes
Accepted

Every DFA accepting a finite language must contain a dead state?

2 votes
Accepted

Is the bubble sort algorithm more efficient for sorting and how to implement it?

22 votes
Accepted

Does an algorithm's space complexity include input?

1 vote
Accepted

Generate a minimum number of clauses in 3-CNF form that give a unique solution

1 vote
Accepted

Dropping terms in proving the runtime for a recurrence?

1 vote
Accepted

In Context free languages, is it okay to substitute multiple same variables at the same time?

2 votes

What is the lower bound of n factorial

1 vote

How can dfa have more than one sink state? Isn’t it the same state?

1 vote

Generate a minimum number of clauses in 3-CNF form that give a unique solution

1
2 3 4 5
15