# Questions tagged [regular-expressions]

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

560 questions
Filter by
Sorted by
Tagged with
8 views

### Converting a regular expression to a grammar and regular grammar

I tried looking around for help before posting this but either the question did not match mine or I was not able to understand the answer posted due to my lack of knowledge. I am working on a lab and ...
11 views

### Prove or disprove that the language L is regular [duplicate]

I had an exam where I had to prove or disprove that the language $L=\{w^{|w|} | w \in \Sigma^*\}$ where $\Sigma = \{0,1\}$ is regular. On a glance, it looked regular to me so I tried using induction ...
26 views

I need to come up with a hypothesis and prove whether the language in question is regular (e.g. pump it out / provide a DFA that generates it). $$L = \{ xyyz \in \{0,1 \}^* \colon x,z \in \{0,1 \}^*, ... 2answers 213 views ### If we remove one string from any nonempty regular set, the resulting set is still regular. I am guessing this is true, because based on the definition of a regular language: "A language is called a regular language if some finite automaton recognizes it". Meaning if we have a non empty ... 1answer 51 views ### 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 ... 0answers 25 views ### Regular expression of the Language over {0,1} where any prefix that ends with 00 does not contain 11 I need to find a regular expression of the strings over {1,0} where any prefix that ends with 00 does not contain 11 I was able to find when no 11's 00. But don't understand how to move forward. 0answers 33 views ### Can a regular language be defined using recursive regular expressions? My problem is essentially that I can't find anything that explicitly prohibits or allows such definitions. To illustrate with an example: Our teacher challenged us to create a definition for a ... 1answer 19 views ### What do the regular expression operations + and . mean in the context of finite state automata? Suppose you have the alphabet \Sigma = \{0, 1, 2, 5\} where the symbols represent the value of coins, and you're given the regular expression e = (1.1) + 2 which is supposed to describe all the ... 0answers 40 views ### A regular expression that has a even number of a's and that does not contain the pattern aba The problem I have is that for the language {a, b} I have to provide a regular expression that has an even number of a's and that does not contain the pattern aba. I know that for an even number of a'... 0answers 28 views ### Given the language L=\{w\in\{a,b\}^*\mid\text{w has an odd quantity of a and even quantity of b}\} answer [duplicate] Find a finite automaton that recognizes the language$$L=\{w\in\{a,b\}^*\mid\text{$w$ has an odd quantity of $a$ and an even quantity of $b$}\}.$$Indicate whether the automata is deterministic or not.... 1answer 20 views ### Find automata for S\to01X\mid0S,\;X\to2X\mid1Y,\;Y\to2Y2\mid0 Given the grammar G=(\{S,X,Y\},\{0,1,2\},P,S) where P is$$S\to01X\mid0S,\quad X\to2X\mid1Y,\quad Y\to2Y2\mid0$$find the automata. The teacher found that the language generated by G i.e. L(G)... 0answers 19 views ### Proving regular expression identity [duplicate] For regular expressions r and s prove:$$(r^*s^*)^*=(r+s)^*$$I guess I have to prove the equality of sets (R^*S^*)^* = \left\{ x_1^{n_1}y_1^{m_1}x_2^{n_2}y_2^{m_2}... \mid n_i,m_j \in \mathbb{... 1answer 30 views ### Are the following regular expressions equivalent? Is$$ 0((01+0)^+(0+10)1) = ((0+01)^+(01+101))^+1?$$I think it's not , because the language generated by the regular expression on the left accepts the word 00101, but the language on the right doesn'... 1answer 31 views ### Creating DFAs from REGEX I am currently studying DFAs and attempting to create a DFA that only allows strings that contain 'A' three times over the language ['A','B','C']. I have the following regex which is probably not ... 1answer 37 views ### Help with Regular Expression How would you write a regular expression that matches exactly the strings over the alphabet {A, . . . , Z} that contains the letter "O" only if they contain the letter "I" and contain at most two "E"’... 2answers 45 views ### Proving the regular expression identity (a(a + b)^*)^* = (ab^*)^* I'm struggling to prove the regular expression identity$$(a(a+b)^*)^* = (ab^*)^*$$The recommendation is to use induction on the star operator. My strategy was to first prove that$$(a(a+b)^*)^* \...
I thought I proved that those two regular expressions are and identity using induction. But my friend told me that there was a counterexample. I am not sure anymore. $$(1(1 + 0)^*)^* = (10^*)^*$$