Chomsky Hierarchy
Chomsky Hierarchy Is Finite Automata Is Less PowerFul Than Push Down Automata, Push Down Automata Is Less Powerful Than Linear Bounded Automata, Linear Bounded Automata Is Less Powerful Than Turning Machine. Type 0 Is More Powerful Than Type 1, Type 1 Is More Powerful Than Type 2, Type 2 Is More Powerful Than Type 3.RL Is Less Powerful Than CFL, CFL Is Less Powerful Than CSL, CSL Is Less Powerful Than REL. Today We Will Understand The Relation Between Types Of Languages And Types Of Grammer And Types Of Automata. And We Will Know Which Which Machine Represents Which Langauge And Which Grammer Represents Which Grammer. There Are Four Types Of Formal Language Regular Language (RL) Context Free Language (CFL) Context Sensitive Language (CSL) Recursive Enumerable Language (REL) Let's Know Which Grammer Applies For These Languages An Which Grammar I Use.
If You Observe The Above Picture, You Can See The Four Languages Types. Grammer Is Generator For A String. If I Want To Generate Regular Language, I Use Regular Grammer. To Generate Context Free Language, I Use Context Free Grammer. To Generate Context Free Language, I Use Context Sensitive Grammer. Last Type Of Formal Language Is Recursive Enumerable Language, REL Accepts All Languages, All The Strings,So There Is No Structure For Grammer, That's Why We Call It As Unstructured Grammer. In Few Books, You Will Be Seeing Recursive Enumerable Grammer But The Proper Word For It Is Unstructured Grammer. The Two Components For Language Is Generator And Acceptor. Grammars Are The Generators Of The Languages. Let's Know About The Acceptor(Machine Or Automata). For Every Langauge, There Is A Automata(Machine) Which Accepts The Language. We Call Automata As Acceptor. To Accept Regular Language, I Use Finite Automata. To Generate Context Free Language, We Use Context-Free Grammar, To Accept Context Free Grammer We Use Push Down Automata. To Generate ContextSensitivee Language, Context Free Grammer Is Used To Accept Context Free Grammer We Use Linear Bounded Automata. To Accept Recursive Enumerable Language, There Will Be No Structures For This Language, Any Structure Or Any String Comes This Language. If Other Languages Doesn't Accept Any Grammer, Recursive Enumerable Language Accepts That Grammer. We Use Turing Machine To Accept This Language. Turing Machine Is Called As Abstract Model Of Computer Because Whatever Computer Can Solve The Problems, This Turing Machine Can Solve Every Problem That Computer Solves. This Is All About The Types Of Formal Languages, Types Of Grammars, Types Of Acceptors (Machines) Which Accepts The Languages.
Chomsky Hierarchy
According To The Chomsky, Chomsky Is The Name Of A Scientist, He Divided Languages Into Types. He Divided Grammars In To Types. He Said Two Grammars Are Most Powerful. Type 0 Grammer. Turing Machine Is The Most Powerful Machine. I'm Comparing Turing Machine With Computer. That's Why Unstructured Grammer Is Called A Type 0 Grammer. Chomsky Said Context Sensitive Grammer As Type 1 Grammer. Context Free Grammer Is Said As Type 2 Grammer. Regular Grammer Is Said As Type 3 Grammer. According To The Power Of Acceptance, The Machine Which Accepts The Strings Most He Said It As The Powerful.I.e Turning Machine. The Machine Which Accepts Fewer Strings, Which Accepts Fewer Languages, I.e Finite Automata. Type 3 Is Less Powerful Than Type 2 And Type 2 Is Less Powerful Than Type 1 And Type 1 Is Less Powerful Than Type 0. If You Observe The Picture You Can See Type 3 Is Finite Machine. Type 2 Is Pushdown Automata. Type 1 Is Linear Bounded Automata. Type 0 Is Turning Machine. In Languages, Regular Language Is Less Powerful Than Context Free Language(RL Read the full article