We're learning about the difference between regular languages and regex, and the teacher explained that the language
a^n b^n
is not regular, but she said that most regex flavors can match
a^n A^n
and she gave this problem for our extra credit homework problem. We've been struggling for a couple of days now, and could really use some guidance.
The teacher gave a HUGE hint by limiting the alphabet to {a, A}
. The key to solving this problem is realizing that in case-insensitive mode, a
matches A
and vice versa. The other component of the problem is matching on backreference.
This pattern will match a{n}A{n}
for some n
(as seen on rubular.com):
^(?=(a*)A*$)\1(?i)\1$
The pattern works as follows:
^(?=(a*)A*$)
- Anchored at the beginning of the string, we use positive lookahead to see if we can match (a*)A*
until the end of the string
\1
captures the sequence of a{n}
a{n}A{n}
, since it's not even a*A*
\1(?i)\1$
, that is, the a{n}
captured by \1
, then in case-insensitive mode (?i)
, we match a{n}
again until the end of the stringa*A*
\1
is a{n}
\1(?i)\1
can only be a{n}A{n}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With