Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
864 questions
1
vote
2
answers
42
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 ...
- 73
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
93
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,058
3
votes
1
answer
92
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
427
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
147
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
122
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
81
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
140
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
334
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