principleMinor
Flowcharts vs DFA resp FSM equivalency
Viewed 0 times
dfaflowchartsrespfsmequivalency
Problem
First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I am a bit confused about this. There are classes where using logical synthesis, Karunaugh maps, state encodings, flip flops etc. one is able to construct hardware consisting of logic gates and flip-flops which realizes the desired DFA. Basically all processes that runs on the computer (no matter if is written in C# or Assembler), are at the lowest level realized through logical gates, zeros and ones. So it seems that programs firstly needs to be converted (by compiler I suppose) to some form as I've described. This might imply that every problem that is solvable using C# is solvable using FSM. But this is in contradiction to Chomsky hierarchy and all this theory related stuff, which says that you cannot do the same magic with regular expressions (which are based on FSM) that you can do on Turing machine (which is equivalent of any programming language, if I am wrong correct me please). Moreover, if flowcharts (or even C#, Java ... source codes) were equivalent to FSM why we do not have all software formally verified so far? There is mathematical apparatus for FSM and related stuff, so why do not formally verify everything and ensure the correctness? What I am missing here?
Solution
Converted comments to answer.
FSM is an ambiguous term but is often taken to mean "finite automaton", of which deterministic finite automata (DFAs) are representative. These are strictly less powerful than Turing machines and other Turing-equivalent systems of computation. That said, actual computers running C# programs are not Turing equivalent; in fact, they're a strictly weaker model of computation that finite automata, although many interesting finite automata can be modeled exactly, and many Turing machines can be simulated accurately. PC < FSM ~ DFA < TM.
Suppose that your PC has 1 TB of memory (RAM, registers, stack, HDD, etc.) This is 8796093022208 bits. Your computer can exist in 2^8796093022208 unique states. It is therefore incapable of recognizing any regular language whose minimal DFA contains more than 2^8796093022208 unique states. One such language is the language containing the first 2^8796093022208 words over a unary alphabet (when ordered lexicographically).
FSM is an ambiguous term but is often taken to mean "finite automaton", of which deterministic finite automata (DFAs) are representative. These are strictly less powerful than Turing machines and other Turing-equivalent systems of computation. That said, actual computers running C# programs are not Turing equivalent; in fact, they're a strictly weaker model of computation that finite automata, although many interesting finite automata can be modeled exactly, and many Turing machines can be simulated accurately. PC < FSM ~ DFA < TM.
Suppose that your PC has 1 TB of memory (RAM, registers, stack, HDD, etc.) This is 8796093022208 bits. Your computer can exist in 2^8796093022208 unique states. It is therefore incapable of recognizing any regular language whose minimal DFA contains more than 2^8796093022208 unique states. One such language is the language containing the first 2^8796093022208 words over a unary alphabet (when ordered lexicographically).
Context
StackExchange Computer Science Q#18210, answer score: 3
Revisions (0)
No revisions yet.