User ttnick

9 votes

Accepted

Do Turing machines have memory registers?

answered Sep 28, 2021 at 9:48

7 votes

Length of a regular expression

answered May 17, 2022 at 17:30

5 votes

Understanding Time Complexity

answered Jun 26, 2021 at 8:05

5 votes

Accepted

Ω(f(x)) and worst case analysis

answered Jan 19, 2021 at 10:47

4 votes

Are Linear Bounded Automatons Turing Complete?

answered Jun 20, 2019 at 5:58

4 votes

Accepted

Assumption: A PSPACE-hard problem can be solved in polynomial time

answered Jun 8, 2018 at 13:43

4 votes

Accepted

Using Myhill-Nerode to prove that language is not regular

answered Mar 23, 2018 at 14:46

4 votes

Accepted

Is there such data type for low range float?

answered Dec 3 at 10:48

3 votes

Accepted

Is "imperative computing" just a fancy way of saying "scripting"? Or is there more to it?

answered Jan 18, 2020 at 19:13

3 votes

Accepted

Where is the second face in a graph with 3 nodes?

answered Apr 5, 2018 at 18:43

3 votes

Are the implications of the diagonalization language different from those of the halting problem?

answered May 15, 2018 at 5:59

3 votes

Accepted

Do the classes $P$ and $NP$ include problems faster then polynomial?

answered May 15, 2018 at 6:05

3 votes

Accepted

The set of all eventually periodic words is not Buchi Recognizable?

answered Feb 26, 2018 at 10:44

3 votes

DFA for Strings with third symbol from RHS as 1

answered Mar 11, 2018 at 17:11

3 votes

Fantasy premier league dream team algorithm?

answered Jul 15, 2018 at 14:40

3 votes

Accepted

Decidability of a set containing first symbols of elements of a decidable set

answered Jul 16, 2018 at 5:56

3 votes

Prove no DFA with four states can accept L={111}

answered Mar 4, 2021 at 20:56

2 votes

Accepted

A task-scheduling problem as a matroid (CLRS book)

answered Apr 21, 2021 at 22:02

2 votes

Proof that R (decidable languages) is not closed under homomorphism

answered Jun 2, 2021 at 9:13

2 votes

Simple path in a Finite Acceptor

answered Jun 24, 2018 at 17:32

2 votes

Both a language and its complement are not context free

answered Jul 2, 2018 at 13:28

2 votes

How to calculate machine epsilon

answered Jul 8, 2018 at 16:28

2 votes

Accepted

Show that the regular language is contained in another

answered Mar 12, 2018 at 9:52

2 votes

Accepted

How does this reduction to prove undecidability account for epsilon?

answered Feb 26, 2018 at 11:15

2 votes

Accepted

Making a CFG for a^i b^j c^k such that i+j = 3k

answered May 15, 2018 at 20:16

2 votes

Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}

answered May 21, 2018 at 20:06

2 votes

Accepted

Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)

answered Mar 24, 2018 at 11:56

2 votes

Accepted

Problem with forming a context-free grammar describing a language

answered Mar 29, 2018 at 10:38

2 votes

Accepted

prove A is co-re

answered Mar 31, 2018 at 21:05

2 votes

Accepted

How to check $L$ is regular or not

answered Jul 2, 2021 at 6:56

Stack Exchange Network

57 Answers

Do Turing machines have memory registers?

Length of a regular expression

Understanding Time Complexity

Ω(f(x)) and worst case analysis

Are Linear Bounded Automatons Turing Complete?

Assumption: A PSPACE-hard problem can be solved in polynomial time

Using Myhill-Nerode to prove that language is not regular

Is there such data type for low range float?

Is "imperative computing" just a fancy way of saying "scripting"? Or is there more to it?

Where is the second face in a graph with 3 nodes?

Are the implications of the diagonalization language different from those of the halting problem?

Do the classes $P$ and $NP$ include problems faster then polynomial?

The set of all eventually periodic words is not Buchi Recognizable?

DFA for Strings with third symbol from RHS as 1

Fantasy premier league dream team algorithm?

Decidability of a set containing first symbols of elements of a decidable set

Prove no DFA with four states can accept L={111}

A task-scheduling problem as a matroid (CLRS book)

Proof that R (decidable languages) is not closed under homomorphism

Simple path in a Finite Acceptor

Both a language and its complement are not context free

How to calculate machine epsilon

Show that the regular language is contained in another

How does this reduction to prove undecidability account for epsilon?

Making a CFG for a^i b^j c^k such that i+j = 3k

Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}

Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)

Problem with forming a context-free grammar describing a language

prove A is co-re

How to check $L$ is regular or not