0

I would like to construct a regular expression of length at least 5 that starts with 'f' and ends with 'y' and who's second symbol is 'u' from the alphabet {a,b,...,z}. My solution to this problem is: $$$$ Let m be a string s.t. $\{m\in\{a,b,...,z\}^* \mid$ m has length that is at least 5, starts with 'f' and ends with 'y' and who's 2nd symbol is 'u'$\}$ Then,$$m=fun^*n^*y$$ Does that seem right?$$$$ Edit: After reading some comments below shouldn't the answer be $$fum^*m^*y$$ since m is any of the letters a through z, but then if m is an empty string we get fuy and it doesn't meet the condition of being of length 5 so is there a way to say that m cannot be empty in fum*m*y, but in such a way that it is in the form of a regular expression? $$$$ Second Edit: After reading up on some examples I would say that the answer would be $$m=fum^+m^+y$$ that is it starts with f followed by u and at least one m followed by at least one more m and ends in y but I'm still unsure if $$m^+$$ could still be an empty string in which case I would have to define a new alphabet that contains no empty string and use that i.e. $$$$ Let $A=\{m^\prime \in \{a,b,...,\} \mid m $ doesn't contain empty string $\}$ and then we get: $$m^\prime=fu m^\prime m^\prime y$$ the only thing is I am not sure if every set has to have an empty string or that I can just construct a new alphabet and use it in my answer.

Vector_13
  • 626

1 Answers1

1

The answer $fuMM^{+}y$ will match strings you are looking for. The first $m$ picks a single character from the alphabet. The $m^{+}$ picks at least one more character from the alphabet.

Note that I define $M = (a + b + c + d + e + ... + z)$, which is different from how you defined it. This way, $m$ is a single character, not the Kleene closure of the alphabet.

Edit: I might use the syntax $fu[a-z][a-z]^{+}y$.

ml0105
  • 14,674
  • but doesn't that mean that the first m only picks m out of the alphabet but we want any letter? – Vector_13 Apr 20 '14 at 21:01
  • No. The $+$ symbols mean $OR$. It will pick any character from the alphabet. You could equivocally write $fu[a-z][a-z]^{+}y$, which is probably more concise and more descriptive. – ml0105 Apr 20 '14 at 21:05
  • 1
    Also, the fact that you are using $m$ to be your regular expression, a part of your regular expression, in the alphabet, and the Kleene closure of the alphabet is probably causing some confusion. Don't abuse notation. Part of math is being very clear as to what your variables represent. – ml0105 Apr 20 '14 at 21:08
  • could you please explain how your alphabet differs from mine and why m cannot choose an empty string which would make fuy? – Vector_13 Apr 20 '14 at 21:09
  • My alphabet doesn't differ from yours. In fact, I am using the same alphabet you are. Let's do this- stop using $m$ as anything other than an element in the alphabet. This will alleviate some notational abuse (and hopefully confusion). I've replaced my little $m$ with a big $M$ to denote the difference. The syntax $(x + y)$ says pick exactly one of $x$ or $y$. Since we must pick exactly one element per big $M$, we must have at least $5$ characters. Note that $M^{+} = MM^{*}$. – ml0105 Apr 20 '14 at 21:12
  • one last thing so why can't M pick an empty string since empty string is part of any alphabet and that would make fuy. And is it okay to define a new set such as $M^\prime=M/empty string$ ie M without empty string and then do $fu M^\prime M^{\prime +}y$ – Vector_13 Apr 20 '14 at 21:16
  • It depends on your definition of an alphabet. I haven't seen an alphabet defined as containing the empty string. If you define it that it does contain the empty string, then defining a subset of the alphabet and applying my solution would suffice. Also, notice how I define $M$. It explicitly does not contain the empty string. – ml0105 Apr 20 '14 at 21:17