edited by
17,384 views
18 votes
18 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
edited by

8 Answers

Best answer
24 votes
24 votes

type 3

selected by
6 votes
6 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.
edited by
2 votes
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).

1 votes
1 votes
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:

Related questions

33 votes
33 votes
4 answers
1
10 votes
10 votes
1 answer
2
34 votes
34 votes
7 answers
4
Kathleen asked Sep 22, 2014
20,200 views
$$S \to aSa \mid bSb\mid a\mid b$$The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of:all palindromesall odd length palindromesstrings t...