Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
797
questions
1
vote
1
answer
40
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 ...
- 45
0
votes
0
answers
16
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
0
votes
0
answers
9
views
RE to NFA conversion JFLAP [closed]
Having this regular expression ((0 + 1)(11)* + 0)* I get this NFA according to me:
I'm trying to compare it with the RE on JFlap and it says it's not equivalent ...
- 1
0
votes
1
answer
19
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'...
- 1
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?
- 1
3
votes
0
answers
49
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,268
1
vote
1
answer
32
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 ...
- 15
0
votes
1
answer
43
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
51
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
33
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
45
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
36
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
36
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
40
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
1
answer
58
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
21
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
26
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:\...
0
votes
1
answer
49
views
Context Free Grammar Advantages
I am currently learning about context-free grammar, however, I am confused as to why context-free grammar is used over regular languages(Regular expression) and what makes CFG more powerful. Even ...
- 11
1
vote
1
answer
39
views
Check whether a regular expression is correct
I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct?
...
D.W.♦
- 150k
-5
votes
1
answer
75
views
regex for {w ϵ {a,b}*: |w| mod 3 =0}
I think this is what the regular expression would be. (aaa U aab U aba U abb U baa U bab U bba U bbb)*
- 1
0
votes
1
answer
34
views
Regular grammar such that it rejects keywords
I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable.
Def: A variable can be any combination of characters, ...
- 1
4
votes
0
answers
69
views
Inverse operation to concatenation for regular languages
I'm currently in need of the inverse operation of the concatenation of 2 regular languages.
Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
- 103
0
votes
2
answers
67
views
Language to regular expression to prove it is regular
I'm trying to find a regular expression to describe the following language:
$\{a^n xa^n | n≥1,x ∈ Σ^* \}$
where $Σ$ = {a,b}
So far I've come up with
$aa^* (aUb)^* aa^*$
but I don't think that accounts ...
- 103
2
votes
1
answer
35
views
How to prove that for any words $w_1, ..., w_n$ of alphabet $\{0,1\}$ regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
How to prove that for any words $w_1, ..., w_n$ on alphabet $\{0,1\}$ the regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
- 131
0
votes
1
answer
45
views
Asked to write a regular expression for a language but I am confused about the teachers given solution. (all strings NOT ending in 01)
The problem reads as follows:
Write a regular expression for the following language on {0, 1}:
$\bullet$ all strings not ending in 01.
The solution my teacher gave is
(0+1)$^{*}$(00+10+11)+0+1+$\...
- 1
0
votes
1
answer
70
views
1
vote
1
answer
164
views
Regular Expression Equality
I am wondering about this small question, why aren't these regular expressions equal?
$(a+b)^* a^*$ and $(a^* b)^* a^*$
1
vote
1
answer
48
views
Regular expressions cannot be used to express context free grammars. Is there a similar notation that can?
Regular expressions are a powerful practical tool for string processing. But there are simple examples of useful string processing tasks (like, say, removing brackets from an expression ...
- 141
0
votes
0
answers
23
views
Regular expression for strings that do not contain the substring $aa$ and contain an even number of $a$'s [duplicate]
I am trying to find the regular expression for the set of strings over the alphabet $\{a,b\}$ that:
do not contain the substring $aa$ and
contain an even number of $a$'s
Such examples include:
$...
- 1
0
votes
1
answer
92
views
How to convert the regular expression $\emptyset^*$ to an NFA?
The question is to convert the following regular expression to an NFA: $\emptyset^*$.
I know that the symbol phi in Theory Of Computation means an empty set. But what does phi^* mean?
0
votes
1
answer
48
views
Regular Language to Regular Expression
Let's assume I have the following regular language:
L = {1,0}*{010}{1,0}*
I would like to convert this to regex for a program. Would the equivalent regular expression for this be:
((0+1)*(010)(0+1)*)
...
9
votes
4
answers
1k
views
Non-regular language whose prefix language is regular but not the whole set of words
I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of ...
- 391
0
votes
0
answers
56
views
proof that there exists a regular expression r for every NFA with only 2 states
Let L be a regular language. Then there exists a regular expression r such that L = L(r).
Proof for NFAs with only 2 states (can be generalized!), partly seen during a lecture and completed by me:
Let ...
- 89
0
votes
1
answer
106
views
Describing the Language of a DFA with 7 States
So in my attempt to convert the following DFA into a regular expression, I ended up with ((ba)*(ab(ab)*)*(aa(ba)*a)*)*. The exercise I'm following wants me to ...
- 13
1
vote
1
answer
46
views
Are both regular expressions correct for the given DFA with three states?
Are both regular expressions correct for the following automaton?
$$(\lambda+ a a^*b(ab)^*)(\lambda + b(a+b)^*)\\
\ \\
(a a^*b)^*(\lambda + b(a+b)^*)$$
The first one is the solution provided by the ...
- 89
0
votes
0
answers
28
views
Power of regex extensions [duplicate]
It is well known that classical regexes recognize exactly regular languages. But in practice, many programming languages have extensions to the regex syntax which potentially broaden the field of ...
- 111
0
votes
2
answers
1k
views
Regex for string does not contain the substring "110"
Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)?
Write a regular expression for the language L = {w | w does not contain 110}
So, the answer I get is: $(...
- 33
0
votes
1
answer
41
views
Confused by Sipser's proof of equivalence of R and NFAs
I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression ...
- 33
0
votes
1
answer
136
views
DFA and NFA with 2 Substrings
I am preparing for my CS exam and found this question in a collection of old exams:
Find a DFA and NFA with Σ = {o,p,q} that checks if the substrings op and pq are present in the string.
I thought, ...
- 113
0
votes
1
answer
68
views
regex find substring matches in text
I have written a regex engine and it can match whole strings to a pattern without a problem, i.e.:
match(E, w)
and it returns ...
- 1
-2
votes
1
answer
51
views
Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?
Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$
Why is $L'$ a regular language?
I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
- 239
4
votes
1
answer
103
views
Are the set of all Bitcoin addresses a context-sensitive language?
This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
- 43
-1
votes
2
answers
1k
views
Regular Expressions with at least 3 b's and at most 2 a's
I am not a Regular Experssion expert, but my request is simple: I need to match any string that has at least 3 characters of B and at most 2 characters of A
so for example:
...
0
votes
1
answer
94
views
How would I design a State Diagram (FSM) for a AC unit?
Ok so I'm learning Finite Automata in my Theory of Computation course and understand the basic FSM but can't wrap my head around this question:
The AC should only turn on if a person is
detected in ...
3
votes
2
answers
1k
views
Length of a regular expression
What is the definition for the length of a regular expression? This question might sound simple, yet I cannot find a definition. Do I only count letters from the alphabet? Do * and $\cup$ count?
For ...
- 43
1
vote
2
answers
291
views
NFA to recognize the language ${ab}$
In Michael Sipser's Introduction to the Theory of Computation, Example 1.56 shows how to convert $\left(\text{ab }\cup\text{ a}\right)^*$ to an NFA. It builds up from the smallest subexpression to ...
- 113
1
vote
1
answer
100
views
Prove that the language of regular expressions is not regular
I want to prove that the language of all regular expressions is not a regular language. I'm having trouble to approach this problem. I thought maybe to show that the parenthesis language is a part of ...
- 11
1
vote
1
answer
574
views
Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?
I understand why L2 is not a regular language. We can use the pumping lemma to prove it
In the case of L2:
assume n = 1 and string = ab
We assume that L2 is regular, so it has "pumping length&...
- 305
3
votes
4
answers
2k
views
What exactly is pumping length in pumping lemma?
Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and
...
- 305
-2
votes
1
answer
55
views
How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?
Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method
I end up with this:
My ...
- 305