# Questions tagged [regular-expressions]

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

829 questions
Filter by
Sorted by
Tagged with
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|...
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, ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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?
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\}$
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 ...
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 ...
64 views

1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
29 views

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 ...
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 ...
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?
1 vote
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: ...
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 ...
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. ...
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 ...
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 ...
1 vote
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'...
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?
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 ...
1 vote
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 ...
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 ...
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 ...
99 views

1 vote
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 ...
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 ...
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$, ...