Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [regular-expressions]

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

A regular expression (shortened as regex or regexp) is a sequence of characters that specifies a search pattern. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. It is a technique developed in theoretical computer science and formal language theory. The phrase regular expressions, or regexes, is often used to mean the specific, standard textual syntax for representing patterns for matching text, as distinct from the mathematical notation described below. Each character in a regular expression (that is, each character in the string describing its pattern) is either a metacharacter, having a special meaning, or a regular character that has a literal meaning.

673 questions
2
votes
2 answers

Proving ${0^n 1^n 2^n | n >= 0}$ is not regular

This is not a homework assignment, but something I'm reviewing. I need to prove that $0^n 1^n 2^n$ where $n \geq 0$ is not regular (Just the DFA, not related to CFG). I feel like this is similar to proving $0^n1^n$ is not regular because all you…
Arrow
  • 135
2
votes
0 answers

Regular expressions and equality

Is the equality true or false? $(r^*s^*)=(r+s)^*$ My Approach: Assume the alphabet used is {0,1}$^*$ Equality is false: If r = 0 and s = 1 Then if 0101 $∈$ $(0 + 1)^*$ this is true because $(0 + 1)^*$ contains all strings that contain 0 or 1 But…
geforce
  • 217
2
votes
1 answer

regex for binary string which doesnt contain 11110

Here's my attempt, although I'm not sure if i missed any edge cases: $(0,10,110,1110)^*(1)^*$ it seems to work for any random string i test in a regex program, but is this correct?
Gudushen
  • 101
1
vote
0 answers

Equality of regular language

I am showing that two regular expressions are equal. In one of intermediate steps, I thought of the equaility: $$(RS+R)^* = (RS)^*R(RS)^*R(RS)^*....R(RS)^* = R^*(RS)R^*(RS)...R^*$$ Is it true? I mean, can I use it in my proof steps?
Jnau.Ch
  • 11
1
vote
1 answer

Solving an Equation for a Variable with $\max()$ and $\min()$ Functions

I came across an expression in 3 variables involving the max and min functions: $$x = y - \max(x,z) + \min(x,y,z).$$ I need to solve this expression for $y$. Is there any way we can do this? Reading somewhat related answers here such as this and…
Daccache
  • 1,110
1
vote
0 answers

how to covert regular expression in simplest form?

I have made this expression from nfa (NFA to regular expression) : (a+ab+aab)(a+aa) but at book answers it is written like this : (a+aab)(aa) I am thinking that the my answer is same as book but they have converted it into it just like quadratic…
user3508182
  • 121
1
vote
1 answer

Regular Expression that accepts a language L

Given, $L=\{ x \in\{0,\,1\}^* | x=0^n1^m \text{ and }n+m\text{ is a multiple of }3\}$ give a regexp that accepts the language. My thoughts are: $(000)^*(\epsilon + 001 + 011)(111)^*$ Is this right?
EggHead
  • 667
1
vote
1 answer

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 so that the words generated will contain 0(s) and…
Bilkent Ogrencisi
  • 15
1
vote
0 answers

Prove $a^*(a+b)^*=(a+b)^*$

Seems obvious but I need mathematical proof I tried to go by knowing $R^*=\epsilon + RR^*$ but reached nothing
Parsa Noori
  • 161
1
vote
1 answer

Simplifying a regular expression

I'm trying to solve a problem that requires me to simplify regular expressions. Here is the starting point: $(aaa)^*b(bbb)^*$ Which I rewrote as follows: $(a^3)^*b(b^3)^*$ However I've been trying to simplify it without success. Is there a way it…
Spook
  • 111
  • 1
1
vote
1 answer

Regular expression that represents the words s.t. start with $a$ and have an odd quantity of $a$'s

Find a regular expression that represents the language "The words over the alphabet $\{a,b,c\}$ such that end with a pair of letters, or start with $a$ and have in total an odd quantity of $a$'s". The null word is represented by $\varepsilon$. I…
manooooh
  • 2,269
1
vote
0 answers

How to Express A Regex That Accepts Nothing

I'm asked to write a regex that accepts the complement of another given regex: (a*b*)* This regex seems to accept every single string on the alphabet consisting of {a, b}, so I believe that its complement must accept no strings at all on this…
JosephTLyons
  • 403
1
vote
1 answer

Regular expressions clarification

I'm currently using the TheoryOfComputation book by Maheshwari and Smid to study regular expressions. In the book, examples were given as: The language $$\{w \in \{0,1\}^* : \text{the length of } w \text{ is even}\}$$ is described by the regular…
Jae
  • 53
1
vote
1 answer

Are these all the strings that the regular expression (a* + b*) . (a.b)* accepts or am I missing some?

From what I understand the regular expression (a* + b*) . (a.b)* accepts the following strings: Empty string, aaaaaaaaaababab, bbbbbbbbbbabab, aabab, babab, etc with different lengths of a, b and ab. Do I have it right?
zeqof
  • 181
  • 1
  • 2
  • 9
1
vote
0 answers

Constructing a regular expression based on this language

{w : w has at least two a’s and an odd number of b’s} I'm having trouble wrapping my head around how to get every single possible outcome based on this language. An odd number of b's is more or less ((bb)b), at least 2 a's is just aa(a*). I know…
pajkatt
  • 373
1
2
3 4 5 6