Question

Give English descriptions of the languages represented by the following regular expressions. The descriptions should be simple, similar to how we have been defining languages in class(e.g., “languages of binary strings containing 0 in even positions. . .”). Note: While describing your language, you don’t want to simply spell out the conditions in your regular expressions. E.g., if the regular expression is 0(0 + 1)∗, an answer of the sort “language of all binary strings that start with a 0” will receive A grade, but an answer of the sort “language of all binary strings where the first symbol is a 0 and it is followed by an arbitrary number of 0s and 1s” will receive a B grade. Note that both are technically correct, but the former one is easier to comprehend. Basically, try to simply the description (without losing precision) to the extent possible.

a) (0* 1* ) * 0000(1+0) *

b) (a + b + c)∗b(a + b + c)∗c(a + b + c)∗ + (a + b + c)∗c(a + b + c)∗b(a + b + c)∗

Answer 1

a) This regular expression generates a language which accepts all string which "can start with repeated sequence of 0s and 1s followed by three 0s and then followed by any number of 0s or 1s".

b) This regular expression generates a language which accepts all string which '"can either start with any number of a's, b's or c's and then followed by b and and again followed by a sequence of any number of a's, b's or c's and then followed by c and finally followed by a sequence of a's, b's or c's" or ""can either start with any number of a's, b's or c's and then followed by c and and again followed by a sequence of any number of a's, b's or c's and then followed by b and finally followed by a sequence of a's, b's or c's".