# Tag Info

0

The following result holds for any language $L$ (regular or not): $(L^*)^* = L^*$. Actually, a similar result holds for any monoid $M$. Given a subset $S$ of $M$, define $S^*$ as the submonoid generated by $S$, that is, the smallest submonoid of $M$ containing $S$. Equivalently $S^*$ is the smallest subset $N$ of $M$ containing $S$ and $1$ (the identity of ...

-1

It is straightforward that $(r_1*)$ is contained in $(r_1*)*$ . Next, prove that $(r_1*)(r_1*)$ is contained in $(r_1*)$. (Use double induction.) Finally, prove that $(r_1*)*$ is contained in $(r_1*)$. (Use induction.)

0

HINT: There are two slightly different definitions of Chomsky normal form. It appears that you’re using the one that simply requires each production to be of the form $X\to YZ$ or $X\to a$, rather than the one in Wikipedia; this causes no problems, since the lack of $\lambda$-productions means that $\lambda$ isn’t in the language anyway. The algorithm ...

0

Take the string $a^qb^q$, where $q$ is any prime greater than the constant given by the pumping lemma.

5

If $p$ is a proposed pumping length, let $q > p$ be prime, and consider the string $w = a^qb^{(q^2)} \in L$. (Clearly $|w| = q+q^2 \geq p$.) Let $w = xyz$ be a decomposition such that $y \neq \varepsilon$, and $|xy| \leq p$. In follows that $y = a^k$ for some $1 \leq k \leq p < q$, and so "pumping" it zero times results in the string $$xy^0z = xz ... 2 They just put the bit about external devices in so that you would be sure that you couldn't, for example, plug in a drive to make the storage bigger. A Turing machine has an unlimited tape, so your finite-memory computer can't satisfy that. Similarly a pushdown automaton has a potentially-unlimited stack. However, a computer is fully programmable, while a ... 1 The lower branch is taken if the input ends in \ldots 1. In that case we want to replace trailing \ldots 011\ldots 1 with \ldots 100\ldots 0 (or exceptionally B11\ldots 1 with 100\ldots 0). Hence, as long as we read 1, we must write 0 and move left; only when we read 0, we must write 1, move left, and proceed looking for the left end (as ... 1 It's pretty clear from inspecting the DFA that L_3 = L(M): from q_0 we do some sequence of 0-selftransitions (going throught the loop), and then we must see a 1 to go to q_1, which is the only terminating state. We could stop then (so then we just have 0^\ast 1 as the input sequence), or we do excursions to q_0 or q_2, and so we either have ... 1 Your construction fails to make sure that the a's stay in front of the b's, note that it allows S \to bSc \to baSbc \to baDbc \to badbc. This example also shows that you need to make sure there are at least as many d's as a's and b's combined. The following rules should work:$$ S \to aSd \mid T \\ T \to bTd \mid U \\ U \to Ud \mid cU \mid c $$... 0 It seems to me, that dots in these two examples might have a different meaning. The first one looks very much like a dot from Lambda calculus, and given that the chapter talks about fixpoints, I find that highly probable. If this is the case, then the dot is only a delimiter, and it is to indicate that the symbols that come between the operator (\nu or ... 2 Every regular grammar which contains a rule of the form A \rightarrow aB (reachable from the start symbol) has an equivalent ambiguous regular grammar. Just take a new non-terminal symbol, D, add the rule A \rightarrow aD, and for each rule with B as the left symbol add a new rule obtained by replacing each B in that rule with D. For example, ... 1 There do indeed exist ambiguous regular grammars. Take for example S\rightarrow A~|~B A\rightarrow a B\rightarrow a 2 First of all, the grammar you wrore down allows any number of 0's and 1's in any order, as long as the string starts with a 1. Your regex does not encode this information, so your regex is wrong. I'm not sure why you are mixing regular expression notation and the "language" notation, but usually people don't combine those. Note that when you write a ... 0 Hint. Your language is the union of two (regular) languages: the langage L_1 of all words containing an even number of 1's and the language L_2 of the words of length multiple of 3. Now just find a regular expression for L_1 and a regular expression for L_2 (this is easy in both cases) and just take the union of your two regular expressions. 0 I think in the even number of 1's category, your NFA will miss strings of the form 110 since you do not have an ending 0* at the end of your regex. The other part of your regex only detects strings of length 3, not multiples of 3. The correct thing would be to allow the second part of your regex to be repeated as many times as you want. So, doing ... 0 Here is a possible NFA for the language 1(0 + 0(10)^*0)0: 0 I think you can add a branch in second 0-transitions to take a union operation. It is feasible in NFA. Here is a required NFA. 0 The key idea, which you mentioned, is to show that this problem is equivalent to the halting problem (on a single input). Suppose you had a decider D for the 3-input problem, and use this to get a decider for the usual halting problem. Since we know that the halting problem is undecidable, our assumption must have been wrong and there is no such D. 1 You essentially need two copies of the (00010 + 1101 + 1010) automaton to distinguish the parity, i.e., we need to keep track of the overall parity as well as the 0-1-sequence since the last completed (00010+1101+1010)^\star (fortunately, there is always only one way to reach every valid string): Thus create nodes carrying mnemonic labels: even, odd0, ... 0 At that point you know that the string$$a_1\ldots a_n\underbrace{00\ldots 00}_{i-1\text{ zeroes}}\tag{1}$$is a string of length n+i-1 that has a 1 in position i, while$$b_1\ldots b_n\underbrace{00\ldots 00}_{i-1\text{ zeroes}}\tag{2}$$is a string of length n+i-1 that has a 0 in position i. There are$$(n+i-1)-i=n-1 bits after $a_i$ ...

1

You are correct in thinking that $L_1$ is not even context-free, though the reason that you give is not a proof; it’s not too hard to find a proof using the pumping lemma for context-free languages, however, and it’s even easier to prove that $L_1$ is not regular using the pumping lemma for regular languages. It’s true that $L_1\subseteq L_1/L_2$, for the ...

Top 50 recent answers are included