1
$\begingroup$

I have an alphabet $\Sigma = \{a,b,\#\}$. I'm trying to write a regex that only accepts strings that have the same pattern before and after the $\#$ without using back references. For example, $aab\#aab$ is accepted, but not $aba\#aab$. How in the world do you handle this? I thought you could maybe do something like $(a|b)^*\#(a|b)*$, but this doesn't work at all.

$\endgroup$
1
  • 6
    $\begingroup$ Exercise: Use the pumping lemma to show that this language is not regular. Advanced exercise: Use the pumping lemma to show that this language is not context-free. $\endgroup$
    – Pseudonym
    Sep 23 '21 at 4:33
1
$\begingroup$

As pointed out by Pseudonym (in the comments) it's not a known pattern nor regular to be matched by a simple regex. If you knew the possibilities then sure you could use a regex (aab#aab|bba#bba).

Another option is to write some code to use the regex to find a looser pattern but then validate the pattern that you wish to have:

const input = "aab#bba aab#aab"

/**
 *
 * @param {string} val input of plain text
 * @returns Array<string> Strings that have a matched pattern
 */
function findMirroredString(val = "") {
  
  const matches = val.match(/([a-z]+#[a-z]+)/g);
  
  // Return early if no matches were found by the regex.
  if (!matches) return [];
  
  // Filter to find the correct patter of "x#y" where x equals y
  return matches.filter(match => {
      // Split the parts by the # symbol and check if the two parts are equal,
      // If they are equal then the pattern is valid.
      const parts = match.split("#");
      return parts[0] === parts[1];
    });
}

console.log(
    findMirroredString(input)
);
```
$\endgroup$

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.