Regular Languages Are … well … Regular

Home » Blog » Software » Regular Languages Are … well … Regular

A few weeks ago I came across an article describing “A regular expression to check for prime numbers“. I was intrigued because processes defined by formal regular languages have an inherently linear runtime while the process described is non-linear. This contradicts the definition of regular languages, specifically the Pumping Lemma.

So, how is this even possible? Well, the regular expression discussed in this article and the regex framework it’s used with makes clever use of backtracking for realizing this ‘magic’.

Quite simply, the languages used by common regular expression frameworks aren’t exactly regular but rather context-free through features such as backtracking and backreferencing. So, however nifty and in some cases useful such seemingly magical usages of regular expressions are you might still want to consider using another, more appropriate tool for solving problems that show non-linear behaviour – the most notorious one probably being parsing HTML.

Leave a Comment

* Checkbox GDPR is required

*

I agree

By continuing to browse the site you agree to our use of cookies. Privacy Policy

Privacy Preference Center

Strictly necessary

These cookies are necessary for the site to function.

PHPSESSID: Preserves user session state across page requests.

__cfduid: Used by the content network, Cloudflare, to identify trusted web traffic.

PHPSESSID
__cfduid

Preferences

Remembers the user's submitted data when a comment is submitted in a blog post. The purpose is to aut o-populate form fields for subsequent comments, in order to save time for the user.

wfvt_#

Statistics

Statistic cookies help us to understand how visitors interact with our websites by collecting and reporting information anonymously.

_ga: Registers a unique ID that is used to generate statistical data on how the visitor uses the website.

_gat: Used by Google Analytics to throttle request rate.

_gid: Registers a unique ID that is used to generate statistical data on how the visitor uses the website.

collect: Used to send data to Google Analytics about the visitor's device and behaviour. Tracks the visitor across d evices and marketing channels.

_ga,_gat,_gid
collect

Security

We use Wordfence to secure our website against hacking attempts: https://www.wordfence.com/

wordfence_verifiedHuman

Close your account?

Your account will be closed and all data will be permanently deleted and cannot be recovered. Are you sure?