Skip to main content
user326210's user avatar
user326210's user avatar
user326210's user avatar
user326210
  • Member for 6 years, 1 month
  • Last seen this week
9 votes
Accepted

How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$

2 votes

Prove that "If $L$ is a context-free language, is $\overline{L}$ also context-free?" is undecidable

2 votes

Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

2 votes
Accepted

Understanding context free grammars in conjunction with PDA

2 votes

Can a Turing machine determine if a set is accepted by a another Turing machine?

2 votes

Is the leapfrog automata problem in P?

1 vote

A turing machine L takes a machine <M> which has to halt at for least n Inputs

1 vote

TM to detect repeats of any other TM and input value

1 vote

Determine if a language is decidable

1 vote

Non recursively enumerable language proof by reduction to non-HP

1 vote

Undecidability of language involving two TMs

1 vote

Undecidability of TMs recognizing a decidable language

1 vote

reduction from ALLTM to ETM

1 vote
Accepted

Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?

1 vote

Build a 2-PDA for language accepted by Turing Machine

0 votes

ETM Undecidability

0 votes

How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

0 votes

Can a non-recognisable language have a recognisable subset?