A four-part question dealing with formal languages and regular expressions:

  1. How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string?
  2. How many using just *, +, and •?
  3. How many using just + and •?
  4. How many using just •?
  • 1
    Are you talking about regular expressions which only match abcd or regular expressions which match a set which includes abcd? – rici Sep 29 at 19:51
  • 1
    Either way, as soon as you allow alternation, the answer is "an unlimited" number, because abcd is matched by $abcd$, $(a+a)bcd$, $(a+a+a)bcd$, $(a+a+a+a)bcd$ …. If you want to say "But those don't count!", then you need to be very clear what you mean by "different" regular expression. – rici Sep 29 at 19:56
  • We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Raphael Oct 11 at 12:00
up vote 0 down vote accepted

First, note that, over any finite alphabet, there are countably infinitely many regular expressions. This is immediate from the fact that regular expressions are finite strings (which gives the upper bound) and that $a$, $aa$, $aaa$, ... are all regular expressions (which gives the lower bound). From now on, I'm just going to say "infinite" instead of "countably infinite" because we've established that nothing in this context is uncountable.

If you're allowed to use $\varepsilon$, there are infinitely many regular expressions that match $abcd$: for example, $abcd\epsilon^n$ for all $n\geq 0$.

If you're allowed to use alternation, there are infinitely many: for example, $abcd$, $(a+a)bcd$, $(a+a+a)bcd$, ... .

If you want regular expressions that match only the string $abcd$, Kleene star isn't useful. If it's applied to any regexp that matches any non-empty string, then the resulting regexp will match strings of arbitrary length, so will be invalid. If it's applied only to regexps that are equivalent to $\varepsilon$ then we could have already used those regexps to get infinitely many regexps for $abcd$, as in the $\varepsilon$ case. The only remaining case is that $\emptyset^*\equiv\varepsilon$, so Kleene star and $\emptyset$ together yield infinitely many regexps for $abcd$. However, this case isn't relevant in your case structure, since you eliminate $\varepsilon$ and $\emptyset$ from consideration at the same time.

If you're only allowed concatenation, then there is exactly one regular expression that matches $abcd$: $abcd$ itself.

  • Thanks! One small note: I overlooked that technically, concatenation has only two arguments, so if we're being really picky, even with just concatenation, there are 5 possible arrangements: (ab)(cd), (a(bc))d, ((ab)c)d, a((bc)d), (a(b(cd)) – Vera Oct 4 at 21:39
  • @Vera Good point. And the number of such concatenations is the $n$th Catalan number. – David Richerby Oct 4 at 21:54

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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