Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
761
questions
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
39
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
70
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
34
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
241
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
28
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
24
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
42
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
1
answer
56
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
55
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
74
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
34
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
1
answer
58
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$, ...
- 111
1
vote
0
answers
28
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
19
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
56
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 ...
- 331
1
vote
2
answers
23
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
40
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 ...
- 331
0
votes
1
answer
81
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.
- 109
0
votes
0
answers
33
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
64
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
394
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
56
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
40
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
- 15
2
votes
0
answers
36
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
92
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?
- 15
1
vote
1
answer
81
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
149
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
44
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
33
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
0
votes
1
answer
54
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
0
votes
1
answer
24
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
29
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
1
vote
0
answers
61
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 ...
- 111
0
votes
1
answer
70
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
556
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 ...
2
votes
1
answer
52
views
Convert a dfa to rule for a asterisk case
Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
- 19
0
votes
1
answer
43
views
Can any language be expressed by regular expression?
I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression.
In my current understanding the rule is &...
- 1
0
votes
1
answer
32
views
Empty string in an ambiguous grammar?
I'm a bit confused by the role of the empty string in this ambiguous grammar:
A' -> A
A -> if A B
A -> null
B -> [empty string]
B -> else S
So what ...
- 101
0
votes
1
answer
27
views
Can a non-regular language have a regular grammar?
Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now:
S -> 1 | 0 | ε
Since it ...
0
votes
1
answer
51
views
Regular expression for set of all strings containing no 3 consecutive 0s?
The answer is
$1^*01^*01^*+1^*(0+00+\in)1^*$
If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice?
How do I understand what the regular ...
- 9
3
votes
2
answers
773
views
Regular Expressions - What is difference between a+ and a⁺
I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.
- 31
0
votes
0
answers
42
views
conversion of regular expression to automata
I've a task to specify a finite automata (of any kind) that accepts the language described by this regular expression: $a(bab)^+b^*|(ab)^*(aa)^+$
My first solution looks like this:
I would like to ...
- 25
1
vote
1
answer
52
views
Regular expression for words without two equal consecutive letters
I need to find a regular expression for the language over $\{a,b,c\}$ consisting of all words in which no two consecutive letters are the same.
For example, $abacbabca$ is in the language, while $abbc$...
- 11