Peter Linz, EX-3.1, Q10

Question

Give a regular expression for L = {anbm: n ≥ 1,m ≥ 1,nm ≥ 3}

Comments

Duplicate: https://gateoverflow.in/207494/peter-linz-edition-4-exercise-3-1-question-10-page-no-76

Check for duplicates before asking a question.

Read all the rules from here https://csedoubts.gateoverflow.in/blog/1/guidelines-to-users

Answer 1

here condition  nm >= 3 , for this minimum possible values satisfying these for (n,m) are (1,3),(3,1),(2,2) so these are minimum no of a’s and b’s can have  together in any expression.

so, (abbb,aaab,aabb) are min length strings And can have any no. of a’s in left side and b’s  in right  side of these strings.

So we can write it as, 

 a*(abbb +  aaab + aabb)b*

=> a*a(bb + aa + ab)bb*

=> a*a(bb + a(a+b) )bb*

 

So the regular expression for  {anbm: n ≥ 1,m ≥ 1,nm ≥ 3}  is  a*a(bb + a(a+b) )bb*.

 

Correct me If I’m Wrong :)