# Tag Info

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