# Questions tagged [regular-expressions]

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

632 questions
Filter by
Sorted by
Tagged with
13 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 ...
22 views

### Automata Regular Expression that remembers n iterations

Given is $L = \{\sigma_1 ~u~\sigma_2~v~\sigma_3 ~|~ \sigma_{1,2,3} \in \Sigma,~~ u,v\in \Sigma^*,~ |u|=|v|,~ \sigma_2=\sigma_3 ~or~ \sigma_2=\sigma_3 ~~\mathbb{but ~~ not ~~ both} \}$ I do not ...
• 654
60 views

### Prove $L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$ is a regular language where $L$ is regular [duplicate]

Let $L$ be a regular language with alphabet $\Sigma$. Prove that the language $$L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$$ is regular.
1 vote
29 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 ...
• 373
38 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 ...
• 111
58 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 ...
49 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 ...
39 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
24 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
32 views

### 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 ...
• 2,029
1 vote
36 views

• 529
68 views

### Design a regular expression that accepts the language of all binary strings with no occurrences of bab [duplicate]

i have tried a∗b∗ ∪ b∗a∗ ∪ a∗b∗aa+b∗a∗ , it can be represented as abbaaaba which meets the requirement. However, I am not very confident in my answer and want to ask if anyone can help confirm this ...
• 21
125 views

### Give the regular expression for the set of strings $\{a, b, c\}$ that do not contain substring $aa$

Give the regular expression for the set of strings $\{a, b, c\}$ that do not contain substring $aa$. How to solve this regular expression? I've been thinking for a long time to generalize that. But ...
1 vote
169 views

• 155
39 views

### Minimum length regular expression for $\{ w| w\in\{0,1\}^*$ and for every x that is a prefix of w, $|\#1(x)-\#0(x)| \leq2\}$

$L(M) =$ $\{ w| w\in\{0,1\}^*$ and for every x that is a prefix of w, $|\#1(x)-\#0(x)| \leq2\}$ I tried to use some online convertors and only found this regular expression: ((a+(ϵ+a(ab)*b+b(ba)*a)(...
1 vote
347 views

### Showing star-freeness of recursively defined languages

Problem: Define a sequence of languages on $A$, a finite alphabet as $D_0 = 1$ (empty string) and $D_{n+1}= (aD_nb)^*$. Show that each $D_i$ is star-free (for each there is an equivalent star-free ...
• 2,988
1 vote