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

learn more… | top users | synonyms

1
vote
0answers
61 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be invalid....
0
votes
1answer
41 views

Proving that $\mathscr L=\{0^n \big|\text{n is the square of a natural number }\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{0^n \big|\text{n is the square of a natural number}\}$ is non regular using the pumping lemma My try: $\mathscr L=\{\overbrace{\epsilon}^{0^2},\...
1
vote
1answer
23 views

Proving that the language $\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{w\in \{a,b\}^* \big|\#_a(w)< \#_b (w)\}$ is non regular using the pumping lemma My try: $\{a,b\}^*=\{\epsilon,a,b,aa,ab,ba,bb,aaa,aab,\dots\}$ ...
0
votes
0answers
41 views

Regular expressions divisible by 3

Give a regular expression for the language L over Σ = {a, b}* of words that contain a number of b’s that is evenly divisible by 3. I know that this expression: $(a^∗ba^∗ba^∗b)^∗a^∗$ works for the ...
4
votes
1answer
58 views

Finding a general formula for a regular expression

I need to find the general formula for the regular expression $(S+T)^n$ where $S$ and $T$ are arbitrary regular expressions over a one-letter alphabet and $n$ is an arbitrary natural The general ...
0
votes
1answer
219 views

Prove that $wu=uw$, given that $w^5=u^3$

Suppose $w,u\in\Sigma^*$, $w^5=u^3$, and I need to show that $wu=uw$. I started with $5|w|=3|u|$, but I didn't know how to continue... any suggestions?
1
vote
1answer
36 views

How we derive language from grammar by bottom up or any other approach?

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 $S$ is the start symbol, $A$ and $B$ are non-terminals and $0$ and $1$ are ...
0
votes
0answers
42 views

Regular Expression for a Set of Strings of Even Length

Can the language for the set of even strings be represented by L={ε,aa,ab,ba,bb.....} Isnt Epsilon Odd?
1
vote
1answer
30 views

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular?

Given language : $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular? Somewhere it explained as : Here we need just 6 states ...
1
vote
1answer
231 views

Automata | Prove that if $L$ is regular than $half(L)$ is regular too

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one. Let L be regular language, and let half(L) be: $half(L) = \{u | uv \in L\ s.t. |u|=|v|\}$ Prove ...
-1
votes
1answer
35 views

Regular expression language that describes a graph?

Does anyone know of a regular expression language that can be used to describe a chart with time on the x-axis and price on the y-axis? I would use this language to match regular expressions against ...
0
votes
1answer
21 views

Regular Expression definitions, as a rule, what is always true?

If I have two regular expressions $\sf S$ and $\sf T$, what is always true of these? options: Both $\sf(SS \mid T)^\ast$ and $\sf(TSS)^\ast$ are subsets of $\sf(TSS\mid STS\mid SST)^\ast$ $\sf(TSS)^...
0
votes
0answers
16 views

Subset in a regular expression

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

Prove that $L = \{0^n1^m \mid n ≥ 10, m ≤ 50\}$ is regular and that any subset of it is regular

Question: Let L = {0n1m, n ≥ 10 m ≤ 50}. Prove that this is a regular language and that any subset of it is also regular. Answer or approach: 0 is regular, 1 is regular since any symbol in ∑ is ...
2
votes
0answers
100 views

Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. Shouldn'...
0
votes
2answers
24 views

Intersection of two languages

Let $L=L_1∩L_2$, where $L_1$ and $L_2$ are languages as defined below: $L_1=\{a^mb^mca^nb^m∣m,n≥0\}$ $L_2=\{a^ib^jc^k∣i,j,k≥0\}$ Then $L$ is Not recursive Regular Context free but not regular ...
1
vote
0answers
47 views

Evaluating $b^*a^*\cap a^*b^*$ to a minimal regular expression

Evaluate to a minimal expression: $b^*a^*\cap a^*b^*$ To me, the only elements to both sets are the empty string, strings containing only $a$, and strings containing only $b$, so isn't the answer ...
1
vote
1answer
27 views

Prove that the Language $L= \{ 0^n1^m \;|\; n,m \ge 0 \}$ is regular

I've looked and didn't find an answer. I know that languages like $\{ 0^n1^n \;|\; n \ge 0 \}$ and $\{ 0^n1^m \;|\; m \gt n \ge 0 \}$ are irregular so I don't understand how this language can be a ...
1
vote
0answers
27 views

Which automata recognizes the language defined by the regular expression

I am trying to understand why the following NFA is the one which recognizes the language defined by the regular expression: $(00+10)0^*((1100+1110)0^*)^*$ As far as I can see the NFA will get stuck ...
1
vote
1answer
18 views

Regular language or not : XAB where X,A belongs to (0,1)+

I am working on a problem a) L1={XAB | X,A belongs to (0,1)^+ and B is Reverse of A} i have to check whether this language is regular or not. I am trying to do ...
0
votes
1answer
41 views

Regular expression for language containing all strings that start and end with different symbols

ques - Regular expression for language containing all strings that start and end with different symbols i just went through some examples where the RE for above question is ...
0
votes
1answer
38 views

how to solve equation with epsilon

i am working on a problem for Regular expression and it resulted to this $\epsilon + a+b + aa+ab + ba + bb$ now when i solved it further and reached here $\epsilon + a + b + (a+b)(a+b)$ the ...
1
vote
1answer
67 views

Regular expressions with empty set/empty string

I was wondering if expressions such as: $λ*$ $∅*$ $λ+∅$ $∅λ$ are considered valid expressions. If so, how can I explain them? also if $∅λ$ is valid, does that imply $∅λ∅λ∅λ∅λ∅λ∅λ$ is valid, or $...
0
votes
1answer
81 views

How to determine if a word in $\Sigma^*$ is in a language?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Languages defined by regular expressions. To be ...
0
votes
2answers
339 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
1
vote
3answers
47 views

Trying to convert DFA to regular expression

I'm trying to write a regular expression from this DFA but I'm having some trouble. I can tell you what I've done so far: I started by adding a new beginning state and a new final state because ...
0
votes
0answers
48 views

Topology on a free monoid using regular languages.

A free monoid together with arbitrary unions of regular language subsets forms a topological free monoid. Every free monoid homomorphism is continuous with respect to the topology described in 1. ...
2
votes
1answer
35 views

What is the best way of resolving an expression with square roots in denominator?

I was resolving the following question from my textbook: Write each of the following expressions as a single fraction, simplifying your answer where possible: $4 - \frac{1}{\sqrt{12}} + \...
1
vote
1answer
60 views

Regular expression of alternating smaller and bigger digits

How would i go about making a regular expression that alternates between smaller and bigger numbers for an alphabet {0,1,2,3} such as "01032312" or "230102132"
2
votes
3answers
105 views

Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem. Create a regular expression for the following language: The set of all strings that do not contain ...
0
votes
2answers
42 views

How to convert DFA into RE?

So I am trying to convert this DFA into an Regular Expression. I got an answer but I am not 100% is correct I feel like it is too long. From my understanding, I just need to find the transitions into ...
-1
votes
1answer
24 views

Find languages L1 and L2, neither of which contains the other, such that (L1* ∪ L2*) = (L1 ∪ L2)*. [closed]

I'm trying solve this question in several ways, but only textbook has not helped me alot.
1
vote
1answer
39 views

Is $L_1$ context free language?

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then L ...
1
vote
3answers
49 views

Find a regular expression for the following language

I was given an example in class. It goes as follows: Let the alphabet be $\{a, b\}$. $L$ is the string with one $b$ and at least two $a$'s Find a regular expression that generates this language. ...
-1
votes
3answers
67 views

What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$? [closed]

What is the difference between regular expression $(x + y)^*$ and $(x^*y^*)$ ?
0
votes
1answer
60 views

Drawing automata for languages

I'm trying to draw two automata for these two languages: For the first one, I know that the minimum is n = 1, m = 1, but I'm having troubles drawing a NFA for it. The second one the minimum is n = ...
0
votes
0answers
18 views

Converting regular expressions to NFAs

I'm having trouble converting these regular expressions to NFAs For 1, does the plus sign mean I should draw each term individually and then make an epsilon state between them? Would this be ...
0
votes
1answer
23 views

regular expressions, notation w|w and w|?

I'm trying to give regular expressions for the following languages {a, b} What does w| and w|w mean? For the first question, I have (b(a+b))*, but I'm lost on the second.
0
votes
2answers
95 views

regular expressions $(a+b)^*$

If I have a regular expression $(a+b)^*$, does that mean I can't have the string $abba$ because the expression ends with a $b$? Or does this expression accept every string in the alphabet $\{a, b\}$?
2
votes
2answers
34 views

How to prove that $R_1(R_2R_1)^* = (R_1R_2)^*R_1$; Theory of computation

I need a formal proof for this property (or hints): Let $R_1$ and $R_2$ be to regular expressions : $R_1(R_2 R_1)^* = (R_1 R_2)^*R_1$ I don't know if the way I'm solving the problem is totally fine, ...
5
votes
1answer
85 views

Proving that all equivalent regular expressions are reachable via algebraic laws

Given a set of laws for regular expressions, for example (ripped from this document): $$ \begin{array}{llll} \text{1.} & (A|B)|C = A|(B|C) &\qquad& \text{(associativity of choice)}\\ \...
0
votes
0answers
24 views

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^...
0
votes
1answer
116 views

Writing regular expressions

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the ...
1
vote
1answer
147 views

Give some examples of strings in, and not in, these sets, where Σ = {a,b}

Here's the set: {w : for some u ∈ Σ*, www = uu} From what I understand, it's saying "w (which is a string) such that for some u (which is another string) is an element of the possible combinations ...
1
vote
0answers
73 views

Rewriting regular expressions

For the following two regular expressions, how would I rewrite them as a simpler expression representing the same set? $b^* \cup a^* \cup (a \cup b)^*$ $\Big((a^*b^*)^*(b^* \cup a^*)^*\Big)^*$ I ...
2
votes
1answer
78 views

examples of “interesting” star-free languages

Can you point me to some examples (preferably known ones from the literature, but this is not crucial) of "interesting" / non-trivial star-free languages? I'm trying to get some intuitive sense of ...
-1
votes
2answers
62 views

Prove that $R_1 \times R_2$ is a regular language for $R_1, R_2$ regular [closed]

Let A and B be two sets. The cross products of A and B are defined as : AxB={(a,b): a belongs to A and b belongs to B }. Assume R1 and R2 are regular languages over an input alphabet Σ={a,b}. Prove ...
1
vote
1answer
27 views

Creating a regex expression for a regular language

$\{x \in \{0, 1 \} : x = 0^m1^n \hspace{.1cm} \text{for some} \hspace{.1cm} m, n \in N \hspace{.1cm} \text{such that} \hspace{.1cm} m * n \ge 3\}$. I've been stuck on trying to create a regex for ...
1
vote
1answer
26 views

Using induction to prova a regular expression belongs to the language generated by a grammar (well half-proving anyways)

I have a grammar with this productions S->aBSBBa |$ \epsilon $ B->bB|$\epsilon$ $L(B)=b^*$ (by Arden's rule) and seems that $L(S) = a(b+ab^*a)^*a + \epsilon$ I have to prove that last ...
1
vote
1answer
113 views

Arden rule proof

I'm studying Arden's Rule for regular languages, but I'm having troubles with the proof. Arden's rule states that the set A*⋅B is the smallest language that is a solution for X in the linear equation ...