The Gateway to Computer Science Excellence
+16 votes

What is the highest type number that can be assigned to the following grammar?

$$S\to Aa,A\to Ba,B \to abc$$

  1. Type 0
  2. Type 1
  3. Type 2
  4. Type 3
in Theory of Computation by Loyal (5.8k points) | 4.7k views
Type-3 because all these grammar satisfying the rules of type-3 grammar.
we can derive only one string from given grammmer


8 Answers

+20 votes
Best answer

type 3

by Active (4.2k points)
selected by
but if grammar satisfies type 3 t can also satisfies type 0 also so highest is type o,i.e recursive enumerable language
why not type 0 it satisfies all prpperties and question says highest type no.
Languages generated by Type 3 (Regular) grammars are the Regular languages. The rules have the restriction that they are of the form: A->a or A->aB (the rule S->epsilon is permitted if the starting symbol S does not appear on the right-side of any rules), which means that each non-terminal must produce exactly one terminal symbol (and possibly one non-terminal as well). The regular expressions generate/recognize languages of this type.
So we see that type 3 has production of form S->a or S->aB..hence how can the following be type 3
here highest means by smallest property it satisfies ?
he asked highest so why nt type0
Actually, we can assign Type 2 to it.

Question says highest number which acn be assigned

Since this is also a Type 2 (CFG) (and obviously type 3 - Regular), so it can be assigned type 2
The explanation provided in the answer is not correct. Right and Left Linear grammar are not correct justification of the answer, instead properties of Type 2 languages should have been provided.
why can't it be Type - 2 grammar because it is also satisfying the CFL grammar constraints.

A -> B then A is variable and B belongs to (variable or terminal)
yes it is satisfied by type-2 grammar but this grammar is finite hence regular grammar so that's why it is type-3 grammar and we know that if grammar is regular then it can be accepted by any type of grammar whether it is type-2,1,0.
but the question is asking about highest type number right ? then type-3 is subset of type-2 so highest number should be type - 2 right ? plz respond @shubhgupta
When you say type 2 grammar then it doesn't specify that, will this grammar be accepted by type 3 or not ? but when you say it is type-3 then it will automatically satisfy by the type-2 grammar and Type 2 grammar is less restrictive compare to Type 3 grammar. And in official key answer was given as D.
+4 votes
Let us see what we get by following the production rules :

$S \rightarrow \underline{A}a \rightarrow \underline{B}a.a \rightarrow abcaa$

We see that the language consists of just one string, which is $abcaa$. Thus, the language is finite and can be represented by FA. Hence, the highest type number is type-3.
by Active (2.6k points)
edited by
+2 votes

Option C Type 2 grammar

It is context Free grammer which is type 2 grammer beacuse here Non Terminal produce Terminal as well non terminals ie NT ---> T/NT.

Why not type 3 beacuse it not producing Non terminal to terminal only. (SAa,ABa,Babc).

by (105 points)
It is type-3 grammar.

As it generates only one finite string, given grammar is regular.
+1 vote
grammar will be type 3 grammar as it generates a regular language.. abcaa

since abcaa is regular it satisfies every type.. type 0,1,2,3

but the highest type number is TYPE 3
by (143 points)
+1 vote

D is the correct option because it preserves the form A->aB/Ba/a where A,B are set of Vertices and a is set of terminals.

by (23 points)
Its not type 3 different books have different conventions and the above grammar is not strict see wiki comes under type 2 only books cant be wrong see klp mishra nd one more book..A->aB/a ths is the strict form of type 3 grammar check john martin book also
It is satisfy all the rules of RL i.e TYPE-3 and it clearly generate only ONE string "aaabc".

Hence option D) is correct one.
0 votes

both C and D

by Junior (795 points)
0 votes

given grammar is left linear grammar .and every left and right linear grammar is regular.and reguar  grammar is colled type 3 grammar.

by Boss (36.6k points)
0 votes

The only Language represented by this Grammar is L = abcaa.

Hence regular, hence Type 3.

Option D

by Loyal (6.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,365 answers
105,260 users