Regular expression with quantity dependence

Question

Is it possible to create regular expression that will describe words like:

aabc
aaaabcbc
aaaaaabcbcbc

?

Words are created like each occurrence of (bc) on the right is connected with occurrence (aa) on the left.

Words below are not valid:

aa
bc
aaabc
aaaabc
aabcbc 

Answer 1

No it cannot be expressed in terms of regular expressions. That is because, your expression, requires a number of "aa" followed by equal number of "bc". This requires infinite memory. FA do not have infinite memory.

It can be expressed in context-free grammar.-

S -> aaSbc | έ     Epsilon stands for string of zero length(empty string).

This generates strings like - Valid string - έ(Empty string), aabc, aaaabcbc and so on.

Read more about context free and regular grammar here.

Answer 2

Just fyi it would be possible in non regular languages.

For example you could play with balancing groups in .NET and get something like this:

^(?<a>aa)+(bc(?<-a>))+(?(a)(?!))$