Let a b For each of the following languages find a grammar

Let = {a, b}. For each of the following languages, find a grammar that generates it.

1. L1 = {a^n b^m : n => 0, m < n}

2. L2 = {a^3n b^2m : n => 2}

3. L3 = {a^(n+3) b^n : n => 2}

4. L4 = {a^n b^(n-2) : n => 3}

Solution

1. L1 = {a^n b^m : n => 0, m < n}

what this means is that there is a string with aaaaaa.. which are followed by more number of bbbbb...

also, null will NOT be a member of this since n can be 0 but m < n so m has ttto be atleast 1

so some examples include abb, aabbbb and so on...

there has to be a condition that for every a added we must add a b atleast.

but we need to make sure m > n always ,these two conditions can be acheieved by the following -

S -> bSa //for every a added, add a b

B -> bB | b // to generate extra b\'s since m > n

these two conditions will provide the grammar needed.

---------------

L2 = {a^3n b^2m : n => 2}

let us look at this similarly to the first one.

here m can be 0 so , but n >=2 so we\'ll have strings like - aaaaaa , aaaaaaaaa, ... and so on

so, solution -

B -> aaaaaaB | B

S -> aaaSbb

no relation between m and n so this holds

----------------

L3 = {a^(n+3) b^n : n => 2}

here base string will be atleast aaaaabb so

S -> aaaaaSbb | B

B -> aSb

since we have already considdered n+3 and n>=2 in the first condition

---------------------

L4 = {a^n b^(n-2) : n => 3}

like for L3 , let us just create a base any string after it will just simply have an a and a b.

all strings will be of the form aaab

given by

S -> aaaSb | B

after this all strings will have an a or a b atleast

B -> aSb |

***** this part of the solution is incorrect . please look at the comment section.

-------------------

thank you