Tag Info

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

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

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

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

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

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

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

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

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

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)^* ...

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

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?

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

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

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

To find a context free grammar for $L$, note that a word of $L$ can be generated by first adding $a$s and $d$s on both sides of the starting symbol $S$, and afterwards, adding $b$s and $c$s. So a grammar will be \[ \{S \to T\mid aSd, T \to \lambda \mid bTc \} \] Denote the modified NFA by $N^+$. As we needn't have $q_f \in \delta^*(q_0, \lambda)$, ...

As you seem to understand, the states in a FA can be designed to correspond to having seen a particular form of input. One solution (not with the minimal number of states, but easier to understand) uses five states: $q_0$: Processes any input and takes special action if a $b$ is seen. (start state) $q_1$: Just saw input $\dots b$ $q_2$: Just saw input ...

Off the top of my head you have at least the following: $\epsilon\alpha=\alpha=\alpha\epsilon$. $\alpha+\beta=\beta+\alpha$. $\alpha+\alpha=\alpha$. $\alpha\beta+\alpha\gamma=\alpha(\beta+\gamma)$ and $\beta\alpha+\gamma\alpha=(\beta+\gamma)\alpha$. $(\epsilon+\alpha)^*=\epsilon+\alpha^*=\alpha^*$. $\epsilon^*=\epsilon$. If your formalization ...

Your first answer is correct, assuming that by "any string that is a permutation of $\{a,b\}$", you mean any string in the language $\Sigma^*$. Your second answer isn't quite right - the given regular expression puts more constraints on where the $a$ and $b$ fall in the string. For example, the string $abab$ is not in the language.

As Alex Kruckman noted in his answer, the language $a\Sigma\Sigma^*b\Sigma\cup b\Sigma\Sigma^*a\Sigma$ is more restrictive than you suggest. Let’s take a closer look at the first ‘piece’ of it, $a\Sigma\Sigma^*b\Sigma$. Every word in this language clearly starts with an $a$. Then $\Sigma\Sigma^*$ generates any non-empty string of $a$’s and $b$’s. Then there ...

As you said, for any $x$, $x^0=1$. What is said here is actually that an element of a set to the power $0$ is the neutral element of this set for the "product" operation. In your case the set is the set of strings and the "product" operation is concatenation. Thus the neutral string is the string which, when you concatenate it with another string is still ...

A string belongs to the set $\{11\}^*\{01\}^*$ if and only if it can be written in the form $(11)^m(01)^n$ for some non-negative integers $m$ and $n$: it must be the result of concatenating $m$ copies of $11$ and $n$ copies of $01$ for some integers $m,n\ge 0$. The length of the string $(11)^m(01)^n$ is $2m+2n$, which is clearly always even. The length of ...

i This works, but why do you bother with the arrow labelled 1? It appears that you are not requiring your automata to be complete, and so you can eliminate every state that doesn't lie on a path to a final state. ii This is fine. iii As David Lewis commented, this is much more complicated than necessary. Look at each of your $\epsilon$-transitions and ...

Hints: 1)For $a_{i}\in A$ we have that $$a_{1}a_{2}....a_{n}=a_{1}\epsilon a_{2}\epsilon....\epsilon a_{n}$$ note that $\epsilon\in B^{*}$. 2)For $b_{i}\in B$ we have that $$b_{1}b_{2}...b_{m}=\epsilon b_{1}\epsilon b_{2}...\epsilon b_{m}$$ note that $\epsilon\in A^{*}$.

Regex/Automata-based Approaches Informally The regular expression (M|N)* matches the same thing as (M*N*)*. This is obvious by inspection: both of them denote a completely arbitrary (and potentially empty) mixture of M's and N's. By Finite State Machine Equivalence We can show the expressions are equivalent by constructing the equivalent deterministic ...