For an NFA, can we always find a RAM?
Domanda
For an NFA, can we always find a RAM, which recognises the same language?
Soluzione
If RAM is a Random Access Machine (i.e., a rudimentary computer with registers, memory and assorted instructions), the answer is just "build a DFA that recognizes the same language, simulate that DFA in code". I.e., have a transition table that tells you the next state for each combination of state and input symbol; start in the start state, check if the state after consuming all input is final.
More abstractly: RAM is equivalent in computing power to a Turing machine. As regular languages are decidable, they can be decided by a (deterministic) Turing machine or a RAM.
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange