Are regular languages and their regular expressions part of computer science?

Question

I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular.

In math discourse there was always the question like "Are mathematics discovered or invented?".
I am quite sure regel-regex is not a mathematical theory but a linguistics theory (even though it was first theorized by a mathematician - Stephen Cole Kleene).

Is regex part of computer science and if so, is it generally accepted as "discovered" or as "invented", and what could be one example of what's being further researched in regards to matching information on a computer document?

Answer 1

There are several things that are all called regular expressions. The answer to your question is different depending upon which thing you want to talk about.

The three relevant distinctions for this question in my opinion are as follows:

First

The notion of regular languages and related things like recursive enumerability.

Individual regular languages are isomorphic, (i.e. able to be losslessly transformed to and from,) to deterministic finite automata and reducing something to a regular language demonstrate results about that thing's computablity, so I would argue it is part of computing science.

If linguistics folks find the notion or regular languages useful, however, then we can share it. Human languages are (generally?) not regular languages but something more complex, so I would be surprised if that was the case.

I think most interested people would give the same answer to whether regular languages are invented or discovered as they would about mathematics.

Second

The particular notation for describing regular languages, in the formal literature, developed by Kleene and others.

This is clearly invented. There's no particular reason we have to have used * and + in particular to represent those ideas. If you want to assign this notation to one or more fields, I would argue it belongs to any field that publishes papers using it.

Third

Computer programs which take as input an expression in a language and produce an automata or something resembling one and that result can then be used to perform operations on a different input including search and replace.

The languages these programs define which usually contains some form of the Kleene Star and Kleene Plus, along with several other more complicated but useful constructions, which are generally absent from formal regular language literature to my knowledge. Backreferences would be one example of this. These programs are invented, as are their particular sets of notations. They are also instances of computer engineering rather than computing science per se. Although of course they are building on at least a certain amount of computing science results, and computing science results can be stated about these programs. For example, it is possible to construct regular expressions of this sort that produce exponential running times, and subsets of those notations can be defined where that is impossible.

Answer 2

Regular expressions are at the very core of computer science, conceptually and historically.

Kleene's article in which he introduced them and proved them equal in power to finite automata is one of the foundational articles of computer science. It was the foundation of formal language theory, which was based on its results and its approach; it is an important branch of computer science, a rich body of strictly mathematical theory, the basics of which are taught in all computer science curricula, including the theory of regular expressions. It is devoted to the subject of parsing input, one of the essential problems to address when programming. The techniques we use daily to parse text, both natural language and computer languages, are based on this theory - they may deviate from it, but we need basic insight into the theory in order to know which parsing techniques to apply when.

So yes, regular expressions are a prime example of what computer science is about.

Historically, they were developed in the context of cybernetics and the quest for artificial intelligence: mathematicians at MIT and elsewhere were studying formalisms such as state machines and neural networks, which could exhibit interesting behavior and do such things as recognize patterns of input stimuli. This is why Kleene's article speaks of nerve nets and the recognition of events (stimuli to the net).

However, the same techniques were applied to the recognition of written natural language; e.g. people such as Noam Chomsky were working on machine translation; they were hoping to create computer systems that could take a Russian text and translate it into English, or vice versa. Chomsky realized that regular expressions weren't powerful enough to describe human language, that the grammars used in linguistics have more descriptive power; this led to the development of the formal (mathematical) theory of grammars and the rest of formal language theory, which were subsequently employed in linguistics (by followers of Chomsky) and in computer science and the daily practice of IT (by all programmers who need to parse input).

Answer 3

Honestly, I don't think the "discovered" vs "invented" is a distinction that matters. If you want to get into that, fine, but it's a matter of philosophy, not science.

To your main point, yes, regular languages are very much a part of computer science because, regardless of their history, they identify a class of computational problems and correspond to a class of computational machines (finite automata). They are also a part of mathematics and of linguistics.

The entire field of information retrieval deals with matching information in text documents.