1,447 views

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??

### Subscribe to GO Classes for GATE CSE 2022

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.

But

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

YES.
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.

by
8 2

### 1 comment

@Deepak Poonia thank u sir for clearing the concept.

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?
by
163 309 512

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

you have already shown, more than one grammar for same regular expression.

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

1
1,045 views