Tag Info

Hot answers tagged

2

What you have generates the language $\{aca,acb,acc,bca,bcb,bcc,cca,ccb,ccc\}$. As you can see, it’s far from being what you want: it’s missing most of the words that you do want, and it contains six words that you don’t want. The trick is to generate the $w$ and $w^R$ parts at the same time. Suppose that you have the productions $E\to aEa$ and $E\to cEc$. ...


2

Yes, they are. You can simplify both to $$\Sigma^+\mathtt{0}$$ for $\Sigma = \{\mathtt{0},\mathtt{1}\}$, that is, $$(\mathtt{0}\cup\mathtt{1})(\mathtt{0}\cup\mathtt{1})^*\mathtt{0}$$ The crucial part is to observe that, after you cleared the initial state (i.e. read the first symbol), whatever you do, and wherever you are, after reading symbol $\mathtt{0}$ ...


2

The regular expression $a^*b^*$ matches any string $a^nb^m$, so it gives you more than the language you want. The simplest way to show that the language is not regular is to note that $$\{a^nb^n\mid n\in{\Bbb N}\} =\{a^nb^m\mid n,m\in{\Bbb N}\}-\{a^nb^m\mid n\ne m\}\ .$$ If your set were regular then the RHS would be regular, so the LHS would be regular. ...


2

Suppose that $M=\langle Q,\Sigma,\delta,q_0,F\rangle$ is a DFA that recognizes $L'$; we can construct a DFA $M'=\langle Q',\Sigma,\delta',q_0',F'\rangle$ that recognizes $L$ as follows. $Q'$ is the set of all functions from $Q$ to $Q$. A state $f\in Q'$ is an acceptor state in $M'$ if $f^3(q_0)\in F$, where $f^3(q)=f(f(f(q)))$; i.e., $F'=\{f\in ...


1

Here is one calculation (inspired by dtldarek's comment): Let $S_k$, $k=0,1,2$ represent the states above. We have the equations $S_1 = (0|1) \big | S_1 1 \big | S_2 1$, $S_2 = S_1 0 \big | S_2 0 $. Solving for $S_2$ gives $S_2 = S_1 0 0^*$, then $S_1 = (0|1) \big | S_1 1 \big | S_1 0 0^* 1$, which reduces to $S_1 = (0|1) (1 | 0 0^* 1)^*$, and so $S_2 = ...


1

In order to tackle these questions, it's useful to know what is and what isn't a regular language :-). Wikipedia is helpful. http://en.wikipedia.org/wiki/Regular_language Regarding question (ii), for example, we can take $M = \left\{a^nb^n \mid n \in \mathbb N_0\right\}$ and $L = \left\{ab\right\} \subseteq M.$ Since $M$ is not regular, but $L$ is, (ii) is ...


1

(i) is clearly false. Take $L$ any non-regular language over the alphabet $A$ and $M=A^*$ (which is regular). (ii) is clearly false, too. Take $L=\emptyset$ (which is regular) and M any non-regular language. (iii) is true. The complement of a regular language is always a regular language. Therefore, the complement of a non-regular language must be ...


1

Hi.Nop, it does not have to be the same $n$. $L_1L_2=\{xy: x\in L_1,y\in L_2\}$. So, if you want to see if a string is in that set, you want to factor it in two parts, the prefix part must to be in $L_1$ and the suffix part must to be in $L_2$. As an example, $aabbcccc\in L_1L_2$ but $aabb\not \in L_1L_2$.Hope this helps.


1

Hint: Let $M_y$ be the automaton that recognizes suffixes from $L$ and $M_x$ be the automaton that recognizes prefixes from $L$. Neither automaton has any transitions on $Z$, since $Z\notin\Sigma$. Could you connect $M_y$ to $M_x$ somehow, and let $M_y$ recognize the $y$ part of the input string, and $M_x$ recognize the $x$ part?


1

Suppose that the language is regular, and let $p$ be the pumping length. Consider the word $w=a^{2^p}$; $2^p\ge p$, so the pumping lemma says that $w$ can be decomposed as $xyz$ in such a way that $|y|\ge 1$, and $xy^kz$ is in the language for every $k\ge 0$. There must be integers $r,s$, and $t$ such that $x=a^r$, $y=a^s$, and $z=a^t$, where $s\ge 1$, and ...


1

Suppose the language is regular, then there is a DFA for it with $n$ states. Then for the strings $a^{2^i}$ for $1 \leq i \leq n + 1$ at least 2 of them must be in the same accept state by the pigeonhole principle. Say that the two strings are $a^{2^j}$ and $a^{2^k}$ with $j < k$. Since they are in the same state, so long as we append the same string to ...



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