Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
864 questions
1 vote
2 answers
48 views
Regularity of Languages $L_1$ and $L_2$
I am analyzing the regularity of the following two languages defined over the alphabet $\Sigma = \{a, b\}$:$$L_1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ \text{ AND } \beta \in \{a, b\}^+ \}...
- 13
0 votes
1 answer
45 views
Regular expression circular definition in Sedgewick's Algorithms 4th ed
In Sedgewick and et al.'s Algorithms 4th ed., I found the following definition for a regular express: A regular expression (RE) is either Empty A single character A regular expression enclosed in ...
- 127
2 votes
0 answers
56 views
Translating star-free $\omega$ -regular expressions to LTL formulae
It's known that LTL formulae describe star-free languages, but is there a good method to translate star-free $\omega$-regular expressions (i.e. expressions of the form $X\cdot Y^\omega$ where $X$ and $...
- 21
-1 votes
1 answer
195 views
Does the "regular" in "regular expression" have the same terminology as the "regular" in "regular language"?
According to this post: Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such as geometric or other analogies ...
- 1
1 vote
0 answers
73 views
Syntactical Difference Between Regular Expressions
Given two regular expressions $r_1, r_2$ such that $r_1 \neq r_2$ but $L(r1) = L(r_2)$, how can I characterize the syntactical difference between them? (Ignoring the order of union that might be ...
- 322
2 votes
1 answer
94 views
Why are the inference rules of Salomaas axiomatization of regular events problematic?
In Salomaa's Jewels of formal language theory, Ch. 2 Exercise 8 asks you to prove the completeness of a system which, after digging around for a bit, turns out to be a result of one of his papers (...
- 2,068
3 votes
1 answer
93 views
Definition of Star Normal Form of Regular Expression
I'm trying to understand the following definition from this paper: I understand that it means that for each starred sub-expression, a letter that can be the first letter in a word generated from this ...
- 322
6 votes
1 answer
428 views
How can you convert a generalized regular expression to a standard regular expression?
Formally, regular expressions only contain the union, concatenation, and star operations. However, regular languages are also closed under intersection and complementation. This means that a ...
- 161
2 votes
1 answer
163 views
Comparison of time complexity for NFA and backtracking implementations of regex search
I followed this helpful blog "Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)" by Russ Cox. This link is got from Russ Cox, ...
- 233
0 votes
1 answer
128 views
Trouble understanding how to convert this NFA to a regular expression
I'm trying to convert the following NFA to a regular expression using the elimination method. To do this, I first eliminated $q_1$, getting the following automaton: Then, starting at $q_0$, I know ...
2 votes
1 answer
80 views
Regular expressions, NFAs, and epsilon loops
It's well-known that you can use NFAs to implement regular expression matching, and that NFAs are distinguished (among other things) by having epsilon transitions that are taken when encountered ...
- 123
0 votes
1 answer
82 views
Epsilon or Lambda Transition Consumption Rules
How do I know when to include the state vs when I've gone too far? Example 1: {Q0,b} -> {Q1,Q3,Q4}. Example 2: {Q3, b} -> {Q1,Q3,Q4} - not sure if this is correct to include Q3, please see the ...
- 1
0 votes
1 answer
101 views
Unix 'find' utility : Question about relation to Kleene Star in Mathematics
Does anyone know how the Unix find search -name queries with _? in leftmost column relate to Kleene Star as defined on Wikipedia?...
- 195
0 votes
2 answers
141 views
How do I prove that this is not regular L = $\{ a^i b^j c^k \mid k = i \times j \text{ and } 0 < i < 10 < j \}$
I made a CFG to prove that it's context-free, however, I wasn't able to convert it to left-linear or right-linear grammar. \begin{align*} S &\to \text{a}^iB \\ B &\to b^{11}Dc^{11\text{x}i}\\ ...
- 11
4 votes
3 answers
338 views
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
The let $L$ be a language. The following are equivalent: $L$ is given by a deterministic or non-deterministic finite accepter. $L$ is given by a regular grammar. $L$ is given by a regular expression. ...
- 207