Answer to Question #227652 in Algorithms for kkk

Question

​c) Classify each of the following grammar rules according to Noam Chomsky’s classification of ​grammars (in each case give the largest – i.e. most restricted - classification type that applies):

​1. aSb → aAcBb

​2. B → aA

​3. S → aBc

​4. S → aBc

​5. Ab → b

​6. AB → BA

Answer 1

​1. aSb → aAcBb Type-1 grammar or the context-sensitive

​2. B → aA Type-3 grammar or regular gramma

​3. S → aBc Type-2 grammar or context-free

​4. S → aBc Type-2 grammar or context-free

​5. Ab → b Type-1 grammar or context-sensitive

​6. AB → BA Type-1 grammar or context-sensitive