Tag Info

Hot answers tagged

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


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

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

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

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

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

(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

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

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

A DFA has no $\epsilon$-transitions, so this is not a DFA. I would rather called your automaton a nondeterministic finite automaton with $\varepsilon$-moves. Your regular expression $1(11 \cup 0^*)^*$ is correct. Your informal description is almost correct: you should just modify your sentence each $1$ after the first, will be accompanied by at least ...


3

A regular language is one that can be recognized by a finite machine—that is by a computer with a finite amount of memory. $\mathtt 0^*\mathtt 1^*$ is the family of strings that have some zeroes followed by some ones. Suppose you had some string a billion symbols long and you had to decide if it had this form. You could do that with hardly any memory: just ...


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

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

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



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