Denis's user avatar
Denis's user avatar
Denis's user avatar
Denis
  • Member for 11 years, 1 month
  • Last seen more than a week ago
8 votes
Accepted

Closure of CFL against right-quotient with regular languages

8 votes

A quine in pure lambda calculus

7 votes
Accepted

Context-free language and regular expressions

7 votes
Accepted

Decidability of fullness of intersection of a CSL with a regular language

7 votes
Accepted

If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

4 votes
Accepted

Why have additional symbols on a Turing machine?

4 votes
Accepted

Deterministic Turing Machine with infine tape in both directions

4 votes
Accepted

Is the language of all ucv with u ≠ v context-free?

4 votes
Accepted

Assuming NP $\neq$ P, are there NPI languages only P languages reduce to?

4 votes
Accepted

Finding an Uncomputable Function

4 votes

Prove that the language is not regular without using Pumping Lemma

3 votes

Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable?

3 votes

How do I use the Myhill-Nerode theorem to show that a language is not regular?

3 votes
Accepted

Unambiguity of Reverse Polish Notation

2 votes
Accepted

Exponential reduction vs Polynomial Reduction

2 votes

Decide if L is regular or not and argue it. Trying to use Pumping Lemma

2 votes
Accepted

Deciding the class of certain languages

2 votes
Accepted

Quasigroups, congruences and recognizable subsets

2 votes

Why is the node with the greatest DFS post-order number not necessarily a sink?

2 votes

Why can't we flip the answer of a NDTM efficiently?

2 votes
Accepted

Three languages and how to decide if they are regular

2 votes

Can a language have $\Sigma^{*}$ as its syntactic monoid?

2 votes

Prove the halting problem is undecidable using Rice's theorem

1 vote
Accepted

How can time complexities be elements of others?

1 vote
Accepted

regular expression: sum of positive fixed point decimal numbers

1 vote

In a BOINC project, how are responses checked for accuracy?

1 vote
Accepted

Reducing 3CNF to Clique: Why do we omit negated literals?

1 vote

Looking for a contex-free grammar for the following language

1 vote

Why is ww a linear indexed language while www is not?

1 vote
Accepted

Constructing Context Free Grammar