254 views
0 votes
0 votes
S→ aSb/epsilon

is this linear grammar? I know it's a cfg but is it linear as well?

1 Answer

0 votes
0 votes
See they talking about linearity only not regularity.Most of us can confuse in it.

But Chomsky hierarchy says that=>

every CFG is not a linear G( the grammar which has at most one non terminal in RHS) ,but every linear G is a CFG.

we also says that CFG is a superset of linear G.

and moreover, linear grammar is a superset of RG.

linear grammar have special two version:

1)right linear G

2)left linear G

which are RG.

so the given grammar is linear.

i hope its helpful.

Related questions

1 votes
1 votes
1 answer
3
aditi19 asked Mar 7, 2019
823 views
what is the CFG for the language L=w where number of a’s in w+number of b’s in w=number of c’s in whow to approach this?
0 votes
0 votes
1 answer
4
aditi19 asked Mar 2, 2019
780 views
S->A | BA→ εB->aBbB->bwhat is the complement of the language of this grammar?