# Tag Info

## Hot answers tagged regular-expressions

11

Your answer is $$\frac{22x-7}{20x-10}$$ And the books "correct" answer is $$\frac{7-22x}{10-20x}$$ Yes? Notice what happens when you multiply both the numerator and denominator in your answer by $-1$? You're very welcome.

10

I am going to write $S_i$ for the set of strings that cause the machine to go from the start state into state $i$. From the diagram of the machine, we have: \begin{align} \def\a{\mathtt{a}}\def\b{\mathtt{b}} S_1 & = \epsilon + S_3\a \\ S_2 & = S_1(\a+\b) + S_2\a + S_3\b \\ S_3 & = S_2\b \end{align} (This part is crucial, and if you don't ...

8

You want to show that $$\frac{\sqrt{3}+1}{2\sqrt{2}} = \frac{\sqrt{2+\sqrt{3}}} {2}.$$ Rearrange this into $$2(\sqrt{3} + 1) = 2\sqrt{2}\sqrt{2+\sqrt{3}}.$$ Since both sides are evidently positive, this is equivalent to $$(2(\sqrt{3} + 1))^2 = (2\sqrt{2}\sqrt{2+\sqrt{3}})^2,$$ which simplifies to $$4(4 + 2\sqrt{3}) = 8(2+\sqrt{3}),$$ which is of course true.

8

You got the correct answer. You just need to multiply both numerator and denominator by -1 $$\frac{22x-7}{20x-10} = \frac{-1}{-1} \times \frac{7-22x}{10-20x}$$

7

Hint: Show that any two regexps over a $1$-letter alphabet commute, i.e. $PQ = QP$ for every two regexps $P,Q$. Hint to the hint: Show that any two words over a $1$-letter alphabet commute, i.e. $ab = ba$ for every two words $a,b$.

7

In order to show that $A^*B$ is "the" solution to $X=AX+B$ you have to show that (1) $A^*B$ is "a" solution to $X=AX+B$, and (2) if $X$ is a solution to $X=AX+B$ then $X = A^*B$. Unfortunately the second part is actually false in general, since $\Sigma^*$ is always a solution when $\epsilon \in A$. For a correct statement, see the Wikipedia page on Arden's ...

5

The basic idea for an automated proof is: convert both languages to their deterministic finite state machines. Calculate the cross product of the finite state machines with the transitions $F: ([x,y],\sigma) => [F_x(x,\sigma), F_y(y,\sigma)]$ Collect the list of reachable states, and their acceptivity status from both languages. If there are any [...

5

The only strings that match the regular expression $0^*$ are strings consisting entirely of $0$s. (This includes the empty string.) Thus, a string that matches $0^*1$ must end in a $1$, everything before that $1$ has to match $0^*$, so it must be a string of $0$s (or empty). Finally, a string that matches $0^*10^*$ must start with a string that matches $0^*1$...

5

The regular expression you have given gives the language $$\{\varepsilon, a, aa, aaa, \dots\} \cup \{\varepsilon, b, bb, bbb, \dots\} \cup \{\varepsilon, c, cc, ccc, \dots\}$$ $$= \{\varepsilon, a, aa, aaa, \dots, b, bb, bbb, \dots, c, cc, ccc, \dots\},$$ which is clearly not what you are after. Using only union ($\cup$), concatenation ($\circ$), and the ...

5

So we know that $A^* = \epsilon + A + A^2 + \cdots$. Are you asking to show how $X = A^* B$ from $X = AX + B$. If so, we can show it simply \begin{align} X &= AX + B \\ &= A(AX + B) = A^2 X + AB + B \\ &= A^2 (AX + B) + AB + B = A^3 X + A^2 B + A B + B \\ &\ldots \\ &= B + A B + A^2 B + \cdots \\ &= (\epsilon + A + A^2 + \cdots) B \\...

4

One easy if tedious approach is to design a finite-state automaton that recognizes $L$ and then apply the algorithm that converts such an automaton to a corresponding regular expression. Going about it directly, I observe that if $w\in L$, every $a$ in $w$ must be immediately followed by another $a$ or a $c$ or be at the end of the word; otherwise there are ...

4

Let $R$ be the set of words described by the regular expression $r$, and let $S$ be the set of words described by the regular expression $s$. Then the regular expression $(r+s)^*$ describes the words in the set $(R\cup S)^*$, and $r^*+s^*$ describes the words in the set $R^*\cup S^*$. Thus, the question boils down to asking whether it’s necessarily true that ...

4

$(1+01)^*$ generates all strings of zeroes and ones with the property that every $0$ is immediately followed by a $1$; these are the strings that do not contain $00$ and do not end in $0$. Similarly, $(0+01)^*$ generates all strings of zeroes and ones in which every $1$ is immediately preceded by a $0$; these are the strings that do not contain $11$ and do ...

4

Calling your four patterns $A_k,B_k,C_k,D_k$ respectively, note that $01101$ is in both $A_2$ and $B_1$, so you are over counting. You can fix your solution though using inclusion-exclusion

4

For completeness, I will mention: $$\mathbf{aaa}\cup \mathbf{aab}\cup \mathbf{aac}\cup \mathbf{aba}\cup \mathbf{abb}\cup \mathbf{abc}\cup \mathbf{aca}\cup \mathbf{acb}\cup \mathbf{acc}\cup\\ \mathbf{baa}\cup \mathbf{bab}\cup \mathbf{bac}\cup \mathbf{bba}\cup \mathbf{bbb}\cup \mathbf{bbc}\cup \mathbf{bca}\cup \mathbf{bcb}\cup \mathbf{bcc}\cup\\ \mathbf{caa}\... 4 Let me show you a systematic approach. Think of each of the state names as an abbreviation for a regular expression corresponding to the set of words that end at that state when starting from the initial state. Since B and C are the acceptor states, we want the expression B+C. (I’ll use + instead of a comma for or; I use \lambda for the empty word.)... 4 A DFA has no \epsilon-transitions, so this is not a DFA. I would rather called your automaton a nondeterministic finite automaton with \varepsilon-moves. Your regular expression 1(11 \cup 0^*)^* is correct. Your informal description is almost correct: you should just modify your sentence each 1 after the first, will be accompanied by at least ... 4 This has been an open problem for some years until a negative answer was given indenpendtly by Redko [4] and Conway [1, pp. 105-118]): every complete system of identities for the regular expressions is necessarily infinite. Conway [1, pp. 116-119] conjectured a "good" complete system and this conjecture was ultimately proved by Krob [2, 3]. Interestingly, ... 4 One way is to take it in pieces. Clearly your automaton accepts 0^*. What else gets it back to state a? Only 11^*00, after which you can have any number of zeroes again. Thus, 0^*(11^*000^*)^* almost does the trick. However, like your automaton, it misses the possibility that an acceptable string can end in 1 or 10 if no 0 immediately precedes ... 3 It has problems in both directions: it doesn’t accept the empty word, which is in the language, and it does accept a lot of words, like aba and abb, that aren’t in the language. The first problem is easily fixed: just make q_0 an acceptor state. The second requires some more significant changes. The b-transition from q_3 should go to q_1, the ... 3 Try this:$$ \frac{(-1)^{n}n(n+1)}{2}+(-1)^{n+1}(n+1)^2 = (-1)^n\bigg(\frac{n(n+1)}{2}-\frac{2(n+1)^2}{2}\bigg)\\ =\frac{(-1)^n(n+1)}{2}(n-2(n+1))\\ =\frac{(-1)^{n+1}(n+1)(n+2)}{2} $$3 Suppose that I’ve a one-state machine E_a that recognizes a^* and another, E_b, that recognizes b^*; combining them in the second way would result in a one-state machine that recognized (a\lor b)^*, not a^*\lor b^*. This violates both (2) and (3), but you can use similar ideas to show that violating either of them individually can produce ... 3 Another approach: identities in Kleene algebra... (a) M \subseteq M^* \subseteq M^*N^* \text{ and } N \subseteq N^* \subseteq M^*N^* \\\text{ so } (M+N) \subseteq M^*N^* \\\text{ so } (M+N)^* \subseteq (M^*N^*)^* \\\text{QED one way}  (b)  M^* \subseteq (M+N)^* \text{ and } N^* \subseteq (M+N)^* \\\text { so } M^*N^* \subseteq (M+N)^*(M+N)^* \... 3 (a) The requirement boils down to saying that once you get xx, you can never get a y. Your regular expression generates only valid strings, but it doesn’t generate all valid strings. For instance, it doesn’t generate xyxx. You want something like y^*(xy^+)^*x^*. (b) The second part of your regular expression is fine: it generates precisely those ... 3 A comment before I get to your (1)-(3): p and P are not the same symbol, so either the pumping length is p, or it’s P, but you shouldn’t keep jumping back and forth between the two. I’ll use p. This is correct: the pumping lemma is strictly a tool for showing that a language is not regular. This objection is not really well-taken. It’s true that ... 3 Usually, in a monoid, we define x^0 to be the identity element of the monoid, that is, the element e such that ex = x = xe for all x. This is so that the standard "exponent rules" such as x^{a+b} = x^a \cdot x^b hold even when a or b=0. In your case, since the operation is concatenation, it makes sense for x^0 to mean the empty string, since ... 3 r and s are regular expressions, which represent regular sets. If r and s are regular expressions that represent sets R and S, then the regular expression r+s denotes the set R\cup S. If r is a regular expression denoting the set R, then$$r^*$$is a shorthand for$$\epsilon + r + rr + rrr + \cdots .$$3 One very straightforward approach to (a) is to begin by listing the 8 binary strings of length 3. Every string whose length is a multiple of 3 must be formed by concatenating those strings. I’ll illustrate with strings of even length: any string of even length can be segmented into two-character chunks, each of which must be 00,01,10, or 11, so the ... 3 For any fixed value of n, the language$$ L_{n}=\{w:|w|_a=2^n+273\} $$is certainly regular, and the regular expression you described will recognize it. But the question here is whether$$ L=\bigcup_{n\in\mathbb{N}}L_n = \{w:|w|_a=2^n+273 \text{ for some } n\in\mathbb{N}\} $$is regular. It's not; and the easiest way to prove it is to use the so-called ... 3 Let H denote the unit step function. xH(x) is zero when x is negative and equal to x when x is positive. xH(x-1) is zero when x is less than 1 and equal to x otherwise. If I'm not mistaken,$$xH(x) - (x-1)H(x-1) is the function you want.

Only top voted, non community-wiki answers of a minimum length are eligible