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
0
votes
2 answers

Find a regular expression for the language of all words over {a,b} that include ab or ba

My original thought for this problem was (a+b)b*(a*+b)(λab) + (b+a)a*(b*+a)(λba) but the problem with this is that it can't generate abaa So i tried to rewrite it as (a+b)a*+b*(a*+b)(λab) + (b+a)a*+b*(b*+a)(λba) If anyone could offer me some…
0
votes
1 answer

State whether the string 010 belongs to the language denoted by each of the following regular expressions

(a) $(\epsilon + 1)0^{*}1^*0$ Solution that I cant read properly: $(\epsilon + 1)0^{*}1^*0$ $= (\epsilon + 1)$ [by def of union] $= 0 \epsilon 0^{*}$ [by def of star] $1 \epsilon 1^*$ $\epsilon 010 = 010$ [def of concatenation] I don't get it. Could…
Tinler
  • 1,061
0
votes
1 answer

Determine an expression for X from the truth table

I am having a problem with determining an expression for X from the truth table below. Can you help me to do this? Thanks in advance
NST
  • 1
0
votes
1 answer

Find a regular expression of following sets

The set of strings over $\{a, b, c\}$ with length greater than three. The set of strings over $\{a, b\}$ where every $a$ is immediately preceded and followed by $b$. The set of strings over $\{a, b\}$ that do not end with $ba$. I understand how to…
0
votes
1 answer

Equivalence of regular expressions

I need to prove (or disprove, but I think those are proves), that the regular expression: r = (a+b)*b(a+b)*a(a+b)* (where + is OR and * is Kleene star) is equivalent to those expressions: r' = (a+b)*bb*a(a+b)* r'' = a*b(a+b)*ab* The prove needs to…
DanielY
  • 979
0
votes
3 answers

Factorization, simple expression!

I must factor out this expression: (I don't speak English, I don't know the right mathematical terms you use in English, sorry if I make a mistake). $a^{3}(\frac{a^{3}-2b^{3}}{a^{3}+b^{3}})^{3}+b^{3}(\frac{2a^{3}-b^{3}}{a^{3}+b^{3}})^{3}$ The…
0
votes
2 answers

Having a hard time translating from infix to postfix

Trying to translate this infix expression: $(7 - 3) * (5 + ((8 * 4) - 9))$ in to a postfix expression. Based on my understanding the answer is $7\; 3 - 8\; 4 * 9 - 5 + *$ but when I look up solutions I get this answer: $7\; 3 - 5\; 8\; 4\; *\; 9 - +…
Darien Springer
  • 133
  • 1
  • 8
0
votes
1 answer

Concatenate Language to a specified power

I'm trying to understand a point in my textbook: We let $R^k$ be the shorthand for the concatenation of k R's with each other. From my understanding then, $R^2$ would be the set containing all strings over R of length 2. There was a problem at the…
Elizabeth
  • 149
0
votes
1 answer

Can anyone explain why language concatenation works like this

For a language S, an empty string $\epsilon$, and an empty language {}, S $\cdot$ {$\epsilon$} = S = {$\epsilon$} $\cdot$ S but S $\cdot$ {} = {} = {} $\cdot$ S (where $\cdot$ denotes concatenation) I understand why concatenating a language with…
Otay
  • 91
  • 9
0
votes
1 answer

Equivalent Expressions

Basically I'm trying to get this expression: $${(-1)^nn(n+1)\over2} + (-1)^{(n+1)}(n+1)^2$$ In this form: $$(-1)^{(n+1)}(n+1)(n+2)\over2$$ This is for a proof using mathematical induction, and I'm 99% sure that they DO equal each other. For some…
mh234
  • 171
0
votes
1 answer

Order of expressions in regular expressions?

Does the order of expressions in regular expressions matter? For example: Can I write for example $(a^*)b$ as: $(a^*)b$ = $b(a^*)$ ? What about the following? $a^mb^n = b^na^m$ $a^nb^n=b^na^n$ $a^n b^m c^n = a^nc^nb^m$ If not then when does this…
0
votes
0 answers

Checking if regular expressions are equivalent

Is there a quick script/tool to check if two regular expressions are equal? For example: I want to know if 0*(01 + 11) is equal to (0*01 + 0*11) i.e. Can I multiply them just as basic math?
0
votes
1 answer

Subset in a regular expression

Is this true for every two regular expressions $G$ and $K$? $(GG + K)^*$ is a subset of $(KGG)^*$ and $(KGG)^*$ is also a subset of $(GG + K)^*$
0
votes
0 answers

How to solve the following relationship?

We can easily seen that $${q^{2n}} = {q^n}\left( {{q^n} - 1} \right) + {q^n},{q^{3n}} = {q^n}{\left( {{q^n} - 1} \right)^2} + 2{q^n}\left( {{q^n} - 1} \right) + {q^n}.$$ Similarly, we assume that $${q^{mn}} = {q^n}\sum\limits_{k = 1}^{m - 1}…
xuce1234
  • 1,330
  • 7
  • 12
0
votes
1 answer

Regular expression

I'm trying to find Strings of length 4 In this regular expression. However, I'm having trouble understanding how the string is built $$1(1+00)^*0+(01)^*+(101+0)(10+λ)1^*$$ For example, for $1(1+00)^*0$, if I decide that * gives me 1 or more I…