0
$\begingroup$

Check this problem (1.71 from Sipser 3rd edition):

Let $\sum = \{0,1\}$. Let $A =\{0^ku0^k \ | \ k \ge 1 \ and \ u \in \sum^*$}. Show that $A$ is regular.

$u$ can be $\{0,00,000,...,01,011,...,1,11,111,11111...etc\}$

So, the language $0^k10^k \ with \ k\geq1$ should be regular, $u=1 \in \sum^*$, but is not regular according to pumping lemma, or because you need to count infinite states at the start and end.

I thought a regular language was a set of strings which every string being recognizable by a finite automata.

$\endgroup$
1
$\begingroup$

Well, the language $L=\{0^k10^m\mid k,m\in{\Bbb N}_0\}$ is regular, but the subset $\{0^k10^k\mid k\in{\Bbb N}_0\}$ is not. The accepting automaton for $L$ doesn't care how many $0$'s after the prefix $0^k1$ follow.

$\endgroup$
1
$\begingroup$

It's not necessary that the subset of a regular language should also be regular. In your example, observe that any string starting and ending with $0$ belongs to the language, and any other string does not.

$\endgroup$
  • $\begingroup$ But the problem says that $u$ belongs to $\{0,1\}^*$, accordidng to my interpretation, for every u belonging to this set the resulting string should be regular. $\endgroup$ – Carlitos_30 Apr 27 at 15:52
  • 1
    $\begingroup$ @Carlitos_30 Strings aren't regular, languages are. In this question, the language A contains all those strings which match the "template" given. $\endgroup$ – sriram B Apr 27 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.