Why don't regular expression engines support all set operations?
Similar to this question on a private forum: Why don’t RegEx implementations support intersection and complement?
Finite automatas built from regular expressions are closed under the set operations union, intersection, complement, and difference. These FA are closed under the two additional operations concatenation and Kleene star.
Anecdotally, concatenation, union, and star operations are ubiquitous in regular expression implementations. Why don't regular expression engines typically support the other set operations intersection, complement, and difference?
An example FA demonstrating the intersection of the two FA substring 01 and odd number of 1s from these lecture notes.
Citation:
Scott Aaronson. 6.045J Automata, Computability, and Complexity. Spring 2011. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Regex engines that support lookarounds let you implement intersection, complement and difference :
(?=pattern1)pattern2will match a string that both pattern1 and pattern2 match(?!pattern).*will match anything that isn't matched by pattern (although more realistically you'd usepatternas a regex and have your higher-level environment reverse the match result)(?!pattern1)pattern2will match a string that is matched by pattern2 but not by pattern1
However lookarounds are a rather recent feature in the history of regular expressions and still aren't supported by many regex engines. Why is that?
I'm not well versed in regex's history, but if I believe a cursory glance at Wikipedia articles, they originate from mathematician Stephen Cole Kleene's definition of regular languages which is only based on the union, concatenation and Kleene star operations, which might explain why those are the basic operations in regular expressions.
- Rcpp Rf_warningcall compiler warnings
- Modify the name of factor variables in lm function(summary function)
- Extreme value analysis and quantile estimation using log Pearson type 3 (Pearson III) distribution - R vs Python
- How to hide NAs when using xlsx::saveWorkbook?
- How do I retrieve a simple numeric value from a named numeric vector in R?
- Matching pair-wise columns from left to right across rows in one dataframe to another dataframe and adding new columns with matching values
- Income to outcome flow chart in Sankey plotly R
- color mapping in geom_conn_bundle not showing correctly
- Print R package startup message AFTER automatic package conflict messages instead of before
- Summing a set of R dataframe rows (column-wise), while retaining the first n columns
- Added variable / partial regression plots for groups in an interaction?
- how to make a topoplot in R with coordinates variable distribution
- List of all functions in base R?
- Plotting multiple plots for different initial conditions in one graph
- Printing repetitively on the same line in R
- Generating UI/Server based on initial selection
- Subset dataframe based on pickerInput
- How to let user pick the data in R-shiny?
- Couldn't show my simple bar charts separately on Shiny R dashboardBody
- How to programmatically filter contents of a second shiny app displayed via iframe
- How to select specific interesting groups for the boxplot in R Shiny app?
- Crosstable and Plot grouping with reactive values
- Is there a way to make multiple Shiny picker inputs where the selections must be disjoint?
- Delay/avoid duplication of shiny server side functions until after credentials
- Predictions only returns value "1"
- How to display a busy indicator in a shiny app?
- Append doesn't work when writing to CSV in R
- Changing the start date of a gantt chart in DiagrammeR
- Check for installed packages before running install.packages()
- Compare two columns element-wise