Verification of “Prove/Disprove that the language $L = { a^kba^{2k}ba^{3k} | k geq 0}$ is context free.”
$begingroup$
I attempt to show that the language $L = { a^kba^{2k}ba^{3k} | k geq 0}$ is not context free by applying the Pumping lemma for context-free languages.
This is achieved by a proof by contradiction by first assuming that $L$ is context free, in which case arbitrarily long strings in $L$ should be able to be "pumped" and still produce strings inside $L$. By "pumping" strings in $L$ to produce other strings which are not contained in $L$, then it cannot be true that the language $L$ is context free.
Progress so far:
The pumping lemma states that every string $s$ in $L$ can be written in the form
$ s = uvwxy$
with substrings $u, v, w, x, y$
such that
- $|vx| geq 1$
- $|vwx| leq p$
$uv^nwx^ny in L$ for all $n geq 0$
so a suitable decomposition into the substrings $u, v, w, x, y$ must be found.
My informal approach is to consider on a case by case basis that each decomposition fails.
case 1:
If only the letter b is pumped, then there will be more than two b's the final string, which cannot be in L. For example:
$u = a^k, v = b, w = a^{2k}, x = b, y = a^{3k}$
by condition 3, $s = uv^nwx^ny notin L$ for $n = 2$
case 2:
If only the letter a is pumped, then the distribution of the letter a in the pumped string will no longer be valid. For example:
$u = varnothing, v = a^k, w = ba^{2k}b, x = a^{3k}, y = varnothing$
case 3:
If both the letters a and b are pumped, then the order of letters will be invalid in the pumped string.
For example:
$u = varnothing, v = a^kb, w = a^k, x = a^kb, y = a^{3k}$
case 4:
The case that neither the letter a nor the letter b is pumped fails because of the first condition.
In this solution I have neglected to consider both defining a pumping length $p$ ($p$ is still conceptually difficult for me and I don't know how to correctly define it) as well as the second condition of the pumping lemma.
I would be greatly appreciative for any assistance in this, as well as verifying/formalizing the above proposed solution.
proof-verification computer-science context-free-grammar pumping-lemma
asked Jan 13 at 17:09
OscarOscar
351111
$endgroup$
add a comment |
$begingroup$
I attempt to show that the language $L = { a^kba^{2k}ba^{3k} | k geq 0}$ is not context free by applying the Pumping lemma for context-free languages.
This is achieved by a proof by contradiction by first assuming that $L$ is context free, in which case arbitrarily long strings in $L$ should be able to be "pumped" and still produce strings inside $L$. By "pumping" strings in $L$ to produce other strings which are not contained in $L$, then it cannot be true that the language $L$ is context free.
Progress so far:
The pumping lemma states that every string $s$ in $L$ can be written in the form
$ s = uvwxy$
with substrings $u, v, w, x, y$
such that
- $|vx| geq 1$
- $|vwx| leq p$
$uv^nwx^ny in L$ for all $n geq 0$
so a suitable decomposition into the substrings $u, v, w, x, y$ must be found.
My informal approach is to consider on a case by case basis that each decomposition fails.
case 1:
If only the letter b is pumped, then there will be more than two b's the final string, which cannot be in L. For example:
$u = a^k, v = b, w = a^{2k}, x = b, y = a^{3k}$
by condition 3, $s = uv^nwx^ny notin L$ for $n = 2$
case 2:
If only the letter a is pumped, then the distribution of the letter a in the pumped string will no longer be valid. For example:
$u = varnothing, v = a^k, w = ba^{2k}b, x = a^{3k}, y = varnothing$
case 3:
If both the letters a and b are pumped, then the order of letters will be invalid in the pumped string.
For example:
$u = varnothing, v = a^kb, w = a^k, x = a^kb, y = a^{3k}$
case 4:
The case that neither the letter a nor the letter b is pumped fails because of the first condition.
In this solution I have neglected to consider both defining a pumping length $p$ ($p$ is still conceptually difficult for me and I don't know how to correctly define it) as well as the second condition of the pumping lemma.
I would be greatly appreciative for any assistance in this, as well as verifying/formalizing the above proposed solution.
proof-verification computer-science context-free-grammar pumping-lemma
asked Jan 13 at 17:09
OscarOscar
351111
$endgroup$
add a comment |
$begingroup$
I attempt to show that the language $L = { a^kba^{2k}ba^{3k} | k geq 0}$ is not context free by applying the Pumping lemma for context-free languages.
This is achieved by a proof by contradiction by first assuming that $L$ is context free, in which case arbitrarily long strings in $L$ should be able to be "pumped" and still produce strings inside $L$. By "pumping" strings in $L$ to produce other strings which are not contained in $L$, then it cannot be true that the language $L$ is context free.
Progress so far:
The pumping lemma states that every string $s$ in $L$ can be written in the form
$ s = uvwxy$
with substrings $u, v, w, x, y$
such that
- $|vx| geq 1$
- $|vwx| leq p$
$uv^nwx^ny in L$ for all $n geq 0$
so a suitable decomposition into the substrings $u, v, w, x, y$ must be found.
My informal approach is to consider on a case by case basis that each decomposition fails.
case 1:
If only the letter b is pumped, then there will be more than two b's the final string, which cannot be in L. For example:
$u = a^k, v = b, w = a^{2k}, x = b, y = a^{3k}$
by condition 3, $s = uv^nwx^ny notin L$ for $n = 2$
case 2:
If only the letter a is pumped, then the distribution of the letter a in the pumped string will no longer be valid. For example:
$u = varnothing, v = a^k, w = ba^{2k}b, x = a^{3k}, y = varnothing$
case 3:
If both the letters a and b are pumped, then the order of letters will be invalid in the pumped string.
For example:
$u = varnothing, v = a^kb, w = a^k, x = a^kb, y = a^{3k}$
case 4:
The case that neither the letter a nor the letter b is pumped fails because of the first condition.
In this solution I have neglected to consider both defining a pumping length $p$ ($p$ is still conceptually difficult for me and I don't know how to correctly define it) as well as the second condition of the pumping lemma.
I would be greatly appreciative for any assistance in this, as well as verifying/formalizing the above proposed solution.
proof-verification computer-science context-free-grammar pumping-lemma
asked Jan 13 at 17:09
OscarOscar
351111
$endgroup$
I attempt to show that the language $L = { a^kba^{2k}ba^{3k} | k geq 0}$ is not context free by applying the Pumping lemma for context-free languages.
This is achieved by a proof by contradiction by first assuming that $L$ is context free, in which case arbitrarily long strings in $L$ should be able to be "pumped" and still produce strings inside $L$. By "pumping" strings in $L$ to produce other strings which are not contained in $L$, then it cannot be true that the language $L$ is context free.
Progress so far:
The pumping lemma states that every string $s$ in $L$ can be written in the form
$ s = uvwxy$
with substrings $u, v, w, x, y$
such that
- $|vx| geq 1$
- $|vwx| leq p$
$uv^nwx^ny in L$ for all $n geq 0$
so a suitable decomposition into the substrings $u, v, w, x, y$ must be found.
My informal approach is to consider on a case by case basis that each decomposition fails.
case 1:
If only the letter b is pumped, then there will be more than two b's the final string, which cannot be in L. For example:
$u = a^k, v = b, w = a^{2k}, x = b, y = a^{3k}$
by condition 3, $s = uv^nwx^ny notin L$ for $n = 2$
case 2:
If only the letter a is pumped, then the distribution of the letter a in the pumped string will no longer be valid. For example:
$u = varnothing, v = a^k, w = ba^{2k}b, x = a^{3k}, y = varnothing$
case 3:
If both the letters a and b are pumped, then the order of letters will be invalid in the pumped string.
For example:
$u = varnothing, v = a^kb, w = a^k, x = a^kb, y = a^{3k}$
case 4:
The case that neither the letter a nor the letter b is pumped fails because of the first condition.
In this solution I have neglected to consider both defining a pumping length $p$ ($p$ is still conceptually difficult for me and I don't know how to correctly define it) as well as the second condition of the pumping lemma.
I would be greatly appreciative for any assistance in this, as well as verifying/formalizing the above proposed solution.
proof-verification computer-science context-free-grammar pumping-lemma
proof-verification computer-science context-free-grammar pumping-lemma
asked Jan 13 at 17:09
OscarOscar
351111
asked Jan 13 at 17:09
OscarOscar
351111
asked Jan 13 at 17:09
OscarOscar
351111
asked Jan 13 at 17:09
OscarOscar
351111
asked Jan 13 at 17:09
OscarOscar
351111
351111
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fmath.stackexchange.com%2fquestions%2f3072254%2fverification-of-prove-disprove-that-the-language-l-akba2kba3k-k%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3072254%2fverification-of-prove-disprove-that-the-language-l-akba2kba3k-k%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
