Regular languages with seemingly-unbounded substrings

108 Views Asked by At

The problem I am concerned with is in two parts: proving that $A=\{0^ku0^k\mid k\ge 1 \text{ and } u \in \Sigma^*\}$ is regular, and proving that $B=\{0^k1u0^k\mid k\ge 1 \text{ and } u \in \Sigma^*\}$ is not regular (where $\Sigma = \{0,1\}$). Intuitively, I don't see why $A$ is regular to begin with. The non-regular language $\{a^nb^n\mid n\ge 1\}$ comes to mind; a finite automaton cannot recognize it. Once that is created, I don't see how $B$ is not regular, though I will start by attempting to prove that with the pumping lemma. Any hints as to what I'm missing (mostly about $A$) would be greatly appreciated.

Edit: I saw the pattern after using the pumping lemma to disprove B. Letting a string $s=0^p10^p$ shows $x=0^k$, $y=0^m$, and $z=0^{p-k-m}10^p$. Then $xy^2z$ would simplify to $0^{p+m}10^p$, which I can then prove cannot be written in a form recognizable to $B$. $A$ is more easily proven once seeing this.

1

There are 1 best solutions below

0
On BEST ANSWER

Hints. Compare $A$ with the language $0\{0,1\}^*0$. For $B$, take its intersection with $0^*10^*$.