Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
-5 votes
0 answers
17 views

DFA testing exercice ASAP please [duplicate]

I have a question : If my word can be only AA or BB or A or B how i will write my regular expression ? And if 0 is a par number it also may be to include ? it is something like this : A|B|epsilon) (AA|...
Duarte Grilo's user avatar
0 votes
1 answer
73 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
  • 111
0 votes
1 answer
27 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,163
0 votes
0 answers
27 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
56 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
56 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
39 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
42 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
38 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
54 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
28 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
37 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
64 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
37 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
29 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
20 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
454 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
51 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
22 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
29 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
19 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,055
0 votes
2 answers
139 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
50 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
0 votes
0 answers
67 views

Help with converting the DFA to a regular expression using Ardens theorem

Can someone explain to me how to convert this DFA to a regular expression? I have tried using Arden’s theorem but I don’t know how to simplify the equations to get the regular expression for this DFA. ...
amanda che's user avatar
0 votes
1 answer
68 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
52 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
26 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
63 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
0 votes
0 answers
21 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 ...
Toothpick Anemone's user avatar
2 votes
1 answer
137 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
77 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
0 votes
1 answer
63 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. ...
mark's user avatar
  • 67
2 votes
1 answer
103 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 ...
mark's user avatar
  • 67
0 votes
0 answers
56 views

When converting a "empty string" regular expression to finite automata, are FA with 2 states vs 1 state equivalent?

Let's say we have a regular expression, R = $ε$. If we wanted to convert this to finite automata ( NFA or DFA ) which of the following would we use? Have 2 states: q0 ( start state ) and q1 ( accept ...
Pratik Hadawale's user avatar
1 vote
1 answer
467 views

Regular Expression of {w : w contains an even number of 0s and exactly two 1s}

I know the answer if it was OR would be (1*01*01*)* U 0*10*10*, but with the AND I have no clue how this can be achieved. There are lot's concatenations that I can'...
Raxhacks's user avatar
0 votes
0 answers
10 views

Regular Expression of {w : w contains exactly two 0s and at least two 1s} [duplicate]

I have this 1^*011^*011^* and haven't been able to think of it differently. Can you please help me see how I can get this input 0011 and 1100 correct?
Raxhacks's user avatar
3 votes
0 answers
52 views

Reference request about equivalence of automata / regular expressions up-to a language

The most widely used notion of equivalence of regular expressions $r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
Martin Berger's user avatar
1 vote
1 answer
35 views

Is it true that $R.L^* + L^* = R + L^*$?

I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^* + L^*$ in the end which I am not sure how to simplify further. I want to ...
Axo's user avatar
  • 115
0 votes
1 answer
56 views

Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language. Theorem Let L ⊆ Σ∗. The following conditions are equivalent: L is generated by a ...
Alan Whitteaker's user avatar
0 votes
0 answers
75 views

What is a regular expression that describes whether an integer w is a multiple of 6?

Let's say we are looking at the decimal language $L_6$ where $$\Sigma = \{ 0,1,2,3,4,5,6,7,8,9 \}$$ and $L_6$ accepts an integer w if w is a multiple of 6. I'm trying to find the regular expression ...
Anonymous123's user avatar
0 votes
0 answers
99 views

How does the regular expression '^(a+)+$' lead to this specific NFA?

OWAPS has an article on ReDoS (archived). In it, they use the regular expression ^(a+)+$ as an example for ReDoS vulnerabilities. They provide this illustration of ...
Alex Povel's user avatar
1 vote
0 answers
55 views

What is the formal definition of a combinational logic?

Question Background A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35): The image below (taken from the Wikipedia article on combinational logic) seems to suggest that ...
Shadow43375's user avatar
0 votes
1 answer
49 views

Convert regex for comma separated value to CFG grammar

I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
user156830's user avatar
0 votes
1 answer
43 views

When converting DFA/NFA to regular expression, where the DFA/NFA accepted empty string, is it okay to not have empty string as kleene star?

Let's say that we have a DFA, where the initial state was also the accept state. Meaning the DFA accepts the "empty string". Now, let's say that we convert the DFA to regular expression $R$, ...
Pratik Hadawale's user avatar
0 votes
1 answer
45 views

Does every regular expression describe only 1 language?

If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it Also, $...
Pratik Hadawale's user avatar
0 votes
3 answers
91 views

Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*

I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem: Since, we have 3 accepting states, we would find 3 ...
Pratik Hadawale's user avatar
0 votes
0 answers
23 views

How to reduce this regular expression: a* + a*bb* + a*bb*cc* + a*cc*?

I know minimizing regular expressions is PSPACE-HARD but we can still use identities to minimize regular expression. I can tell the reduced version of this would be a* b* c* by looking at the NFA, my ...
Pratik Hadawale's user avatar
0 votes
1 answer
32 views

How to make a recursive definition for a given predicate?

I have the following predicate: $empty(r)\Leftrightarrow L(r)=\emptyset.$ Now I am given the following regular expressions where $e, f$ are any regular expression: $r=\emptyset$ $r=\varepsilon$ $r=a:\...
David Krell's user avatar

1
2 3 4 5
17