# Questions tagged [regular-expressions]

Regular expressions or Regex is a search pattern for strings defined by a sequence of characters.

668 questions
Filter by
Sorted by
Tagged with
1 vote
45 views

### Is the Language $L = \{a^n b^m c^k d^q e^r \,|\, n, m, k, q, r \geq 0\}$ a Valid Regular Language?

I am inquiring about the nature of language L. It appears that L is not categorized as a regular language due to its unique characteristics, which involve the need to count occurrences of multiple ...
19 views

### regex for exactly n possible values which are unique

I want to write a regular expression in my python code, but I think this is more of a mathematical challenge. So my requirement is, suppose I want to create $3$ unique coupon codes, I can write a ...
16 views

### Prove that the Kleene closure of the union between language and null string is the same as the Kleene closure of just the language [closed]

There's something I'm currently stuck on. Suppose there is a language L. We know that L* is {ε, L, LL, ...} and so on. (L+ε)* should produce the same set since the null string is already accounted for ...
28 views

### Express a count of an element in period of time [closed]

I want to know if it is possible to represent the count of an element in a set, having different elements collected over a given period of time. Let's say $A$ is the set with varying elements at a ...
22 views

### Pumping lemma question: L = {w0nw | w є {0,1}* and n > 0} verification

Consider the language L = {w0nw | w є {0,1}* and n > 0}. Check the alternative containing the choices that we can make regarding the parameters of the pumping lemma in order to prove that L is not ...
43 views

### Is there a name for the set of single-character prefixes of words in a regular language

This question concerns regular languages and regular expressions. Suppose we have an alphabet $\Sigma$ and a language $\mathcal{L}$. For some algorithm, I am particularly concerned with the set of ...
48 views

### Find all strings of $w$ that satisfy following equation

Solve the following string equation on the alphabet $A = \{1, 0\}$ and find all $w$'s: $w011 = 011w$
32 views

### Trying to draw a graph from regular expression

I do my homework My regular expression is $b^m\,(ab)^na | m,n >= 0$ After several attempts I have this: The vertex q1 is the entry and q2 is the exit. Do you think it corresponds to the given ...
71 views

### Are $111^*$ and $11^*1$ equivalent?

I know it is a trivial question but are $111^*$ and $11^*1$ equivalent? (I think yes because I can have 11 in both at minimum but that seems odd to be true). I am trying to understand automata theory ...
51 views

### Regular expression .Find it

Construct a regular expression that defines the language of all words that contain either the aa-substring or the bb-substring but NOT BOTH the aa-substring and the bb-substring in the same word....
69 views

### Superscript in regular expression

If I want a language where the entries are in the form of $\gamma A^{n+2}\gamma A^{n+2}...\gamma A^{n+2}$, is it possible to write a regular expression as $(\gamma A^{n+2})^*$, or is it weird to have ...
24 views

### Context-free language as regular expression

I want to ask a short question. Can a regular expression expresses a context-free language that is not a regular language?
1 vote
51 views

39 views

### Regular language that specifies cycles of length 7 for rule 110

I found a language of which I may assume that it is regular, and now I want to know the grammar. The words $w$ of the language have the form (A [0, 2, 4] B C+)+ ...
31 views

### Symbol raised to the power of asterix raise to the power of asterix in regex [closed]

To describe the regex (a*+b+a)* in plain English you would simplify it to (a*)* + (b)* + (a)* . How would you describe (a*)* in English as the rest is just any number of bs or any number of as?
53 views

### Is there a procedure to give a generating function for arbitrary regular languages?

The Schützenberger methodology can enumerate the number of words of given length $k$ for unambiguous context free languages by a generating function. But not all regular languages are unambiguous ...
31 views

### How to prove that for any $w_1,...,w_n \in \{0,1\}^*$ regular expression $w_1^*w_2^*\dots w_n^*$ doesn't represent language $\{0,1\}^*$?

How to prove that for any $w_1,...,w_n \in \{0,1\}^*$ regular expression $w_1^*w_2^*\dots w_n^*$ doesn't represent language $\{0,1\}^*$?
47 views

### Is b*a(a+b)* equivalent to (a+b)*a(a+b)*?

So two regular expressions are equivalent if they are associated, i.e., produce the same regular language, I am curious about this because it is clear that the language produced by $b*a(a+b)*$ is ...
1 vote
65 views

### Unambiguous regular expression for binary strings

Give decompositions that uniquely create the following sets of 0/1-strings. All strings with no odd blocks of length greater than 4. With this problem, I was looking for a regular expression that ...
59 views

### Can a binomial be a term?

This is probably a silly question but I'll ask anyway. I know that terms in mathematics are numbers or variables or some combination of numbers/variables multiplied by each other. They are combined ...
71 views

### What happens if I expand b*( (ab) b* )*? [closed]

I just wanted to confirm if what I have here is correct. If I expand b*((ab)b*)* are these set of strings valid? Sorry, I tried posting it in StackOverflow but that needed code and this doesn't ...
1 vote
28 views

### Substitution of a letter with a regular expressions in regular expressions identities

There is an exercise in "Introduction to computer theory" by Daniel IA Cohen (ch. 4, ex. 20) the main part of which goes like: Explain why we can take any pair of equivalent regular ...
36 views

### Prove formal language isn't regular

I've been tasked with showing that given a regular language $L$ over $\Sigma={0}$, prove that the language $Minus(L)= \{ 0^x1^y | 0^{x-y}\in L \}$ is not regular. I've tried to use $L=0^*$, which ...
1 vote
45 views

### Build a regular expression that specifies the language L in the alphabet Σ = {a, b, c}:

Build a regular expression that specifies the language L in the alphabet Σ = {a, b, c}: L = {w : w does not contain aaab}. For this task, you also need to build a deterministic finite automaton, but I ...
1 vote
64 views

### Finding equivalence class for $R_L$ of a regular language

Let $\Sigma = \{ a, b, c\}$, $$L = \{w\in\Sigma^*\mid w \text{ starts with ab and ends with ab}\},$$ i.e. $L = ab(\varepsilon + (a+b)^*ab)=ab+ab(a+b)^*ab$. I need to find a regular expression ...
573 views

### Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma

I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma My proof: If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
463 views

### Regular Expression - binary digits, no occurrences of 111, solving methodology?

Can someone show in some simple steps how one goes about creating a regular expression from binary digits that excludes all occurrences of 111? What I am having trouble is how one starts these sorts ...
60 views

### creating regular expressions from given language

The first question is $L_1 = \{w \in \{a,b,c\}^∗ \mid \text{$w$ends with$ca$}\}$ I started by creating a DFA for that for better understanding and then making a regular expression. and the regular ...
42 views

### Finding the equivalent regex for a formal grammar

We have the following formal grammar: $a, b$ are terminal symbols. $S, A, B$ are non-terminal symbols. $S$ is the startsymbol. Thinking in terms of a nondeterministic finite automata $q0$ indicates ...
1 vote
475 views

### Regular Expression for binary string that contains number of zeros not a multiple of 3

I want to generate a regular expression by using only + (or, union), * (0 or more), and (^+ 1 or more) operations. The language contains only 0 and 1. The problem is to generate a regular expression ...
1 vote
### Solution Verification: Regular expression that starts with $a$ and doesn't contain $aba$ pattern.
Write a regular expression that starts with $a$ and doesn't contain $aba$ pattern. My Solution: If my expression doesn't contain $aba$, then it must not have a $b$ alone in the middle of it before ...