# Tag Info

7

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

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

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

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

$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

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

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 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 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 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 ... 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 ... 2 As for$L_1$you are right, if you would like a more generic approach, it would be$1E^* \cap E^* 0$which indeed equals$1E^*0$. The thing to remember is that conjunction "and" can be often thought of as intersection of languages. Regarding$L_2$, it is also ok. Your answer to$L_3$is wrong,$EEEEE$means exactly 5 symbols, where "does not exceed$5$... 2 The word$nm$can be expressed by the first, but not the second term$(M^∗N^∗)^∗$. Where is my mistake? There's your mistake.$m\in M^*N^*$because it is one word from$M$followed by zero words from$N$.$n\in M^*N^*$too because it is zero words from$M$followed by one word from$N$. Thus$mn\in (M^∗N^∗)^∗$because it consists of two words from ... 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 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 Hint: Use non-terminals as memory. In particular (and this envisions a right regular grammar) for each$n$let$A_n$be a nonterminal which means that (so far)$n\mathtt{a}$'s have been written to the string, and let$B_n$be a nonterminal which means that$n$more$\mathtt{b}$'s need to be written to the string. 2 MJD’s excellent answer illustrates a general technique for solving this sort of problem, but I think that it’s also worth pointing out what’s wrong with the regular expression that you got. The expression $$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*a\Big)^*\tag{1}$$ captures every word that gets accepted at state$1$, and the expression $$\Big(\big((a\cup ... 2 A language is just a set of strings. A language L over \Sigma is a subset of \Sigma^\ast, which is the set of all strings made from letters in \Sigma. L contains some of the strings in \Sigma^\ast, but not necessarily all; it might contain, or not contain, any string of letters from \Sigma. \Sigma^\ast itself is a countable set, and a ... 2 The regular expression is a concatenation of a\cup b\cup c and (ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*, so after you take a from a\cup b\cup c, you must choose either from (ab\cup ac\cup b)^* or from (aa)^*; you can’t use both, because they’re alternatives within the expression$$(ab\cup ac\cup b)^*(a\cup b)\cup (aa)^*\;.$$(In my original ... 2 In regular expression the symbol \cup means essentially or: the regular expression 01\cup 10, for instance, is 01 or 10 and is matched by both 01 and 10. If S is the set of strings matching a regular expression \sigma, the strings that match \sigma^* are the ones that can be formed by concatenating any finite number of strings in S. If ... 2 HINTS: Look at the grammar, find some stuff that you can produce, find some stuff that you can't produce. For instance, I can produce the strings a, aa, aaa, aaaa, .... I can also produce the strings bb, bab, baab, .... I cannot produce the strings ab, aba, abaa, abaaa... Now, this is written in a way that makes it really easy to convert it into a ... 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 ... 2 L is almost a^*b^*, except that \epsilon, a and b aren't in it. Regular languages are closed under difference, so L must be regular. Regular expressions don't have complement or difference, so you have to enumerate the options that are available. Luckily, all words of length 2 are fine so you only need to think about the first two characters. ... 2 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 ... 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 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 ...

1

Either the empty string or sequences of "a"s with single "b"s inbetween. Sequences of "a"s in the middle of the word have to contain 2 or more "a"s, but the word has to end with a single "a" (the word can start with a sequence of any number of "a"s). An easy way to see this is to write down what you can get 1 or more "a"s, 1 "b", 1 "a" 1 or more "a"s, 1 ...

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