UGC NET CSE | July 2018 | Part 2 | Question: 38

Question

The set $A = \{ 0^n \: 1^n \: 2^n \mid n=1, 2, 3, \dots \}$ is an example of a grammar that is

• A. Context sensitive
• B. Context free
• C. Regular
• D. None of the above

Answer 1

Answer : 1

The given language is Standard Context Sensitive language. 

Answer 2

a^nb^nc^n is contest sensitive grammar . We need two stack.so option a is right

Answer 3

It is in the form aⁿbⁿcⁿ which is CSL.

Let's see why :

On seeing a, you push to stack, on seeing b you pop out from stack essentially comparing number of b’s with a’s. When it sees a c, well, there’s nothing it could do as the one memory it had got used up.

Hence it is not CFL and cannot be accepted by a Push down automata. It needs a Linear Bounded Automata to accept it .