# Questions tagged [regular-expressions]

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

518 questions
Filter by
Sorted by
Tagged with
391 views

### Regex for divisibility by 123 in binary strings

Is there a regex that checks for divisibility by 123 in binary strings? This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative ...
77 views

### Is there a way to find a simple regular expression for this language?

Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is ...
49 views

### Show that the regular language is contained in another

Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ? $\bigotimes$ denote the transducer cross product. $L_1^+ \bigotimes L_2^+$ ...
137 views

### Operations on regular languages

I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language ...
369 views

### Regular expression for string with substring 010 and ending with 01

How can one design a regular expression for given string in title ? Also how can we draw DFA of that regular expression? I've tried many expressions but couldn't succeed, please help.
85 views

### Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
286 views

### Do all Regular Expressions describe Regular Languages?

I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent ...
476 views

### Cartesian product of regular expressions?

My textbook has a problem to find the regular expression that describes the set of all strings of 0's and 1's whose number of <...
295 views

### Finding the regular expression equivalent for the given finite automaton

This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression. On inspecting the given automata, I started deducing the ...
360 views

62 views

615 views

### Regular expression for even/odd string on alphabet

Given the alphabet $\{ a,b \}$, if I want to build the regular expression for even/odd lenght strings, I can think that an even lenght string is given by some combination of $a$'s and $b$'s, and the ...
51 views

### Recurrence relation for a star and a dot wildchar pattern

. Matches any single character, * Matches any sequence of characters (including the empty sequence). dict = ["cat", "cats", "...
106 views

### What is the deterministic finitite automaton (DFA) for the regex “.*b.”

I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and ...
65 views

### Giving a regular expression for a situation of a question

I have the following question regarding a situation given and we are then required to derive a regular expression out of it. What i have to do now i to give a regular expression for this language ...
122 views

### Are these two regular expressions equivalent?

$u^*v(w \cup xu^*w)^*$ and $u^*v(w \cup x(u)^*w)^*$ Is that extra set of parentheses around the second $u$ needed?
47 views

### Create DFA with String of {a,b} [duplicate]

I Want to Create Regular Expression from string of {a,b} that it contains neither the substring ab NOR ba?How I can do it?
348 views

### Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

Show that the following language $L$ is regular by describing it using a regular expression. $$L = \{1^n w 1^n \mid n > 0 \text{ and }w ∈ \{0,1\}^*\}$$ My (apparently incorrect) answer: Given ...
92 views

### Creating regular expression with sub sequences of strings

I am creating a program which searches for particular types of strings. The alphabet of these strings are in $\{a, b, c\}$, for which every sub string of length 3 contains exactly $c$. Some strings ...
81 views

### Proving OP(L) is regular [closed]

I did some searching before I decided to ask this question and there was nothing similar to my question that helped me. So I came to CS stack-exchange for hints. So, I am currently working on a proof ...
335 views

### Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof

Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. ...
135 views

### Simplification of regular expressions

$(0+1)^*.1.(0+1) + (0+1)^*.1.(0+1)$ and $(((0^*.1^*)+1)^*(0+1)^*)^*$ I have studied Arden's theorem $R=Q+RP$ has a unique solution $R=QP^*$ and some identities like $E+RR=R$ and $E.R=R$. I have ...
162 views