INTRODUCTION TO THEORY OF COMPUTATION
Automation Theory is also known by the name of theory of computation, which is basically deal's with Mathematic's theory falling under the branch of the computer Science.
Automata originated from the word “Automaton” which is closely related to “Automation”.
Bsically automation represents that how the computer or any electronic compenent's deals with the computation i.e how they calculate the any expressions (NOTE ; that here we are not considering the medium of computation i.e electric signal or any other medium, we are only intrested on how the computer carry out those task's)
CHOMSKY HIERARCHY
Chomsky Hierarchy represents the class of languages that are accepted by the different machine. The category of language in Chomsky's Hierarchy is as given below:
Type 0 known as Unrestricted Grammar.
Type 1 known as Context Sensitive Grammar.
Type 2 known as Context Free Grammar.
Type 3 Regular Grammar.
___________________________________________________________________________________
-----------------------------------------------------------------------------------------------------------------------------
Hierarchy of Automation
Type 3 Finite Automata
Type 2 Push Down Automata
Type 1 Linear Bound Automata
Type 0 Turing Machine
Type 3 Grammar
Type 3 Grammar is known as Regular Grammar. Regular languages are those languages which can be described using regular expressions. These languages can be modeled by NFA or DFA.
Type 3 is most restricted form of grammar. The Type 3 grammar should be Type 2 and Type 1. Type 3 should be in the form of v -> v*T/T*
Type 2 Grammar
Type 2 Grammar is known as Context Free Grammar. Context free languages are the languages which can be represented by the context free grammar (CFG). Type 2 should be type 1. The production rule is of the form A -> a where A is any Non terminal and a is the terminal
Type 1 Grammar
Type 1 grammar is known as Context Sensitive Grammar. The context sensitive grammar is used to represent context sensitive language. The context sensitive grammar follows the following rules:
The context sensitive grammar may have more than one symbol on the left hand side of their production rules.
The number of symbols on the left-hand side must not exceed the number of symbols on the right-hand side.
The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on the right-hand side of any rule.
The Type 1 grammar should be Type 0. In type 1, Production is in the form of V → T
Type 0 Grammar
Type 0 grammar is known as Unrestricted grammar. There is no restriction on the grammar rules of these types of languages. These languages can be efficiently modeled by Turing machines.
Finite Automata:
The most simple and basic automata having multiple restriction which makes it to design simple and easy to understand. There's no any additional memory in this, Therefore the automata make transition's to determine it's current state. This can only solve such problem which is purely decidable and there's no any ambiguity exist's
Push Down Automata:
Complex than the Finite Automata having less restriction than finite automata, which ultimately makes it powerful than Finite Automata, this can also accept's the decidable probelm but with some ambiguous decidable problem
Linear Bound Automata:
This Automata is similar to the Push Down Automata with only the difference that Linear Bound Automata tries to reject the Null movers or epsilon moves which was not so in case of Push Don Automata
Turing Machine :
This is one of the most powerful Automata ever been, This Automata is theoritical Concept there's no any physical proof of this machine exists. In this Automata there's no any restriction on it's computation, which makes it the most powerful Automata
Want to learn Complete Theory of Computation then go through these any of the two link's provided below
No comments:
Post a Comment