Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
839
questions
1
vote
1
answer
51
views
Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}
So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10
I created a DFA that could satisfy this requirement,...
-1
votes
1
answer
30
views
What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?
I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where:
two versions: one that starts and ends with 0, the other that starts and ends with 1
connected by plus, which does not mean union of both ...
-3
votes
2
answers
44
views
A more concise Finite Automata for 10 substring?
I am learning about finite automata and trying to create a machine that matches
{w ∈ Σ∗| w does not contain the substring 10}
I created a DFA where it either starts ...
1
vote
2
answers
54
views
Shortest regular expression possible
The question asks to write the shortest regular expression possible to the following automaton:
I see only one way to tackle the problem:
Use one of the methods mentioned here How to convert finite ...
0
votes
0
answers
39
views
RegEx of odd length binary strings with no '11'
I am quite new to Regular Expressions, and I'm trying to solve this problem:
Design a regular expression that accepts the language of all binary strings which their length is odd with no occurrences ...
-1
votes
1
answer
34
views
Construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa"
I want to construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa". I tried to follow the same procedure as in all the words ...
0
votes
2
answers
78
views
regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$
The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \{a, b\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them.
...
0
votes
2
answers
33
views
NFAs that accept a regular language
Just a quick question about regular languages and which NFAs accept them: If I were to draw an NFA that accepts a particular regular language, does that mean the NFA can only accept strings in that ...
0
votes
0
answers
23
views
Regex Question, creating words with a possibly recurring subword [duplicate]
I want to write a regular expression that generates precisely those words over $\Sigma = \{a,b\}$ that contain at most 1 non-overlapping occurrences of the subword bba. It has to accept the empty word ...
0
votes
2
answers
96
views
how to generate regular expression for the language where symbols have to maintain certain length?
I am having hard time creating regex for languages where symbols must be in certain length. I hope I am not ignorant about rules. we have to generate regex using $^*,|,+ \text{ and }\cdot$ right?
I am ...
0
votes
1
answer
44
views
Can we say $|xy^iz| = a^{p+i|y|}b^p$?
Using the Pumping-Lemma for $ \{L = a^nb^n | n \in \mathbb{N}\} $.
We define $p \in \mathbb{N}$
It exists a word $w = a^pb^p$
For every $|w| \ge p$: $w=xyz$, $y > 0$, $|xy| \le p$
Because of $|...
0
votes
1
answer
40
views
How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)
In the Question here it is said that
$|xy^2z|<2^{p+1}$
Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| < 2^{p+1}$?
2
votes
1
answer
576
views
What does empty string ε actually mean?
I came across this weird expression while learning about regular expressions.
$R^+ \cup \varepsilon = R^*$
why does doing union with an empty string makes this regex go from 1 or more to 0 or more?
2
votes
2
answers
1k
views
Converting Regex to DFA
People I know said that converting a Regex to DFA is just a "matter of judgement" (I do not believe them, there has to be a more systematic approach).
Is there a simple/intuitive, yet ...
0
votes
0
answers
60
views
How to work thompson's construction algorithm?
Could someone explain to me, through an example, how the McNaughton–Yamada–Thompson algorithm works in a way that I can understand?
Thank you in advance for your helpful response!
0
votes
1
answer
35
views
If a person accidentally deletes a few letters when they try to type "IDAHO" or "ILLIONOIS", then when is state name unclear or ambiguous?
The Short Version of my Question
The following two regular expressions represent two sets of strings.
REGEX
EXAMPLES OF STRINGS OF TEXT THAT MATCH THE REGEX
...
2
votes
0
answers
27
views
Flex's NFA Determinization Algorithm
I am trying to understand how the algorithm used by Flex works. I refer to the determinization procedure producing the output DFA. The algorithm is publicly available and contained in Flex's source ...
0
votes
1
answer
80
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, ...
0
votes
1
answer
30
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 ...
0
votes
0
answers
33
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$ ...
0
votes
1
answer
117
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
102
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
44
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 ...
0
votes
1
answer
60
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
46
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?
-4
votes
1
answer
79
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
30
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 ...
0
votes
1
answer
56
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 ...
0
votes
0
answers
161
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, $...
0
votes
0
answers
50
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. ...
0
votes
0
answers
31
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
21
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
493
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
80
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 ...
0
votes
0
answers
26
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 ...
0
votes
0
answers
31
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 ...
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
23
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 ...
0
votes
2
answers
421
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 ...
0
votes
0
answers
80
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 ...
1
vote
1
answer
103
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
75
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 ...
0
votes
1
answer
28
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
91
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
26
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
169
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?
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
88
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 ...
0
votes
1
answer
94
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. ...
2
votes
1
answer
152
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 ...