ISRO CSE 2016 | Question: 38

Question

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

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

• A. Type 0
• B. Type 1
• C. Type 2
• D. Type 3

Comments

Type-3 because all these grammar satisfying the rules of type-3 grammar.

---

we can derive only one string from given grammmer

aabca

Answer 1

type 3

Comments

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.

Answer 2

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.

Answer 3

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. (S→Aa,A→Ba,B→abc).

Comments

It is type-3 grammar.

As it generates only one finite string, given grammar is regular.

Answer 4

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

Answer 5

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.

Comments

Its not type 3 different books have different conventions and the above grammar is not strict see wiki also..it 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.

Answer 6

both C and D