New answers tagged

1 vote

Transition System vs State Machines

From each DFA or NFA, you can obtain a labelled transition system, by ignoring which states are the initial or final states. If you have a labelled transition system with a finite set of states and a ...
user avatar
  • 143k
1 vote

If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?

It cannot be true simultaneously that A is undecidable, A can be reduced to B, and B is decidable. Assume there are three "proofs" for each of these three facts, then at least one of the ...
user avatar
  • 25.5k
0 votes

If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?

Discovering that $B$ is decidable may mean one of two things: There is an error somewhere: either in the proof of decidability of $B$, or in the proof of undecidability of $A$, or in the reduction ...
user avatar
0 votes
Accepted

Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous

Sometimes explicit induction can be avoided by using contradiction. Assume there is a smallest pair of different derivation(trees) that derive the same string. Since the pair is different, we can also ...
user avatar
  • 27.7k

Top 50 recent answers are included