patternMinor
Are regular languages and their regular expressions part of computer science?
Viewed 0 times
sciencearelanguagespartregularexpressionscomputerandtheir
Problem
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?
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?
Solution
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
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.
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.
Context
StackExchange Computer Science Q#116985, answer score: 6
Revisions (0)
No revisions yet.