New answers tagged computation-models
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 ...
D.W.♦
- 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 ...
- 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 ...
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 ...
- 27.7k
Top 50 recent answers are included