Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [regular-expressions]

Questions about regular expressions, a formalism to describe regular languages.

Filter by
Sorted by
Tagged with
0 votes
1 answer
25 views

Formal regular expression equivalent for this programming regex

Consider these Regexes written in Julia (they should be equivalent in Python): ...
lafinur's user avatar
  • 195
0 votes
0 answers
18 views

Is complement of this language context-free? [duplicate]

Let $L = \{wcw : w \in \{a, b\}^\ast\} \subseteq \{a, b, c\}^\ast$. From what I know, this language is not a context-free language but how about complement of this language? I know that the class of ...
Abel's user avatar
  • 1
0 votes
1 answer
60 views

Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$

The question asks to write a regex to the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = ...
Daniel's user avatar
  • 69
0 votes
1 answer
31 views

NFA for a regular expression without $\epsilon$-transitions

I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my ...
Acad's user avatar
  • 101
1 vote
2 answers
69 views

Finding the Smallest Language Class containing a given language definition

Given two regular languages L1 and L2 over alphabet Σ, we define the operator RQ(L1, L2) = {w | there exists a word v in L2 such that wv is in L1}. The task is to determine the smallest language class ...
Oh No's user avatar
  • 11
0 votes
1 answer
23 views

Resources on Tree Automata Regular Expressions

Is there a text that goes through some explicit examples of converting tree automata to tree regular expressions? I'm working through Comon's "Tree Automata Techniques and Applications", and ...
TomKern's user avatar
  • 103
0 votes
1 answer
24 views

Can this Classic Regular Expression be simplified?

I have the following Regular Expression (classic Computer Science definition of Regular Expression, not PCRE or modern computer language RegEx): {(ΣΣ)*00(ΣΣ)*}Σ ∪ Σ{(ΣΣ)*00(ΣΣ)*} It "feels" ...
Diode's user avatar
  • 1
1 vote
1 answer
80 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,...
cool cat's user avatar
-1 votes
1 answer
66 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 ...
cool cat's user avatar
-3 votes
2 answers
46 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 ...
user168855's user avatar
1 vote
2 answers
68 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 ...
Daniel's user avatar
  • 69
0 votes
0 answers
42 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 ...
scoochy's user avatar
  • 101
-1 votes
1 answer
50 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 ...
Nolen's user avatar
  • 1
0 votes
2 answers
100 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. ...
Daniel's user avatar
  • 69
0 votes
2 answers
41 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 ...
Derek Kwon's user avatar
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 ...
emiserry's user avatar
0 votes
2 answers
101 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 ...
hxdshell's user avatar
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 $|...
Robert's user avatar
  • 57
0 votes
1 answer
41 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}$?
Robert's user avatar
  • 57
2 votes
1 answer
587 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?
hxdshell's user avatar
2 votes
2 answers
2k 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 ...
einzigartigerhummer's user avatar
0 votes
0 answers
66 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!
ProgrammerGnome's user avatar
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 ...
Toothpick Anemone's user avatar
2 votes
0 answers
33 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 ...
Chaos's user avatar
  • 543
0 votes
1 answer
81 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, ...
ZENG's user avatar
  • 113
0 votes
1 answer
31 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 ...
Lance's user avatar
  • 2,233
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$ ...
Daniel Donnelly's user avatar
0 votes
1 answer
196 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 ...
Nyquist-er's user avatar
0 votes
1 answer
118 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 ...
Crypton99's user avatar
0 votes
0 answers
48 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 ...
Dave's user avatar
  • 25
0 votes
1 answer
62 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 ...
bipartite's user avatar
1 vote
2 answers
82 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?
fenhax's user avatar
  • 11
-4 votes
1 answer
86 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\}$
user162351's user avatar
0 votes
0 answers
32 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 ...
lafinur's user avatar
  • 195
1 vote
1 answer
79 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 ...
lafinur's user avatar
  • 195
0 votes
0 answers
193 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, $...
lafinur's user avatar
  • 195
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. ...
lafinur's user avatar
  • 195
0 votes
0 answers
32 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: $𝜀,𝑎^+,𝑎^+𝑏𝑐^∗+𝑎^+𝑐^+,(𝑏+𝑐)Σ^...
Mostfa Mostfa's user avatar
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 ...
Evgeniy Berezovsky's user avatar
3 votes
1 answer
499 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 ...
Νικολέτα Σεβαστού's user avatar
1 vote
0 answers
85 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 ...
Jan Schultke's user avatar
0 votes
0 answers
27 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 ...
Finlay Weber's user avatar
0 votes
0 answers
34 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 ...
Eric Auld's user avatar
  • 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. ...
Toothpick Anemone's user avatar
1 vote
0 answers
24 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 ...
Ayrat's user avatar
  • 1,075
0 votes
2 answers
645 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 ...
user129393192's user avatar
0 votes
0 answers
102 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 ...
Zoha Javed's user avatar
1 vote
1 answer
132 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 ...
RandomGuyOnMath's user avatar
0 votes
1 answer
78 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 ...
Pratik Hadawale's user avatar
0 votes
1 answer
29 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 $...
Toothpick Anemone's user avatar

1
2 3 4 5
17