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

9

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

7

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

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

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

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

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

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 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 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 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 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 $$f(x) = \frac{|x|+x}{2} - \frac{(x-1)+|x-1|}{2}.$$ (This can be simplified a bit.) 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 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 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$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 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. 2 Hint: Try the opposite: find DFA that accepts all strings of 0's and 1's such that there exists a block of five consecutive symbols containing one or zero 0's. And then build the complement to this DFA. Added: There was a typo: "every block" -> "there exists a block". Sorry. 2 HINT: Start with some$ab$with$a\in A^*$and$b\in B^*$. If$b=\epsilon$, then$ab=a\in A^*B$. Otherwise, let$b=b_1\dots b_n$, where each$b_k\in B$. Then$ab=ab_1\epsilon b_2\epsilon\dots\epsilon b_n$; clearly$ab_1\in A^*B$, and$\epsilon b_k\in A^*B$for$k=2,\dots,n$, so$ab\in (A^*B)^*$. Can you finish it from here? 2 As per your last thread, note the syntax$(x + y)$says to choose exactly one of$x$or$y$. So let's define$(1 + 2 + 3 + 4 + 5 + 6 + 7 + 9)$. Notice how I concatenate two$6$'s together. Now if I take$3((1 + 2 + 3 + 4 + 5 + 6 + 7 + 9)^{*}6^{*}(1 + 2 + 3 + 4 + 5 + 6 + 7 + 9)^{*}6^{*})^{*}$, I get an even number of$6$'s, if there are any at all. With your ... 2 3 ([1-579]* 6[1-579]* 6)* [1-579]* where [1-579] denotes one of {1,2,3,4,5,7,9}. 2 For the particular example$M=2$and$R=(10 | 1)^\ast 1^\ast$, I suppose if we first convert it to a CFG then there appears to be a general formula that involves convolutions. For example:$A \rightarrow \epsilon | 0A | 1AC \rightarrow \epsilon | 10C | 0CD \rightarrow \epsilon | 1DE \rightarrow ACDA$. Then to get a string of length$n\$, ...

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