Converse of pumping lemma for regular expressionsPumping lemma for simple finite regular languagesProofs using the regular pumping lemmaShow that the pumping lemmas for context-free and regular languages are equivalent for unary languagesProof that a language is not regular using pumping lemmaShowing that the pumping lemma cannot prove that some language is not regularWhat's wrong with my pumping lemma proof?How to show that a turtle graphic language is not regular?Prove this language is non-regularPumping-Lemma regular languages: Consider multiple cases?How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
How do I tell my girlfriend she's been buying me books by the wrong author for the last nine months?
How to track mail undetectably?
Active wildlife outside the window- Good or Bad for Cat psychology?
What is my external HDD doing?
Why do movie directors use brown tint on Mexico cities?
How does the 'five minute adventuring day' affect class balance?
What's the point of stochastic volatiliy models if you can use local volatility?
Odd PCB Layout for Voltage Regulator
Robots in a spaceship
iMac 2019: Can I mix the old modules with the new ones when upgrading RAM?
What was the first science fiction or fantasy multiple choice book?
Disk usage confusion: 10G missing on Linux home partition on SSD
What does 'in attendance' mean on an England death certificate?
Cat files in subfolders in order given by a list
What could a Medieval society do with excess animal blood?
Why are symbols not written in words?
How does mmorpg store data?
Installed software from source, how to say yum not to install it from package?
Russian equivalents of 能骗就骗 (if you can cheat, then cheat)
Basis and cardinality
Having to constantly redo everything because I don't know how to do it
Five 5-cent coins touching each other
How soon after takeoff can you recline your airplane seat?
How do I present a future free of gender stereotypes without being jarring or overpowering the narrative?
Converse of pumping lemma for regular expressions
Pumping lemma for simple finite regular languagesProofs using the regular pumping lemmaShow that the pumping lemmas for context-free and regular languages are equivalent for unary languagesProof that a language is not regular using pumping lemmaShowing that the pumping lemma cannot prove that some language is not regularWhat's wrong with my pumping lemma proof?How to show that a turtle graphic language is not regular?Prove this language is non-regularPumping-Lemma regular languages: Consider multiple cases?How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
$begingroup$
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 mathbbNbig)$ concatenated with something that is not a regular expression $big(0^i1^i: i in mathbbNbig)$.
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!
regular-languages regular-expressions pumping-lemma
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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 mathbbNbig)$ concatenated with something that is not a regular expression $big(0^i1^i: i in mathbbNbig)$.
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!
regular-languages regular-expressions pumping-lemma
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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 mathbbNbig)$ concatenated with something that is not a regular expression $big(0^i1^i: i in mathbbNbig)$.
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!
regular-languages regular-expressions pumping-lemma
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
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 mathbbNbig)$ concatenated with something that is not a regular expression $big(0^i1^i: i in mathbbNbig)$.
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!
regular-languages regular-expressions pumping-lemma
regular-languages regular-expressions pumping-lemma
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
asked 8 hours ago
mathmathmathmathmathmath
132 bronze badges
132 bronze badges
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
mathmathmath is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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+11^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.
The most we can say is that all words in $L_>$ 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^2mid nin 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- $Asubsetneq B$
$AB$ is regular.
Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
$endgroup$
$begingroup$
Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $varnothing$, then I believe it works :)
$endgroup$
– mathmathmath
7 hours ago
$begingroup$
@mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty.
$endgroup$
– Apass.Jack
6 hours ago
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
mathmathmath is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f111293%2fconverse-of-pumping-lemma-for-regular-expressions%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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+11^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.
The most we can say is that all words in $L_>$ 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^2mid nin 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- $Asubsetneq B$
$AB$ is regular.
Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
$endgroup$
$begingroup$
Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $varnothing$, then I believe it works :)
$endgroup$
– mathmathmath
7 hours ago
$begingroup$
@mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty.
$endgroup$
– Apass.Jack
6 hours ago
add a comment |
$begingroup$
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+11^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.
The most we can say is that all words in $L_>$ 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^2mid nin 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- $Asubsetneq B$
$AB$ is regular.
Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
$endgroup$
$begingroup$
Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $varnothing$, then I believe it works :)
$endgroup$
– mathmathmath
7 hours ago
$begingroup$
@mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty.
$endgroup$
– Apass.Jack
6 hours ago
add a comment |
$begingroup$
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+11^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.
The most we can say is that all words in $L_>$ 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^2mid nin 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- $Asubsetneq B$
$AB$ is regular.
Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
$endgroup$
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+11^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.
The most we can say is that all words in $L_>$ 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^2mid nin 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- $Asubsetneq B$
$AB$ is regular.
Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
edited 7 hours ago
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
answered 7 hours ago
Apass.JackApass.Jack
17.8k1 gold badge12 silver badges47 bronze badges
17.8k1 gold badge12 silver badges47 bronze badges
$begingroup$
Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $varnothing$, then I believe it works :)
$endgroup$
– mathmathmath
7 hours ago
$begingroup$
@mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty.
$endgroup$
– Apass.Jack
6 hours ago
add a comment |
$begingroup$
Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $varnothing$, then I believe it works :)
$endgroup$
– mathmathmath
7 hours ago
$begingroup$
@mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty.
$endgroup$
– Apass.Jack
6 hours ago
$begingroup$
Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $varnothing$, then I believe it works :)
$endgroup$
– mathmathmath
7 hours ago
$begingroup$
Thank you for your answer, apreciate it a lot! In regards to Exercise 1, if you choose A = $varnothing$, then I believe it works :)
$endgroup$
– mathmathmath
7 hours ago
$begingroup$
@mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty.
$endgroup$
– Apass.Jack
6 hours ago
$begingroup$
@mathmathmath nice answer. To make it more difficult, I should have added $A$ is not empty.
$endgroup$
– Apass.Jack
6 hours ago
add a comment |
mathmathmath is a new contributor. Be nice, and check out our Code of Conduct.
mathmathmath is a new contributor. Be nice, and check out our Code of Conduct.
mathmathmath is a new contributor. Be nice, and check out our Code of Conduct.
mathmathmath is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f111293%2fconverse-of-pumping-lemma-for-regular-expressions%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
