Search code examples
regexcomputer-scienceregular-languagedfanfa

Find the regular expression for the language on E={a,b}

L = w : (na(w) - nb(w)) mod 3 /= 0

How can I go about finding the regular expression for this language?

I understand that it means that the number of As minus the number of Bs cannot be a multiple of 3. So a - b cannot be 3,6,9,12, etc.

But I am still having trouble putting it into a regular expression. I tried first making it a DFA or NFA but I couldn't do that either.

Any help is appreciated!

Solution

  • I would go about it by dividing the list of words on {a,b} into three cases:

    • L1 = w : (na(w) - nb(w)) mod 3 = 1
    • L2 = w : (na(w) - nb(w)) mod 3 = 2
    • L3 = w : (na(w) - nb(w)) mod 3 = 3

    L is then L1 U L2, and you should be able to create expressions relating L1, L2, and L3. You should then be able to eliminate things and end up with a regular expression on {a,b}.