I am practicing for an exam. I am trying to convert a language to a regular expression. The language and my solution is as follows:

$L=\{w∈\{a,b\}^+│|w|≥4\ and\ the\ second\ symbols\ from \ the \ front\ and\ the\ back\ are\ equal\}$

Solution: $(a+b)x(a+b)^* x(a+b) \ \ where\ x=(a+b)$

Is this correct? If not, can someone correct me. also, am I allowed to use variables in regular expressions?

Thanks in advance

  • $\begingroup$ I think the definition of $L$ is unclear. Is $aabb \in L$? $\endgroup$
    – Raphael
    Jun 15 '17 at 12:47
  • $\begingroup$ @Raphael No, it is not $\endgroup$
    – Amine
    Jun 15 '17 at 12:55
  • $\begingroup$ So, $L = \{ wvw \mid x, w \in \{a,b\}^2, |w| = 2 \}$? Then, the easiest (if maybe not fastest) route is probably to come up with an NFA and convert it. $\endgroup$
    – Raphael
    Jun 15 '17 at 13:26
  • $\begingroup$ Regarding your attempt, if your notation means to imply that $x$ "matches" the same string, it's not a regular expression. If that was not the intent, then the regular expression matches $abba$ which is not in $L$. $\endgroup$
    – Raphael
    Jun 15 '17 at 13:27
  • 1
    $\begingroup$ @AndréSouzaLemos Oh, right. In that case, I understand the attempt -- but it's not a regular expression. Amine, you may have regexps with capturing groups in mind, as they are encountered in programming libraries. Those are strictly more powerful than regular expressions as defined in TCS. $\endgroup$
    – Raphael
    Jun 15 '17 at 21:08

You asked two questions. The usual rule on this site is to ask one question per post.

No, you're not allowed to use variables in regular expressions. Regular expressions have a formal definition. To qualify as a regular expression, you need to meet the requirements in the definition. The definition can be found on Wikipedia or in your favorite textbook, and you'll note that it does not allow "where" or "variables".

For your first question about how to find a regular expression for a language, take a look at How to prove a language is regular?.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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