# Tagged Questions

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

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....
41 views

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)*
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 ...
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'...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
67 views

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"
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 ...
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 ...
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.
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 ...
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. ...
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^*)$ ?
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 = ...
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 ...
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.
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\}$?
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, ...
85 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...