Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
829
questions
-5
votes
0
answers
17
views
DFA testing exercice ASAP please [duplicate]
I have a question :
If my word can be only AA or BB or A or B how i will write my regular expression ?
And if 0 is a par number it also may be to include ?
it is something like this : A|B|epsilon) (AA|...
0
votes
1
answer
73
views
Formally Verify if a Sequence of Regex-Based Modifications is Idempotent
I'm performing a sequence of text formatting using regex in Python.
I'm curious to know if it's possible to formally verify whether a single (or a sequence of) regex modification(s) is idempotent, ...
- 111
0
votes
1
answer
27
views
How does a regular expression match `.+x`?
A quick test shows what I'm describing:
> const text = 'foobarhelloworld'
> const pattern = /.+or/
> text.match(pattern) //=> 'foobarhellowor'
What is ...
- 2,163
0
votes
0
answers
27
views
What is the minimum length word accepted by the product of these simple loop automata?
Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
- 495
0
votes
1
answer
56
views
Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'
I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like:
After a lot of ...
0
votes
1
answer
56
views
Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?
So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
0
votes
0
answers
39
views
Binary combinatorics with rank
I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values).
Also, I want to rank and unrank these subset of values (in ...
- 23
0
votes
1
answer
42
views
Regular expression for binary string containing no instances of 01
In order to enumerate such a regular expression, it's clear one can break down the language into the set $s =\{00,01,10,11\}$ and it is clear that we need to enumerate some expression that avoids the ...
0
votes
1
answer
38
views
How to simplify this regular expression?
How do i prove that the regular expression $$a^*(ba^*)^*$$ is the same as $$(a+b)^*$$. Is there a way to prove this using regular expression identities?
- 1
-4
votes
1
answer
54
views
For each of the following languages, give a regular expression over {a, b}
$\{a^{2n}b^{n+k+1}a^k ∈ \{a, b\}^∗ \mid n \ge 0, k \ge 0\}$
0
votes
0
answers
28
views
Prove the language $a^n b^m$ where $m$ is a multiple of $n$ is not regular
Consider the problem
Show $L = \{ a^{n}b^{m}\mid m \text{ es múltiplo de } n \}$ is not regular.
I attempted the following.
Assume $L$ is regular. Then there is a natural number $p \geq 1$ such ...
- 181
0
votes
1
answer
37
views
The language of chains with twice as many $a$s as $b$s is regular?
I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem:
Let $L$ be the language of all words that ...
- 181
0
votes
0
answers
64
views
Regular expression over $\{a, b\}$ for all words with an even number of $a$s, but without consecutive $a$s
I was given the following problem.
Problem. Give a regular expression over $\{a, b\}$ whose language is the set of all words with an even number of $a$s, but without consecutive $a$s. For example, $...
- 181
0
votes
0
answers
37
views
Finding a DFA with same language as given $\epsilon$-NFA
Consider the following automaton.
How does one find a DFA with an equivalent language using an algorithm? In particular, I was requested to use the algorithm described in the answer to this question. ...
- 181
0
votes
0
answers
29
views
Regular expression - Find the equivalence classes of Nerode theorem
Find the equivalence classes of a nerode theorem and use equivalence
classes to construct a reduced DFA for the following language:
$𝑎^+(𝑏+𝜀)𝑐^*$
The answer:
$𝜀,𝑎^+,𝑎^+𝑏𝑐^∗+𝑎^+𝑐^+,(𝑏+𝑐)Σ^...
1
vote
1
answer
20
views
Meaning/veracity of "each state has [..] or two outgoing ϵ transitions" in Thompson's construction
The dragon book lists properties of an NFA N(r) created using Thompson's construction, in particular:
Each state of N(r) other than the accepting state has either one outgoing transition on a symbol ...
3
votes
1
answer
454
views
Prove or disprove that two regular languages are equivalent
I have $L_1=\{b^*+b^*a(b+ab^*a)^*ab^*\}$ and $L_2=\{(b^*ab^*a)^*b^*\}$. I want to prove or disprove that they are equivalent.
I have proved that $L_2\subseteq L_1$ and I tried to transform the second ...
1
vote
0
answers
51
views
Regex to DFA - How do I implement parsing preferences in regex search?
I've tried a to implement a Regex to DFA converter, and it works, so far, but I don't understand how to implement "parsing preferences" in the DFA.
A classic example is $a^*$. This regex is ...
- 111
0
votes
0
answers
22
views
How does tokenization relates to formalism, lexical grammar, and regular language?
I am reading Bob Nystrom Crafting Compiler's and in the chapter 5 it says this
In the last chapter, the formalism we used for defining the lexical grammar—
the rules for how characters get grouped ...
- 145
0
votes
0
answers
29
views
Why are ] and } not considered special characters?
Reading the manual for GNU grep, the special characters (with -E option) are .?*+{|()[\^$.
This is a somewhat pedantic question, but why are ...
- 115
0
votes
0
answers
14
views
What algrorithm computes a mutally exclusive partitioning from two regulair expressions?
The Question
A regular expression, such as AL+[EYI]+, represents a set of strings.
...
1
vote
0
answers
19
views
Errors in examples of Vardi's paper "Linear Temporal Logic and Linear Dynamic Logic on Finite Traces"
The paper Linear Temporal Logic and Linear Dynamic Logic on Finite Traces has the following examples on page 4:
Q1. (Update to Q1: solved. See the comment by DCTLib.) The first example says that the ...
- 1,055
0
votes
2
answers
139
views
Empty regular expression
When my professor introduced regular expressions, he said that the empty string is the simplest regular expression, where it matches everything. How can this be true? I would think the empty string ...
- 171
0
votes
0
answers
50
views
Removing null production from cfg
While removing null production from cfg as below,
S->ABC
A->aA|^
B->bB|^
C->aaC|^
now as shown above we know that A,B and C all are ...
0
votes
0
answers
67
views
Help with converting the DFA to a regular expression using Ardens theorem
Can someone explain to me how to convert this DFA to a regular expression? I have tried using Arden’s theorem but I don’t know how to simplify the equations to get the regular expression for this DFA. ...
0
votes
1
answer
68
views
Check if these 2 regular expressions are equivalent
Check if these 2 regular expressions are equivalent:
$R_1 = (a+b)^*(aa+bb)$
$R_2 = (a+b)^*aa+a^*bb+b^+b$
My approach:
We check if both of these expressions generate the same set of strings. Meaning ...
0
votes
1
answer
52
views
Let $L$ the language over $\{a,b\}$ of words that contains the same number of occurrences of $a$ and $b$. Which of the following languages is regular?
The options are:
(a) $L \cap a^{\ast}b^{\ast}$
(b) $(L \cap a^{\ast}b^{\ast}) \cup a^{\ast}b^{\ast}$
(c) $L \cup a^{\ast}b^{\ast}$
(d) $(L \cap a^{\ast}b^{\ast}) \cup b^{\ast}a^{\ast}$
My doubt is: We ...
- 305
0
votes
1
answer
26
views
What algorithm accepts a set of strings as input and outputs a regex of minimal size?
We seek an algorithm.
Inputs to the algorithm are a set of strings $A$ and the output of the algorithm $A$ is a regular expression $r$ such that:
The size of regular expression $r$ is minimized.
If $...
0
votes
0
answers
63
views
What algorithm will convert a regex into a tree of predictable size?
How do we quantify the size of a regular expression?
A problem in computer science which sometimes arises is converting a regular expression into a tree.
What rules can we use to ensure that the tree ...
0
votes
0
answers
21
views
How do you minimize the number of nodes in the tree associated with a regulair expression?
Generalization of the Problem
What algorithm solves the optimization problem of minimizing the size of a tree associated with a regular expression?
We use the word tree in way graph theorist talk ...
2
votes
1
answer
137
views
Is there a algorithm to determine if a regular language (expression) is subset of another?
Given two regular languages (fx given by it's accepting regular expression), is there an algorithm to determine if one is a subset of the other?
- 123
1
vote
1
answer
36
views
How do you convert a string representing a finite set of strings into a regulair expression without using lots of vertical bars?
Consider the following string:
...
0
votes
0
answers
77
views
How to prove (L+M)* = M*.(L.M*)*
Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
- 67
0
votes
1
answer
63
views
Simplifying regex expression (L+M*)*
To simplify it, it seems that we can do $(L+M^*)^* = (L+M)^*$, but I also need to prove it.$(L+M)^* ⊆ (L+M^*)^*$ seems straight forward. However, $(L+M^*)^* ⊆ (L+M)^*$ is what I couldn't figure out. ...
- 67
2
votes
1
answer
103
views
Regex where all strings containing an even number of 0's:
Question is to construct a regex where all strings containing an even number of 0's:
By constructing DFA graphically, it is
$$(1^*+01^*0)^* $$
But it is also
$$1^*(01^*01^*)^*$$
Can we prove that they ...
- 67
0
votes
0
answers
56
views
When converting a "empty string" regular expression to finite automata, are FA with 2 states vs 1 state equivalent?
Let's say we have a regular expression, R = $ε$. If we wanted to convert this to finite automata ( NFA or DFA ) which of the following would we use?
Have 2 states: q0 ( start state ) and q1 ( accept ...
- 305
1
vote
1
answer
467
views
Regular Expression of {w : w contains an even number of 0s and exactly two 1s}
I know the answer if it was OR would be (1*01*01*)* U 0*10*10*, but with the AND I have no clue how this can be achieved. There are lot's concatenations that I can'...
- 11
0
votes
0
answers
10
views
Regular Expression of {w : w contains exactly two 0s and at least two 1s} [duplicate]
I have this 1^*011^*011^* and haven't been able to think of it differently. Can you please help me see how I can get this input 0011 and 1100 correct?
- 11
3
votes
0
answers
52
views
Reference request about equivalence of automata / regular expressions up-to a language
The most widely used notion of equivalence of regular expressions
$r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
- 8,308
1
vote
1
answer
35
views
Is it true that $R.L^* + L^* = R + L^*$?
I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^* + L^*$ in the end which I am not sure how to simplify further.
I want to ...
- 115
0
votes
1
answer
56
views
Algorithm to determine the regularity of a language
According to the answer provided by Janoma, there are several methods to determine the regularity of a language.
Theorem
Let L ⊆ Σ∗. The following conditions are equivalent:
L is generated by a ...
0
votes
0
answers
75
views
What is a regular expression that describes whether an integer w is a multiple of 6?
Let's say we are looking at the decimal language $L_6$ where $$\Sigma = \{ 0,1,2,3,4,5,6,7,8,9 \}$$ and $L_6$ accepts an integer w if w is a multiple of 6. I'm trying to find the regular expression ...
0
votes
0
answers
99
views
How does the regular expression '^(a+)+$' lead to this specific NFA?
OWAPS has an article on ReDoS (archived).
In it, they use the regular expression ^(a+)+$ as an example for ReDoS vulnerabilities.
They provide this illustration of ...
- 101
1
vote
0
answers
55
views
What is the formal definition of a combinational logic?
Question Background
A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35):
The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
- 111
0
votes
1
answer
49
views
Convert regex for comma separated value to CFG grammar
I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
0
votes
1
answer
43
views
When converting DFA/NFA to regular expression, where the DFA/NFA accepted empty string, is it okay to not have empty string as kleene star?
Let's say that we have a DFA, where the initial state was also the accept state. Meaning the DFA accepts the "empty string". Now, let's say that we convert the DFA to regular expression $R$, ...
- 305
0
votes
1
answer
45
views
Does every regular expression describe only 1 language?
If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it
Also, $...
- 305
0
votes
3
answers
91
views
Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*
I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem:
Since, we have 3 accepting states, we would find 3 ...
- 305
0
votes
0
answers
23
views
How to reduce this regular expression: a* + a*bb* + a*bb*cc* + a*cc*?
I know minimizing regular expressions is PSPACE-HARD but we can still use identities to minimize regular expression. I can tell the reduced version of this would be a* b* c* by looking at the NFA, my ...
- 305
0
votes
1
answer
32
views
How to make a recursive definition for a given predicate?
I have the following predicate: $empty(r)\Leftrightarrow L(r)=\emptyset.$ Now I am given the following regular expressions where $e, f$ are any regular expression:
$r=\emptyset$
$r=\varepsilon$
$r=a:\...
- 105