State True or False: Classes of Grammar and respective automata
in Theory of Computation
0 votes
0 votes

Consider the following statements:-

I) Type-0 grammar generate exactly all language that can be accepted by a total Turing machine.

II) Type-1 grammar generate exactly all languages that can be recognized by a linear bounded automata.

III) Type-3 grammar have one to one correspondence with set of all regular expressions.

which of the above statements is/are true?

why statement 3 is true 

Counter case :-

Grammar G1) A -> aA/a

Grammar G2) A -> Aa/a

both are type 3 grammar but both represent same regular expression as a+

what is wrong in this??

in Theory of Computation
114 209 372

Subscribe to GO Classes for GATE CSE 2022

2 Answers

2 votes
2 votes

After discussion with deepak sir:

First of all point 3 is wrongly framed.

This are the points from Go classes telegram channel:


There exists a Bijection  between Set of type 3 grammars and set of all regular expressions... YES. 

because both are countable infinite so have same cardinality as set of positive integers. 


There exists a Bijection between Set of Turing machines  and set of all regular expressions...? 

Same reason.


What is countably infinite?

→ when the set S has one to one correspondance with the natural number.

So,similarly “Set of ALL Grammars and set of regular languages both are countable infinite.” 

Since set of all grammars has one to one correspondance with natural number and regular language has one to one correspondane with natural number.So this implies that surely there will be a bijection.

8 2

1 comment

@Deepak Poonia thank u sir for clearing the concept.

1 vote
1 vote
Type-0 (RE)
Type-1 (CSL)
Type-2 (CFL)
Type-3 (Regular Language)

I also think statement 3 is not correct, because a language can be generated by more than one grammar.
It's not only specific to regular language, but any language can be generated by more than one grammar though each grammar corresponds to a unique language.

Where is it given that statement 3 is correct?
163 309 512


they are askng about regular expression.

I thnk that is also same for more than one grammar.

please check the counter case.
you have already shown, more than one grammar for same regular expression.

youdidn't answer from where you copied it!
TestBook Demo test.

Related questions