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!


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.