Match a ^ n A ^ n with regular expression

Question

We learn about the difference between regular languages ​​and regular expression, and the teacher explained that the language

a^nb^n 

is not regular, but she said that most regular expression flavors can match

 a^n A^n 

and she gave this problem for our extra homework problem. We fought for a couple of days and really could use some recommendations.

Answer 1

The teacher gave a HUGE hint, limiting the alphabet {a, A} . The key to solving this problem is to understand that in case-insensitive mode, a corresponds to a and vice versa. Another component of the problem is mapped by a backlink.

This pattern will match a{n}A{n} for some n ( as seen on rubular.com ):

 ^(?=(a*)A*$)\1(?i)\1$ 

---

How it works

The drawing works as follows:

• ^(?=(a*)A*$) - anchored at the beginning of the line, we use a positive lookahead to see if we can match (a*)A* to the end of the line
  • If we can successfully complete this statement, then \1 captures the sequence a{n}
  • If the statement fails, then in no way can there be a line a{n}A{n} , since it is not even a*A*
• Then we match \1(?i)\1$ , that is, a{n} captured by \1 , and then in case-insensitive (?i) mode, we again match a{n} to the end of the line
• Thus, since:
  • String a*A*
  • \1 a{n}
  • \1(?i)\1 may be a{n}A{n}

Related Questions

• Case-sensitive and case-insensitive
• How does the regular expression '(? <= #) [^ #] + (? = #) Work?

References

• regular-expressions.info/Lookaround , Grouping and trackbacks
• Modifiers (for example, turning on and off modes for partial expression only)

see also

• Why {a ^ nb ^ n | n> = 0} is not regular?
• Wikipedia / Regular Expression: Patterns for Irregular Languages