user avatar
user avatar
user avatar
Elimination
  • Member for 7 years, 2 months
  • Last seen more than a month ago
4 votes
3 answers
3k views

Show that regular languages are closed under Mix operations

2 votes
1 answer
2k views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

2 votes
4 answers
2k views

Reduction and decidability

1 vote
1 answer
163 views

Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$?

1 vote
2 answers
215 views

Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

1 vote
1 answer
1k views

Do problems in P only reduce to NP and coNP problems?

1 vote
2 answers
148 views

$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?

1 vote
2 answers
268 views

Is an infinite language of halting TM is in $RE$? in $RE \setminus R$?

1 vote
1 answer
136 views

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

0 votes
1 answer
193 views

Proving that a set of grammars for a given finite language is decidable [duplicate]

0 votes
1 answer
51 views

Validating authenticity of a file

0 votes
0 answers
84 views

Gas Station problem proof

0 votes
1 answer
540 views

What is the minimal number of states for the DFA?

0 votes
1 answer
92 views

Determine if the language is $R$

-1 votes
1 answer
213 views

union of two equivalence classes (Myhill–Nerode theorem) [closed]

-1 votes
1 answer
372 views

Proving a language isn't regular using the pumping lemma [closed]

-1 votes
1 answer
531 views

Why is it true that $NP \ne coNP \implies X = \emptyset$?

-2 votes
1 answer
62 views

Prove/ Disprove: For every nontrivial $A,B \in R (RE)$, $A\le_m B$ [closed]

-2 votes
1 answer
88 views

What is the minimal states for the language DFA?