# Tag Info

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

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

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

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