patternMinor
Converse of pumping lemma for regular expressions
Viewed 0 times
regularexpressionsconversepumpingforlemma
Problem
I want to come up with a language that satisfies the pumping lemma while not being a regular expression.
I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is not a regular expression, as it would not be possible to create an automata that recognizes it. This last part is where I'm having a bit of trouble, as I think I have the right idea, but can't formalize it. This language is just a regular expression $\big(\{0^i : i \in \mathbb{N}\}\big)$ concatenated with something that is not a regular expression $\big(\{0^i1^i: i \in \mathbb{N}\}\big)$.
Is my thought process correct? Can this be generalized? If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE? I believe so, because we know that if $L$ is a RE then so is $L^r$. And so we end up with $(L')^rL^r$, and we can use the contrapositive of the pumping lemma to prove this language is not regular. Any insight would be helpful!
I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is not a regular expression, as it would not be possible to create an automata that recognizes it. This last part is where I'm having a bit of trouble, as I think I have the right idea, but can't formalize it. This language is just a regular expression $\big(\{0^i : i \in \mathbb{N}\}\big)$ concatenated with something that is not a regular expression $\big(\{0^i1^i: i \in \mathbb{N}\}\big)$.
Is my thought process correct? Can this be generalized? If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE? I believe so, because we know that if $L$ is a RE then so is $L^r$. And so we end up with $(L')^rL^r$, and we can use the contrapositive of the pumping lemma to prove this language is not regular. Any insight would be helpful!
Solution
Yes, $L_>=\{0^i1^j: i > j > 0\} $ is a non-regular language.
However, it does not satisfy the pumping lemma for regular languages. Assume for the sake of contradiction that $p$ is a pumping length for $L_>$. Consider $w=0^{p+1}1^p$. Let $w=xyz$ with $|y|>1$ and $|xy|$ can be pumped up.
If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE?
No. A simple counterexample is $L=\Sigma^*$, the language of all words while $L'$ is any non-regular language that contains the empty word such as $\{a^{n^2}\mid n\in \Bbb N_0\}$. $LL'$ is still the language of all words, which is regular.
Exercise 1. Find two languages $A$ and $B$ such that
Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.
However, it does not satisfy the pumping lemma for regular languages. Assume for the sake of contradiction that $p$ is a pumping length for $L_>$. Consider $w=0^{p+1}1^p$. Let $w=xyz$ with $|y|>1$ and $|xy|$ can be pumped up.
If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE?
No. A simple counterexample is $L=\Sigma^*$, the language of all words while $L'$ is any non-regular language that contains the empty word such as $\{a^{n^2}\mid n\in \Bbb N_0\}$. $LL'$ is still the language of all words, which is regular.
Exercise 1. Find two languages $A$ and $B$ such that
- $A$ is regular
- $B$ is not regular
- $A\subsetneq B$
- $AB$ is regular.
Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.
Context
StackExchange Computer Science Q#111293, answer score: 3
Revisions (0)
No revisions yet.