Return to Answer

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex /(.*)\1/ will capture the language $L = \\{ ww | w \in \Sigma^*\\}$ which is a CFL much more powerful. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \\{ ww | w \in \Sigma^*, \mid w \mid \le K\\}$, which for any fixed $K$ is a regular expression again.

But in principle, regexps as specified are more powerful than regular languages, as this related question discusses in much more detail (with a nifty example as well).

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex /(.*)\1/ will capture the language $L = \{ ww | w \in \Sigma^*\}$, which is not context-free. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \{ ww | w \in \Sigma^*, \mid w \mid \le K\}$, which for any fixed $K$ is a regular expression again.

But in principle, regexps as specified are more powerful than regular languages, as this related question discusses in much more detail (with a nifty example as well).

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex /(.*)\1/ will capture the language $L = \\{ ww | w \in \Sigma^*\\}$ which is a CFL much more powerful. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \\{ ww | w \in \Sigma^*, \mid w \mid \le K\\}$, which for any fixed $K$ is a regular expression again.

But in principle, regexps as specified are more powerful than regular languages, as this related question discusses in much more detail (with a nifty example as well).

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex /(.*)\1/ will capture the language $L = \\{ ww | w \in \Sigma^*\\}$ which is a CFL much more powerful. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \\{ ww | w \in \Sigma^*, \mid w \mid \le K\\}$, which for any fixed $K$ is a regular expression again.

But in principle, regexps as specified are more powerful than regular languages, as this related question discusses in much more detail (with a nifty example as well).

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex /(.*)\1/ will capture the language $L = \\{ ww | w \in \Sigma^*\\}$ which is a CFL. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \\{ ww | w \in \Sigma^*, \mid w \mid \le K\\}$, which for any fixed $K$ is a regular expression again.

But in principle, regexps as specified are more powerful than regular languages, as this related question discusses in much more detail (with a nifty example as well).

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex /(.*)\1/ will capture the language $L = \\{ ww | w \in \Sigma^*\\}$ which is a CFL much more powerful. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \\{ ww | w \in \Sigma^*, \mid w \mid \le K\\}$, which for any fixed $K$ is a regular expression again.

But in principle, regexps as specified are more powerful than regular languages, as this related question discusses in much more detail (with a nifty example as well).