What is Noam Chomsky Grammar Classification?

Noam Chomsky Grammar Classification

Noam Chomsky Grammar Classification

Hierarchy means an organized structure in which items are arranged according to their rank or level. Chomsky has proposed such kind of hierarchy in which he has given different levels to grammar. Levels are given in terms of  Type-0, Type-1, Type-2, Type-3 on the basis of their unrestricted to restricted behavior. This behavior is based on the representation or arrangement of terminal and nonterminal in the grammar.

Noam Chomsky Grammar Type 0 :

This type of grammar is unrestricted, or phase structured, which generates all types of languages that can be recognized by a Turing machine. These languages are called recursive enumerable language. Unrestricted means these grammar have very less restrictions. Unrestricted grammar (G) = L → R (L is left side and R is in right side of production) , where L, R ∈ (V ∪ T)* means any combination of terminal or non terminal on left hand side i,e. L as well as on right hand side  i,e. R and one left side mean “L” must have at least one variable. V stands for variable and T for terminals. 

Example of Type 0 grammar : All in red are L and in blue are R

                                        L → R 

                                        S → aSb/λ

                                        A → aA/aB/Cb

                                        Ba → a/Da

Noam Chomsky Grammar Type 1 :

This is context-sensitive grammar (CSG) which is used to generate context-sensitive languages. CSG (G) = L → R, where L,R ∈ (V ∪ T)* and “L” must have at least one variable. There is one additional rule also, |L| ≤ |R|, which means length of “L” should be less than or equal to “R”. In simple words we can say on left of production there should be less number of terminal or non terminal as compare to right hand side of production.

Example of Type 1 grammar : All in red are L and in blue are R

                                    L → R     

                                        S → aSb/λ

                                        Aa → aAB/aB/Cb

                                        B → a/Da

Noam Chomsky Grammar Type 2 :

This is context-free grammar (CFG) which is used to generate context-free languages. CFG (G)= L → R, where R ∈ (V ∪ T)* and |L| ≤ |R|. In addition to the CSG grammar, one extra rule, that is, only single variable is allowed in “L”.

                                    L → R                                        

                                        S → aSb/λ

                                        A → aA/aB/Cb

                                        B → a/Da

Noam Chomsky Grammar Type 3:

This is regular grammar, therefore language generated by these grammars is called regular languages. Regular grammar (G) = L → R, where L ≤ R , {R ∈ (T*, T*V, VT*) and u ∈ V} and “u” has only one variable.

                                    L → R    

                                        S → aS/λ

                                        A → aA/aB/Cb

                                        B → a/Da

Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.