User Bader Abu Radi

11 votes

Accepted

Does there exist a unique minimal DFA with more than one start state?

answered Nov 16 at 19:37

10 votes

Accepted

Why is this automaton considered DFA?

answered Dec 26, 2020 at 23:49

7 votes

Accepted

What role does the lower bound play in the statement of Savitch's Theorem?

answered Aug 15 at 12:24

6 votes

I'm trying to understand why every language has an infinite number of TMs that accept it

answered Jan 1, 2021 at 20:37

6 votes

How to prove the class of regular languages is closed under 3MAJ?

answered Feb 22, 2021 at 15:54

5 votes

What is the complexity for the universality problem for a NFA with all states accepting?

answered Aug 22, 2022 at 12:27

5 votes

Language Containment of Automata

answered Dec 16, 2020 at 11:19

5 votes

Accepted

Relative running times of equivalent Turing machines with arbitrary and binary alphabets

answered Aug 2 at 9:58

5 votes

The SAT problem can be reduced to the complement of the halting problem?

answered Jan 28 at 20:52

5 votes

Notation in NFA, DFA diagrams and language

answered Feb 15 at 13:06

5 votes

How to determine if a set is countable or uncountable?

answered Aug 23 at 13:53

4 votes

Accepted

$L'=\left \{ z^Rx : xyz\in L \right \}$ is regular

answered Aug 25 at 19:10

4 votes

Accepted

Difference between product automaton vs. NFA with epsilon transitions

answered Feb 16 at 19:20

4 votes

Optimal upper bound on the number of states in the complement of an NFA

answered Jan 11 at 23:22

4 votes

Accepted

$L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

answered Aug 2 at 19:52

4 votes

Naming Turing machines paired with input

answered Jul 8 at 15:48

3 votes

Accepted

Prove that $n$ is a time-constructible function

answered Jul 15 at 18:04

3 votes

Accepted

Proving Rice's theorem extension

answered Jul 22 at 12:51

3 votes

A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

answered Jul 31 at 16:29

3 votes

Accepted

A question about the number of states of a Turing machine using the alphabet $\{ 0, 1, \square, \rhd \}$

answered Aug 10 at 13:04

3 votes

Accepted

The number of triple intersections of lines

answered Aug 20 at 18:09

3 votes

Accepted

result of a union between a decidable language and not recognizable one - disjoint

answered Aug 21 at 18:42

3 votes

Accepted

Reduction from dominating set to disconnected dominating set

answered Jan 11 at 23:53

3 votes

Accepted

what is the smallest 3-CNF possible that enforces the boolean expression: a = b + c?

answered Jan 13 at 11:05

3 votes

Is 2-coloring in NL or L?

answered Jan 22 at 18:53

3 votes

Accepted

Easy proof of IP ⊆ PSPACE for private coins

answered Jan 23 at 19:03

3 votes

Accepted

Time complexity of specific variant of Turing Machine

answered Feb 16 at 12:21

3 votes

Pumping lemma: why x in ∣xy∣ ≤ p?

answered Jan 4, 2021 at 9:42

3 votes

Accepted

Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton

answered Dec 29, 2020 at 22:42

3 votes

Question about ALL-NFA in PSPACE

answered Jan 2 at 7:29

Stack Exchange Network

165 Answers

Does there exist a unique minimal DFA with more than one start state?

Why is this automaton considered DFA?

What role does the lower bound play in the statement of Savitch's Theorem?

I'm trying to understand why every language has an infinite number of TMs that accept it

How to prove the class of regular languages is closed under 3MAJ?

What is the complexity for the universality problem for a NFA with all states accepting?

Language Containment of Automata

Relative running times of equivalent Turing machines with arbitrary and binary alphabets

The SAT problem can be reduced to the complement of the halting problem?

Notation in NFA, DFA diagrams and language

How to determine if a set is countable or uncountable?

$L'=\left \{ z^Rx : xyz\in L \right \}$ is regular

Difference between product automaton vs. NFA with epsilon transitions

Optimal upper bound on the number of states in the complement of an NFA

$L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

Naming Turing machines paired with input

Prove that $n$ is a time-constructible function

Proving Rice's theorem extension

A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

A question about the number of states of a Turing machine using the alphabet $\{ 0, 1, \square, \rhd \}$

The number of triple intersections of lines

result of a union between a decidable language and not recognizable one - disjoint

Reduction from dominating set to disconnected dominating set

what is the smallest 3-CNF possible that enforces the boolean expression: a = b + c?

Is 2-coloring in NL or L?

Easy proof of IP ⊆ PSPACE for private coins

Time complexity of specific variant of Turing Machine

Pumping lemma: why x in ∣xy∣ ≤ p?

Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton

Question about ALL-NFA in PSPACE