Number of strings accepted by this regular expression

Question

This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices.

If a regular expression is of the form (x+y)*y(a+ab)* , then what is the maximum number of strings with length 4 will bee accepted by its language?

I've tried simplifying the expression, or drawing FSM diagrams but can't figure it out. A little help would be appreciated.

Thank you!

Answer 1

NOTE: I'm assuming + is the union operation, as used here, rather than the Kleene plus or a terminal symbol.

The first step is breaking this RE into three parts: (x+y)*, y, and (a+ab)*. Now consider, how many ways can we make something with less than four characters from each of these?

• (x+y)*: one of length 0, two of length 1, four of length 2, eight of length 3
• y: one of length 1
• (a+ab)*: one of length 0, one of length 1, two of length 2 (aa, ab), three of length 3 (aaa, aab, aba)

Now, how could you combine these to get length 4?

• 0 from the first (1), 1 from the second (1), 3 from the third (3)
• 1 from the first (2), 1 from the second (1), 2 from the third (2)
• 2 from the first (4), 1 from the second (1), 1 from the third (1)
• 3 from the first (8), 1 from the second (1), 0 from the third (1)

For each of those, multiply the number of possibilities. Taking 1 from the first, 1 from the second, and 2 from the third, for instance, gives 2×1×2=4 possibilities.

The sum of these is the total number of length-4 strings matched by this RE: (1)(1)(3)+(2)(1)(2)+(4)(1)(1)+(8)(1)(1) = 3+4+4+8 = 19.