Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
62 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
21 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
  • 101
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
60 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
36 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
60 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
  • 33
0 votes
0 answers
40 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
38 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
86 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
  • 33
0 votes
2 answers
35 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
98 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
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}$?
Robert's user avatar
  • 57
2 votes
1 answer
580 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
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 ...
einzigartigerhummer's user avatar
0 votes
0 answers
65 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
29 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
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, ...
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,223
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
149 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
109 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
47 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
  • 23
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 ...
bipartite's user avatar
0 votes
1 answer
48 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
  • 1
-4 votes
1 answer
80 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
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 ...
lafinur's user avatar
  • 181
0 votes
1 answer
59 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
  • 181
0 votes
0 answers
176 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
  • 181
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
  • 181
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: $𝜀,𝑎^+,𝑎^+𝑏𝑐^∗+𝑎^+𝑐^+,(𝑏+𝑐)Σ^...
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
497 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
84 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
32 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
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 ...
Ayrat's user avatar
  • 1,065
0 votes
2 answers
527 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
89 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
114 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
76 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
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 $...
Toothpick Anemone's user avatar
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 ...
Toothpick Anemone's user avatar
2 votes
1 answer
179 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?
skyking's user avatar
  • 123
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: ...
Toothpick Anemone's user avatar
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 ...
mark's user avatar
  • 67

1
2 3 4 5
17