Search code examples
regexregular-language

deriving regular expressions from a regular language


Given the language below, how do i find a regular expression for the language

L = {a ^n b ^m | n => 1, m =>1, nm =>3}


Solution

  • n>=1 and m>=1 and nm>=3 is true for each of the following:

    n=1,m>=3

    n>=3,m=1

    n>=2,m>=2

    So L = { abbb, abbbb, abbbbb, ... } U { aaab, aaaab, aaaaab, ... } U { a^n b^m | n>=2,m>=2 }

    This regex should be equivalent to L:

    ((abbb(b*)) | (aaa(a*)b) | (aa(a*)bb(b*)))

    There is probably a much more succinct answer than this.