automatafinite-automataautomata-theory

Regular Expression All strings where the number of b’s can be evenly divided by 3


I am a student doing assigment can any tell me the solution for numbers of bs evenly divided by 3.Have already checked stackover flow no such question i found.


Solution

  • First, all languages are sets of strings whose symbols are taken from some alphabet. You mention just one symbol, b. Your alphabet may be {b}. Or, maybe your strings can also have a; then your alphabet is {a, b}. I'll assume the latter for this answer since it's the harder case to answer and is more representative of all other possible cases.

    We make a few observations:

    1. the empty string is in the language
    2. you can always add more instances of a anywhere
    3. you can only add more instances of b in multiples of three

    The simplest string with three instances of b is bbb. However, as a regular expression, this restricts us to just contiguous instances of b. We want to be able to add instances of a anywhere; so consider

    a*ba* ba*ba*
    

    This regular expression gives us just the strings with exactly three instances of b. To allow any number, we can use a Kleene star and add some more a*:

    a*(a*ba*ba*ba*)*a*