Questions tagged [regular-expressions]

Questions about regular expressions, a formalism to describe regular languages.

46 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
90 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
5
votes
0answers
209 views

How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
4
votes
0answers
553 views

Distinguishing probabilistic, deterministic, and fuzzy matching methods

I have two datasets that I am trying to match to one another. One dataset's contents is a subset of the other, but contains typographical errors of varying types and magnitude. I am applying the ...
3
votes
0answers
100 views

Algorithms to match regular expressions containing backreferences

I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like: ([a-c])x\1 which would match ...
2
votes
0answers
23 views

Regex NFA construction: Why use Glushkov over Thompson? Pros/Cons

In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs? I understand the difference between them, and can follow the ...
2
votes
0answers
30 views

Transform Double Metaphone code into regex

I am using hyperscan to search through large texts for a lot of regexes. One addition should be selective phonetic search for individual words. The algorithm of choice is Double Metaphone (but please ...
2
votes
1answer
215 views

How do I convert the following GNFA to regular expression?

Here is a GNFA I made from an NFA. I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it ...
2
votes
0answers
82 views

Which transducer models replacement in regex?

I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order. For example: ABC => CAB, which, with ...
2
votes
0answers
243 views

What is a regular expression for solutions to the dog/cat/mouse river crossing puzzle?

This is a question that's been bugging me off and on for years, ever since I took a compiler theory class as an undergraduate. There, we learned how to convert a regular expression into a non-...
2
votes
0answers
347 views

Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
2
votes
0answers
47 views

Effectively compute bound and period of regular expression on single alphabet

It is known that an infinite language $L\subseteq \{a\}^*$ is regular iff the set $U:=\{x|a^x\in L\}$ is ultimately periodic. (A set $U\subseteq\mathbb{N}$ is said to be ultimately periodic if there ...
2
votes
0answers
91 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
1
vote
0answers
65 views

Extending Thompson's NFA algorithm with backreferences

I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is ...
1
vote
0answers
152 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
1
vote
1answer
66 views

Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $\equiv_L$ has infinite index. $\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0} My ideas: theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
1
vote
0answers
407 views

How can I find worst time complexity for a Regular Expression problem?

I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution? One way is to perhaps use The Master Method for ...
1
vote
0answers
19 views

Pseudo-random regex-searchable function

Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties: $f$ is efficiently ...
1
vote
0answers
52 views

Regular Expression Metric space

With Levenshtein distance we can create a metric space over string. Is there are any distance metrics for regular expressions?
1
vote
0answers
111 views

What is the correct regular expression for this language?

Consider the following problem: $L$ is the language of regular expression $00^*11^*$. $DM(L)$ is the language obtained from $L$ by throwing away every even-length string belonging to it and for each ...
1
vote
0answers
143 views

Regexp substitution and finite-state transducers

Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, ...
1
vote
0answers
91 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(aa)?(aa) and I convert it to a grammar: G ::= A B A ::= C | (...
0
votes
1answer
13 views

Lexicographic Order of Expression [Automata Theory]

what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order? I'm confused and I really want to clear my concepts so I can proceed further
0
votes
0answers
22 views

Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
0
votes
0answers
45 views

Regex to match number ranges less than a certain number

I'm trying to write some code to match numbers below certain bounds. I would much appreciate nay help somebody could give, I'm pretty lost with this one... NB. I've checked the forums and can find ...
0
votes
0answers
49 views

How generate regular expression on the alphabet {a,b}?

How can I write a regular expression that denotes language on the alphabet {a,b} of the strings that do not present "b" consecutive and the total number of "a" is multiple of three?.
0
votes
0answers
42 views

What is the best algorithm known to learn the regular expression from a set of positive examples?

I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I ...
0
votes
0answers
45 views

Returning all the combinations of a string using regex

Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches? For example, if the string is ...
0
votes
1answer
29 views

Product of Lexical Specification

I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc. The options are: ...
0
votes
0answers
59 views

How use generalized suffix tree to match prefix string?

I know that generalized suffix tree can match substring for a given pattern. But I have need a data structure which is able to match prefix of many strings. match sub string of of many strings. For ...
0
votes
0answers
23 views

Formal Class of Languages Describable by .NET Regular Expressions

This is sort of a computer science question and sort of a programming question. What is the name of the formal class of languages that can be described by .NET regular expressions (assuming it a well ...
0
votes
1answer
878 views

How to convert DFA to regex with State Elimination

I can do the very simple transitions but it gets difficult when you have transitions jumping over 1 or more states. I have this difficult DFA i need help converting to RE: using STATE ELIMINATION ...
0
votes
0answers
66 views

Validating attempt on NFA to Regular Expression

So i tried turning the following NFA into a GNFA (first attempt). Please don't ask why i chose to do such a complex NFA on my first try, i just like the challenge i guess? ab is the concatenation of ...
0
votes
0answers
138 views

Operations on regular languages

I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language ...
0
votes
0answers
139 views

Tool for NFA/DFA manipulation

I am look for a tool with any or all of the following features: Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams NFA to DFA converter NFA minimization NFA ...
0
votes
0answers
62 views

Empty words in regular languages

Let $L_1,L_2$ be any $\Sigma$-Languages, with $l_1\in L_1, l_2\in L_2$ If I have a regular Language $L(l_1(l_2l_1)^*l_2)$ would the word $\omega=l_2$ be recognized? I'm confused because if $\epsilon \...
0
votes
0answers
51 views

Recurrence relation for a star and a dot wildchar pattern

. Matches any single character, * Matches any sequence of characters (including the empty sequence). dict = ["cat", "cats", "...
0
votes
0answers
135 views

Simplification of regular expressions

$(0+1)^*.1.(0+1) + (0+1)^*.1.(0+1)$ and $(((0^*.1^*)+1)^*(0+1)^*)^*$ I have studied Arden's theorem $R=Q+RP$ has a unique solution $R=QP^*$ and some identities like $E+RR=R$ and $E.R=R$. I have ...
0
votes
0answers
112 views

Find a minimal regular expression for the languge of the words that does not contain bbb

Let's say my dictionary is {a,b} I want to ccind a regular expression for the languge of the words that does not contain bbb in the most minimal way. All I can think about is '+'ing between prefixes ...
-1
votes
1answer
40 views

Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?

Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
-1
votes
1answer
17 views

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$ sigma is any alphabet. R is a regular expression. How can L(RR) even be a subset or equal to L(R)?
-1
votes
1answer
46 views

Regular Expression Building

I'm having trouble constructing a regular expression to meet the following criteria: $$\sum = \{0,1\}$$ $$\epsilon \in L$$ $$0 \in L$$ $$1 \in L$$ $$\forall x \in L, 110x \in L \land x01 \in L$$ ...
-1
votes
1answer
321 views

Recursion problem to see if string fits in given pattern

If you are given a pattern and a string, check recursively if the string fits in the pattern. The given pattern will be like "dooo?g*a". A question mark can be replaced with one character and asterisk ...
-2
votes
1answer
261 views

Kleene star of L

$L^*$ is the kleene star of L. say we have a def: $L^*$ = $L^0$ U $L^1$ U $L^2$ U ... U $L^K$ then prove that: $L^*$ = $L$ if and only if $L$ = $L$ o $L$ how do i prove this?
-2
votes
1answer
892 views

Convert regular expression to FA?

I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba) I need help to draw the second part L((ab)*ba). I know the shortest string ...
-2
votes
1answer
9k views

Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
-3
votes
2answers
368 views

DFA accept 00 as a substring

How can design this question if we have an equation like that ={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for ...