Computational science is one of very interesting subject. It's an abstract topic but something which i believe to be most essential for anyone who wants to learn Computers. Learning about this won't help you to write a program or to understand how to build a computer but it will help you to understand the limitation of any mechanical computational device in terms of what kinds of problems it can solve.
Most of books discuss about only 3 categories of Devices i.e.
1. Finite Automata
2. Push down Automata and
3. Turing Machine.
FA is mainly concern with basic computation including matching whether a particular input satisfies any specified pattern or not. These devices are memory-less so they cannot count the occurrence of any specific alphabet. They are very limited in terms of expressiveness yet very helpful.
PDA are mainly concerned with Context Free Grammars i.e. Non Ambiguous Grammars. They have infinite amount of memory which is provided by a stack. They are mainly used for parsing of an expression. So, any compiler you see or any XML parser you see, all have Context Free Grammar. For someone from non CS background, a CFG is a grammar where if you write any statement then it can always be evaluated to one value only not the other.
Turing Machines are computational device which are equivalent in terms of computational power to a computer. So, anything you can do with a computer can be done with a Turing Machine. In fact all the programming languages are expected to be Turing Complete. The grammar is called Unrestricted Grammar.
------------------------------------------------------------------------------------------------------------
Now, above all you can get from any other TCS book, and its their in every syllabus.
Having said above, do you really think all kinds of computational machines can be represented by above 3 automata ??
If you say yes, then think again, what about parallel processing and what about distributed system ???
can you represent this entire world and interaction among all the living species ??
can you represent the complex patterns which occur in this world ???
Yes, these kind of things can also be represented using an automata ...
Most of books discuss about only 3 categories of Devices i.e.
1. Finite Automata
2. Push down Automata and
3. Turing Machine.
FA is mainly concern with basic computation including matching whether a particular input satisfies any specified pattern or not. These devices are memory-less so they cannot count the occurrence of any specific alphabet. They are very limited in terms of expressiveness yet very helpful.
PDA are mainly concerned with Context Free Grammars i.e. Non Ambiguous Grammars. They have infinite amount of memory which is provided by a stack. They are mainly used for parsing of an expression. So, any compiler you see or any XML parser you see, all have Context Free Grammar. For someone from non CS background, a CFG is a grammar where if you write any statement then it can always be evaluated to one value only not the other.
Turing Machines are computational device which are equivalent in terms of computational power to a computer. So, anything you can do with a computer can be done with a Turing Machine. In fact all the programming languages are expected to be Turing Complete. The grammar is called Unrestricted Grammar.
------------------------------------------------------------------------------------------------------------
Now, above all you can get from any other TCS book, and its their in every syllabus.
Having said above, do you really think all kinds of computational machines can be represented by above 3 automata ??
If you say yes, then think again, what about parallel processing and what about distributed system ???
can you represent this entire world and interaction among all the living species ??
can you represent the complex patterns which occur in this world ???
Yes, these kind of things can also be represented using an automata ...
No comments:
Post a Comment