(Originally posted on Math-Stackexchange) https://math.stackexchange.com/questions/2982949/regular-languages-and-regular-expressions

$\Sigma:=\{a_1,\cdots ,a_\Delta\}$ finite alphabet
$\Sigma^n= \underbrace{\Sigma \times \Sigma \times \cdots \times \Sigma}_{n}$ Words of length $=n$
$\Sigma^*= \bigcup \limits_{n\geq0} \Sigma^n$ Set of all finite words
$L \subseteq \Sigma^*$ Language

I'm trying to prove, that the following statements are either true or false. Unfortunately, I'm having a hard time finding formal proofs for my answers. I hope you can help me out a bit.

Let $A,B$ be two subsets of $\{0,1\}^*$

  1. If $A$ is regular pumpable and $B \subseteq A$, then B is regular pumpable too.
  2. If $A$ not regular pumpable and $A ⊆ B$, then $B$ is not regular pumpable too.

  3. If $A$ is regular and $B \subseteq A$, then B is regular too.

  4. If $A \cap B$ is regular, then $A$ and $B$ are regular too.

  5. There is at least one finite language on the alphabet $\{0,1\}$, that doesn't meet the pumping lemma.

  • $\begingroup$ Each one is false. $\endgroup$ – John L. Nov 3 '18 at 18:48
  • $\begingroup$ @Apass.Jack How do you come do that conclusion? $\endgroup$ – Doesbaddel Nov 3 '18 at 18:58
  • 2
    $\begingroup$ Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Nov 4 '18 at 7:19
  • $\begingroup$ @D.W. Sorry for that. $\endgroup$ – Doesbaddel Nov 4 '18 at 11:48
  • 1
    $\begingroup$ I'm voting to close as too broad, since these are largely unrelated questions. Also, you've given no indication of what you don't understand about them, so it's hard to know what you're looking for in an answer. 3 and 4 are already covered in other questions on this site. 5 is, to me, so vaguely phrased as to be unanswerable. What is "pumping lemma rules"? Does it just mean "the pumping lemma"? Or are we to assume that the pumping lemma is "Regular implies 'pumping lemma rules'"? Or "Every regular language obeys 'pumping lemma rules'" or something else? Those could give different answers. $\endgroup$ – David Richerby Nov 4 '18 at 13:48

I'm assuming regular pumpable means regular? you should check out Apass Jack's answer by the way, I'm just going to elaborate a bit.

  1. Your proof is not correct, since the fact that "pumped" strings are in $ A$ doesn't imply it is in $B$. Take for instance $ A = 0^*, B = (00)^*,$ and pumping length = 1. The same pumping length can't really be transferred to B.

  2. The fact that $ A $ is not pumpable doesn't immediately transfer to $ B$ not being pumpable. When you do proofs you should be really convinced that the implications work, and a good way to check that is by making counter examples. For instance, let $ A = \{ 0^n1^n | n \in \mathbb{N} \} $ and $ B = (0+1)^n $.

  3. I'm not sure how this differs from 1.

  4. Certainly you can think of none regular languages that have nothing in common? Or you can chose a none regular language and change its alphabet (like $ 0^n1^n $ and $ a^nb^n$). Obviously their intersection is regular (the empty set), but neither of them are.

  5. To prove that all finite languages are regular, you can construct a DFA that has a branch dedicated to each string in a finite language. The states are finite since there are only finite number of such strings, and obviously that this DFA accepts all and only strings in the finite language.
  • $\begingroup$ Thank you very much, I recreated all your answers on my own and it's indeed obvious. $\endgroup$ – Doesbaddel Nov 4 '18 at 11:50

In all following counterexamples, $A$ and $B$ are subset of the full language $F=\{0,1\}^*$. Note that $F$ is a regular language.

If $A$ is regular pumpable $B\subseteq A$, then $B$ is regular pumpable too.

Counterexample: $A=F$ while $B$ is any non-regular-pumpable language.

(It is taken for granted that a language being regular-pumpable means it is able to be pumped like a regular language. There are different ways to define being able to be pumped like a regular language; however it is defined, $\{0^n1^n\mid n\ge 0\}$ will not be regular pumpable. I made this note since some non-regular languages can be pumped like a regular language. For example, $\{ 01^{n^2} \mid n \ge 1 \} \cup \{ 0^kw \mid k\neq 1, w\in \{1\}^* \}$ is non-regular but can be pumped by the most common version of the pumping lemma for regular languages.)

(In case "regular pumpable" for a language is defined simply as "regular", just let $A=F$ and B be any non-regular language for a counterexample.)

If $A$ not regular pumpable and $A\subseteq B$, then $B$ is not regular pumpable too.

Counterexample: $B=F$.

If $A$ is regular and $B\subseteq A$, then $B$ is regular too.

Counterexample: $A=F$ while $B$ is non-regular.

If $A\cap B$ is regular, then $A$ and $B$ are regular too.

Counterexample: $A$ is not regular while $B=F\setminus A$. $A\cap B=\emptyset$ is regular.

There is at least one finite language on the alphabet $\{0,1\}$, that doesn't meet the pumping lemma rules.

That is not true. All finite languages are regular and, thus, meeting the pumping lemma rules.

How do you come to that conclusion?

Mostly experience and knowledge plus a bit of luck. Before proving any proposition, you would like to do some sanity check with some simple and/or extreme cases. For example, you might have noticed that I have used the simple and extreme language $F$ several times.

  • $\begingroup$ Thank you very much, this helped me alot and I could recreate all your answers on my own. $\endgroup$ – Doesbaddel Nov 4 '18 at 11:51

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.