Register

State True or False: Classes of Grammar and respective automata

2,114 views
1 votes
1 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??

User Avatar

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. 


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.

User Avatar
1 votes
1 votes
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?
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
1 answer
1
Santhosh Devulapally asked Jun 20, 2016
1,290 views
STATE TRUE OR FALSE
1) (L/a)a=L(the left side represents the concatenation of the languages L/a and {a}) 2) a(a/L)=L(again concatenation with {a},this time on the left,is intended) 3) (La)/a=L 4) a/(aL)=L
1) (L/a)a=L(the left side represents the concatenation of the languages L/a and {a})2) a(a/L)=L(again concatenation with {a},this time on the left,is intended)3) ...
User Avatar
2 votes
2 votes
2 answers
2
Kapil asked Jul 8, 2016
1,397 views
Regular Expression time complexity
The equality of two regular expression is computed in? Give reasons also.. Constant Time polynomial time logarithmic Polynomial time Exponential time
The equality of two regular expression is computed in? Give reasons also..Constant Timepolynomial timelogarithmic Polynomial timeExponential time
User Avatar
1 votes
1 votes
2 answers
4
shekhar chauhan asked Jun 8, 2016
1,828 views
Automata Regular expression
If r1 and r2 are 2 Regular Expression Such that r1 = (a+b)* r2 = (a*+b*+a*b*+b*a*) What are the different case's in which r1 = r2 ? Please Explain with an example
If r1 and r2 are 2 Regular Expression Such thatr1 = (a+b)* r2 = (a*+b*+a*b*+b*a*)What are the different case's in which r1 = r2 ?Please Explain with an example
User Avatar
Link Copied!