Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
769
questions
0
votes
2
answers
29
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: $(...
- 3
0
votes
1
answer
29
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 ...
- 3
0
votes
1
answer
44
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
46
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
45
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 ...
- 241
4
votes
1
answer
98
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
58
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:
...
- 11
0
votes
1
answer
58
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
49
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
78
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
47
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&...
2
votes
4
answers
281
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
...
-2
votes
1
answer
32
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 ...
1
vote
1
answer
39
views
Converting Regular Expression to Finite Automata
I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, ...
1
vote
1
answer
60
views
Converting Deterministic Finite Automata to Regular Expression
I am reading Michael Sipser's "Theory of Computation". In one of the proofs he talks about converting "DFA to Regular Expression" and he talks about "GNFAs". I understand ...
1
vote
2
answers
91
views
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's.
So far, I have $(aa)^*a((b+\varepsilon)(aa)^*)^4$, but I don't think this ...
- 11
13
votes
4
answers
2k
views
Proving Equivalence of Two Regular Expressions
Consider the regular expressions
$(1+01)^*(0+\epsilon)$
$(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$,
where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
- 233
0
votes
1
answer
66
views
Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$
Here, $Σ=\{a,b\}$ The number of $a$ can be $1, 4, 7, 10.....$, also $a$ can be placed anywhere.
Find Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$
How can ...
- 9
3
votes
1
answer
77
views
What is the formalism used to describe optional arguments called?
Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example:
foo [opt1[opt2...]] req1 req2 [opt3...]
...
1
vote
1
answer
36
views
How does + symbol works in regular expression?
What's the difference between $a^*+b^*$ and $(a+b)^*$?
I was going through this question. So according to the question-:
(a+b)* generates $\in$, a,b,ab,ba,aa,ba,...
whereas a*+b* generates $\in$, ...
- 13
1
vote
2
answers
166
views
Regular expression for all strings not containing $aba$
This is my first post here. We are currently studying regular expressions, and I have been tasked to write a regular expression for the language of all words which do not contain the substring $aba$, ...
- 155
1
vote
0
answers
44
views
Multithreaded Regex?
I once had an idea for a multithreaded regex engine.
The first method that occured to me (there may be other ways to do it that I haven't thought of) was to split up the string being matched against ...
- 123
0
votes
0
answers
21
views
Prove that the problem of REGEX producing strings with 111 as substring is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given <...
- 17
1
vote
1
answer
60
views
Showing that for every NFA with n states, there is a regular expression of length $O(2^n)$
Consider the idea of an extended non-deterministic automation, where transitions can be
labelled by regular expressions and not simply by symbols of the input alphabet or $\epsilon$. Such
an automaton ...
- 379
1
vote
2
answers
24
views
Construct a regular expression for a specified language
Let $\Sigma = \{a, b\}$ I need to find a regular expression for this language:
The language where the number of $a$'s and $b$'s is equal and for every prefix of a word the absolute value of the ...
- 241
0
votes
1
answer
45
views
Finding an algorithm that decides given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$
Find an algorithm that decides, given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$.
I know that regular expressions are closed under ...
- 379
0
votes
1
answer
96
views
What is the language of this simple DFA with 4 states?
I wanted to say that the language is the set of strings that end with "101" but unfortunately it does not work. Take for example "110101",
which is not accept by the dfa.
- 111
0
votes
0
answers
34
views
Exercises on regular languages
I wanted to know if any of you have a regular language workbook or site. I would need to train on exercises like this:
Y = {w ∈ {a, b} ∗ | w = a2 ^ i b ^2j + 1, i, j> 0}
Y = {0 ^ n 1 ^ m | nm <6 ...
- 1
2
votes
2
answers
69
views
having trouble understanding the proof of regular expression identities $(u + v)^* = (u^*v)^*u^*$
I am having trouble understanding the proof given below:
\begin{align}
(u \cup v)^* &= (u^* \cup v)^* \\ &= u^*(u \cup v)^* = (u\cup vu^*)^* \\ &= (u^*v^*)^* = u^*(vu^*)^* \\ &= (u^*v)...
1
vote
1
answer
421
views
Regular Expression for Grammar = ({X, Y, Z}, {a, b}, X, {X → aY | bZ, Y → b | bZ, Z → a | aY})
2nd year college student here, I have trouble finding for the regular expression for that grammar, any help would help :D
Regular Language of the grammar:
X → aY → ab
X → bZ → ba
X → aY → abZ → aba
X ...
- 11
1
vote
1
answer
67
views
Regular expressions and equivalence classes
I need a little help regarding this problem:
Let L = {w ∈ {0, 1} ∗ : w has an even number of 0s and the last character of w is a 1}. Give the equivalence classes of the relation ≡L using regular ...
- 13
0
votes
2
answers
45
views
Every non-regular language has a subset which is a regular language?
Could anyone give me a counterexample so as to understand the proof? Thanks in advance
- 1
2
votes
0
answers
42
views
Translating weighted regular expressions with the complement operator to weighted deterministic automata
I want to implement regexp search via translation to deterministic automata, as a toy project.
TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
- 83
-2
votes
1
answer
98
views
Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*
I think it's a regular language but I can't find a DFA or a regular expression. Would anyone know how to help me?
- 1
1
vote
1
answer
119
views
Regular expression of binary strings not containing $1011$ or $1101$ as substring
I tried to solve by explicitly writing strings of length $2$, $3$ and $4$ (other than $1011$ and $1101$), but it creates a lengthy regular expression. Can someone suggests underlying pattern that ...
- 111
1
vote
1
answer
155
views
How do I find the regular expression for- All binary numbers greater than 110011
I am trying to solve a problem set to practice for an exam. How can I approach questions like these ? Is there a way to verify solutions or is it just trial and error ?
- 111
0
votes
1
answer
48
views
What could be possible NFA for the RegEx "a?"
I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$
I am wondering if I should deconstruct the RegEx as -
Concatenation of $a+$, $(b|c?)$ together with $c$ OR
...
0
votes
0
answers
42
views
Regex AST to NFA construction
I have written a parser for a regular expression using this grammar and it outputs an AST (abstract-syntax-tree). My goal is to create an equivalent DFA given the Regex AST which can be used to ...
- 129
0
votes
0
answers
7
views
CONVERTING NFA TO RE [duplicate]
How do I obtain the regular expression of this NFA?
I have only done exercises where I obtain the RA from NFAs with only two states or when the third state is an accepting state and I simply follow ...
- 1
-1
votes
2
answers
90
views
Convert ((ba ∪ ab)∗ ∪ b)* to NFA
How do I simplify this $((ba \cup ab)^∗ \cup b)^*$? I can draw the NFA for the '$ba$', '$ab$' and '$b$' term but when it comes to linking the '$ba \cup ab$' to the '$)^∗ \cup b)^*$' i am unsure how ...
- 1
0
votes
0
answers
19
views
How ot prove a language is regular using L′ = {ab(^i)c)^i) | i ≥ 0
I have the following language
L = {a(^i)b(^j)c(^k) | i, j, k ≥ 0, and, if i = 1 then j = k} .
How do I use the fact that L′ = {ab(^i)c)^i) | i ≥ 0 to prove that is it not regular?
I am given a hint ...
- 1
-1
votes
1
answer
30
views
Lexical analysis on a series of tokens given regexes
I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct.
...
- 1
4
votes
0
answers
135
views
Regular languages for which star height is not increased by complementation
The set of (non-generalized) regular expressions over an alphabet $\Sigma$ is the set of expressions generated by the following grammar, where $a\in \Sigma$ ranges over symbols in the alphabet:
$$
\pi ...
- 41
1
vote
0
answers
10
views
Contiguous-substring operator
If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
- 11
0
votes
0
answers
58
views
Decidability of the language of a regular expression being a subset of a given context free language
Let L be a language of pairs $\langle R,G\rangle$, with the first element being a regex and the second being a CFG.
Is it decidable that G accepts whatever the regular expression does? In other words, ...
- 11
2
votes
1
answer
102
views
Is regex with lookaround still regular?
It is well known that "regex" with back-reference is not a regular expression anymore.
For instance, (.*)\1 matches any string repeated twice.
However, is ...
- 121
0
votes
1
answer
82
views
Simplifying regular expression
I'm having trouble understanding the simplification of the following regular expression
\begin{align}
R = ε | 1 | (ε | 1)(ε | 1)^*(ε | 1) = 1^*
\end{align}
In my lectures only the simplified solution ...
- 11
10
votes
1
answer
594
views
What is the correct way to draw NFA of RE (a|b|c)?
We were assigned to draw NFA for regular expression a|b|c, so like any one I draw this
But my professor told me it is wrong, the correct way is
So, I checked it ...
- 115
0
votes
0
answers
15
views
I cant figure out which regular experesion solves my problem [duplicate]
The language L=a binary number with even number of digits that doesnt have 2 consecutive zeroes.
What is the regular expression that can search those words and how what is your thought process when ...
