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

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

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

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

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

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

(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

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.

3

$$f(x) = \frac{|x|+x}{2} - \frac{(x-1)+|x-1|}{2}.$$ (This can be simplified a bit.)

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

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 The definition of$A$is misleading. There is no reason to ever have$k>1$. Think of it as $$A=\{1y|y\in\{0,1\}^\star\textrm{ and }y\textrm{ contains at least one }1\}$$ The question from the commments is why does the regular expression equal this. There are many ways to express a string that contains at least one 1.$(0\cup 1)^\star10^\star$is one ... 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$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 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 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 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 ... 2 Here is the drawing: The idea is that the machine has two counters, one for as and one for bs, indicated by the orange boxes. Since it accepts either a number of as that is a multiple of 2, or a number of bs that is a multiple of 3, it only needs to choose which of these counters to use. Upon seeing the first symbol in the input, either a or b, it ... 2 $$\frac{\sqrt{2+\sqrt{3}}}{2}=\frac{\sqrt{4+2\sqrt{3}}}{2\sqrt{2}}=\frac{\sqrt{(\sqrt{3})^2+2\sqrt{3}+1}}{2\sqrt{2}}=\frac{\sqrt{(\sqrt{3}+1)^2}}{2\sqrt{2}}=\frac{\sqrt{3}+1}{2\sqrt{2}}$$ 2 Yes.$a^*+b^*$gets you all strings that do not contain both$a$and$b$, so you get the strings$a^n$and$b^n$for$n\ge 0$.$(ab)^*$gets you$(ab)^n$for all$n\ge 0$. Thus,$(a^*+b^*)(ab)^*$gives you the strings$a^m(ab)^m$and$b^n(ab)^m$for$m,n\ge 0$. The easiest way to check a string$w$is to start processing it from the back. Find the maximum ... 2 You can use simplify with side relations (see ?simplify,siderels). simplify(a*b*c*e*f/d, {a*b*c= A, e*f/d= B}); It is tricky to use subs when the left sides of the substitutions are more complicated than just single variables. For it to work the left sides must appear as syntactic subunits of the main expression. For your more-complicated update to your ... 2 To show that these two expressions are equivalent, you must show how to translate from one to the other. Start with a string in$(a\cup b)^*b(a\cup b)^*$. There are two cases: Either the substring consisting of the first$(a\cup b)^*$contains a$b$, or it doesn't. If the substring doesn't contain a$b\$, then the string you started with is already in ...

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