# Tag Info

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 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}$$

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

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

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

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

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

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

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

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

$(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

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

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\\ ... 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 3 By convention, the Kleene star oprator (\cdots)^* binds very strongly -- it applies only to the thing immediately before it, unless brackets are used to draw more in. So 1(1+00)^*0 means "a 1, followed by zero or more things that are each either 1 or 00, followed by a 0". Your example 1001 is not matched by the regular expression. In particular it is ... 3 If something is divisible by 5 then it ends in zero or five. So (1|2|4|5|7|9)*5 would characterize your language. 3 Yes, it’s correct. Every 0 in such a string must be preceded by at most three ones, so the regular expression (0,10,110,1110)^* generates every possible acceptable string ending in a zero. The last zero, if any, can be followed by any number of ones, so (0,10,110,1110)^*(1)^* picks up everything. 3 Let w\in S^*. Since (S^*)^* contains all concatenations of any finite number of words from S^*, it certainly contains w, which is a concatenation of just one word from S^*. So S^*\subseteq(S^*)^*. Conversely, let w\in(S^*)^*. By definition we have$$w=w_1w_2\cdots w_n$$for some n\ge0, where each w_j is in S^*. By definition again, ... 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 There are algorithms for converting a DFA to a regular expression, but with a simple DFA like this one can do it in ad hoc fashion. I’ll illustrate this in some detail as a model for thinking about such problems. The key here is what has to happen if you reach q_1. Suppose that you reach q_1; you’ll have to get back to q_0, but before that you can ... 3 Let A = R_{1} and B = R_{2}. Let M(A) and M(B) be the finite state machines accepting A and B respectively. Define M(A \times B) to be the machine with states Q_{A} \times Q_{B}, transition function \delta_{A} \times \delta_{B} and final states F_{A} \times F_{B}. Argue that this machine captures A \times B exactly. Without loss of ... 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 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 Hint: \frac{u^3-v^3}{u-v}=u^2+uv+v^2. Let u=A^x and v=A^{-x}. 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 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 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 So here is my attempt without any state machines...$$0^*1^*?(1^*00^+1^*)^*0^*$$Better version ( minor adjustments, some unnecessary terms ):$$0^*((1^*00^+)^*1^*0^*) where + means 1 or more matches, * 0 or more matches. I have tried it later on, but first some thinking as why it should work Here the philosophy that we start at the endpoints and ...

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