# Tag Info

6

HINT: Let $M$ be a DFA that recognizes $L$. Make two copies of $M$, say $M_1$ and $M_2$; we’ll modify them to make an NFA $N$ that recognizes $L_e$. $N$ starts in the initial state of $M_1$. Each state of $M_1$ has all of the transitions of $M$, and each also has two extra transitions, one for $0$ and one for $1$, that go into $M_2$. There are no transitions ...

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

Your understanding is correct. If you want to apply the lemma to a language you know (or assume) is regular, you can choose $x$, $y$, and $z$ any which way you fancy, as long as you make sure $y$ is long enough. (But since you get $k$ from the lemma, what you actually need in the usual scenario is to provide is a procedure that explains how you're going to ...

2

Your answer to 1 is almost correct: It does not accept strings with zero $a$s such as $bc$. And it does not accept for example $acba$. Try something like $$[bc]^*(a[bc]^*a[bc]^*)^*$$ Based on this, you should have littel problems to find a regex for $4k$ number of $b$s and then $4k+1$ number of $b$s For the third task, first solve "length equals $3$", then ...

2

Suppose that the set of all primes is regular. Then it is recognised by a DFA with say $m$ states. Let $p$ be a prime whose binary expansion ends with $m$ zeros and a $1$, so that $$p=\underbrace{\cdots\ \cdots\ \cdots}_{n\ \rm in\ binary}\, \underbrace{00\cdots00}_{m\ \rm zeros}1=2^{m+1}n+1$$ for some $n$. (We know that there is such a prime from ...

2

Let us choose $w=a^mb^mc^{2m}$ with $m$ is the number of states of your automaton, and apply the pumping lemma you will have: there exists $x,y,z$ such that: $$\left\{\begin{matrix} w=xyz=a^mb^{m}c^{2m}& (1) & \\ |xy|\leq m& (2) & \\ |y|=d\geq 1& (3) & \\ xy^*z\in L_5& (4) & \\ \end{matrix}\right.$$ The equations $(1)$ ...

2

Given $M=(\{0,1\}^*,Q,q_0,'\cdot',\{q_f\})$ a finite state automaton recognizing $L$, The idea of the proof is the following, given a word in $L'$ we run in parallel $M$ over all smaller words then $w$ and if one of them reach the final state then the word is rejected otherwise we accept if it's accepted. so let's take $M'=\left\{\{0,1\right\}^*,Q',q_0', ... 2 A simple machine would have$2^6$nodes, one for every string of length seven at most$3$ones, plus one node for every string of length less than length$7$, plus a failure node. Basically, we "keep track" of the last$7$digits, unless we fail. I think you can probably prove that you can't do much better than this, in terms of reducing the number of ... 2 You're going to need a pumping length of at least$4$, since otherwise you have to break up the string$aaa$, and no shorter strings lie in$L$. If you choose a pumping length of 4, then you can use your method except in the case where the string starts$aab$or$bba$, in which case you choose$x$to be the first two letters and$y$to be the third letter. ... 1 Spoiler alert. My solutions. 1) $$L ::= Bc \mid Cd \\ B ::= aBbb \mid \epsilon \\ C ::= aaCb \mid \epsilon$$ 2) $$L ::= A \mid B \\ A ::= b \mid aAaa \\ B ::= aaba \mid aaBa$$ Notice that the base case of the B recursion is$aaba$, not$\epsilon$. This removes ambiguity. 1 Assume the existence of an automaton$M=(\Sigma^*,Q,q_0,'.',\{q_f\})$recognizing$L$, the very important observation here is :$w$is an element of$L_e$if there exists some words$uvx=0,1$such that$u(1-x)v$is accepted by$M_e$, the idea is to memorize the state of all words of this form,consider the following automaton ... 1 Hint: look at$L=a^*b$and$X=\{b\}$and calculate$LX^{-1}$as well as$X^{-1}L$. 1 Think in terms of the DFA accepting$L$. If you know the theorem that NFAs and DFAs are equivalent (their sets of accepted languages are both just the set of regular languages), you can construct an NFA by first applying the initial DFA transition from the start state as usual given$x_1$, and then having empty string transitions to all$| \Sigma |$... 1 I don't understand your second idea. But induction will work. Recall that $$(a+b)^* = \bigcup_n (a+b)^n$$ We will show by induction that$(a+b)^n \subseteq \alpha$. For$n=0$, this is true by 1), as$(a+b)^0 = \{\epsilon\}$. Now, suppose$(a+b)^n \subseteq \alpha$holds and consider a word$w \in (a+b)^{n+1}$. Then$w = w_1w'$with$w_1 \in \{a,b\}$... 1 Let$L$be a regular language. Then there is a surjective monoid morphism$f:A^* \to M$and a subset$P$of$M$such that$f^{-1}(P) = L$. I claim that$Root(L) = f^{-1}(Q)$where $$Q = \{m \in M \mid \exists n \in \mathbb{N} \text{ such that } u^n \in P \}$$ Thus$L'$is recognized by the finite monoid$M$and hence is regular. Proof of the claim. ... 1 Your construction seems to be correct, but there is a much shorter proof. Since$L$is regular, its complement$L^c$is also regular. Now$L' = LL^c$and since the product of two regular languages is regular,$L'$is regular. 1 Hint: Consider the language$D$defined by:$D$contains no word that has a$\mathtt b$in it. For every$n\in\mathbb N$, the word$\mathtt a^n$(that is,$\underbrace{\mathtt{aaa\ldots a}}_{n\text{ a's}}$) is in$D$if and only if it is not in$f(n)$. Can you prove that$D$is not in the list? 1 Let $$L_0 ={\{ c^n a^m b^p \mid n+m=p,p \geqslant 6}\} = {\{ c^n a^m b^{n+m} \mid n+m \geqslant 6}\}$$ If$L_0$was regular then, $$L_1 = L \cap \{a,b\}^* = \{ a^m b^m \mid m \geqslant 6\}$$ would also be regular (since$\{a,b\}^*$is regular and regular languages are closed under intersection). Similarly, since$\{a^m b^m \mid m \leqslant 5\}$is a ... 1 The class of regular languages is closed under intersection, so if$L_4$were a regular language, then$L_1\cap L_4=L_3$would be regular. But$L_3$is not regular, so$L_4$cannot be regular. The class of regular languages is also closed under union and concatenation, so you can argue in exactly the same way about$L_1\cup L_4$and$L_1L_4$. 1 You can prove the result without using automata. Let$A$be the alphabet, and let $$K = \{ u \in A^* \mid \text{ every prefix of u of odd length is in L} \}$$ Let$K^c$be the complement of$K$in$A^*. Then \begin{align} K^c &= \{ u \in A^* \mid \text{ there exists a prefix ofu$of odd length in$L^c$} \}\\ &= \{ u \in A^* \mid \text{ there ... 1 It’s almost right, but not quite. We know that$y=0^r$for some$r\ge 1$, so $$xy^kz=0^{p+(k-1)r}\#0^{2p}\;,$$ not$0^{p+k}\#0^{2p}$: the length of$y$need not be$1$. But we’re still okay, because$2\big(p+(k-1)r\big)=2p$if and only if$k=1$, so the pumped word is not in the language when$k\ne 1$. 1 HINT: Consider the strings$\underbrace{((\ldots((}_nx$for$n\in\Bbb N$. 1 You can try to answer this question (and other questions you posted) by using automata, but you can also use another way. Definition. A language$L$of$A^*$is recognized by a monoid$M$if there is a surjective monoid morphism$f:A^* \to M$and a subset$P$of$M$such that$f^{-1}(P) = L$. Fact. A language is regular if and only if it is recognized by ... 1 Suppose that$L$is regular. Then the pumping lemma says that there is a pumping length,$p$, such that if$s\in L$, and$|s|\ge p$, then$s$can be decomposed as$s=xyz$in such a way that$|xy|\le p$,$|y|\ge 1$, and$xy^kz\in L$for each$k\ge 0$. To use this to get a contradiction, you need to start with some$s\in L$that is at least$p$in length. I ... 1 Your mistake is in thinking that$a^{p+k}b(a^pb)^R\notin L$. In fact this word is in$L$. To see this, let$w=a$and$v=a^{p+k-2}b(a^pb)^R$; then$a^{p+k}b(a^pb)^R=ww^Rv$, so$a^{p+k}b(a^pb)^R\in L$. Every word that begins with two identical letters is in$L$. 1 The approach is not valid: the class of regular languages is closed under finite unions but not under arbitrary unions. Thus, your approach could be used to show that$\bigcup_{k\le n}L^k$is regular for each$n$, but it does not follow that$\bigcup_nL^n$is regular. To see why this must be so, let$L$be any language that is not regular, say ... 1 Consider that, if you have a DFA which accepts words in$L$, then it can be in one of finitely many states after it reads the first letter - so, to test if a word is in$L\ominus 1$, we just start the DFA at each of the states it could be in after one letter and if it accepts when started in any of these, the word is in$L\ominus 1\$ - and, if you know how to ...

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