Language contex-free
$begingroup$
$$L={a^kb^nc^md^tmid n+m=2(k+t)}.$$
So I am trying to figure out if this language is CFL. So trying to prove that it is not CFL with the pumping lemma, I am not getting anywhere (using the word $a^pb^{2p}c^{2p}d^p$). I also cannot find a grammar for this language. Any tips?
computer-science formal-languages context-free-grammar formal-grammar
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
$endgroup$
add a comment |
$begingroup$
$$L={a^kb^nc^md^tmid n+m=2(k+t)}.$$
So I am trying to figure out if this language is CFL. So trying to prove that it is not CFL with the pumping lemma, I am not getting anywhere (using the word $a^pb^{2p}c^{2p}d^p$). I also cannot find a grammar for this language. Any tips?
computer-science formal-languages context-free-grammar formal-grammar
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
$endgroup$
add a comment |
$begingroup$
$$L={a^kb^nc^md^tmid n+m=2(k+t)}.$$
So I am trying to figure out if this language is CFL. So trying to prove that it is not CFL with the pumping lemma, I am not getting anywhere (using the word $a^pb^{2p}c^{2p}d^p$). I also cannot find a grammar for this language. Any tips?
computer-science formal-languages context-free-grammar formal-grammar
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
$endgroup$
$$L={a^kb^nc^md^tmid n+m=2(k+t)}.$$
So I am trying to figure out if this language is CFL. So trying to prove that it is not CFL with the pumping lemma, I am not getting anywhere (using the word $a^pb^{2p}c^{2p}d^p$). I also cannot find a grammar for this language. Any tips?
computer-science formal-languages context-free-grammar formal-grammar
computer-science formal-languages context-free-grammar formal-grammar
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
edited Dec 27 '18 at 1:29
Math1000
19.1k31745
19.1k31745
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
asked Dec 27 '18 at 0:40
Angeld55Angeld55
565
565
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You are given that the number of $b$'s and $c$'s is twice the number of $a$'s and $d$'s.
Try to create a PDA for this grammar and see if you can build it.
Start with pushing two symbols on the stack for every $a$ and $d$ and popping one symbol for every $b$ and $c$.
But there's a problem. You'll encounter an empty stack after some amount of popping. When you do, do the reverse of what you were doing till now, that is, interchange pushing and popping. This way, you can build a deterministic PDA for your grammar.
answered Dec 27 '18 at 2:42
RahulRahul
212
$endgroup$
add a comment |
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%2f3053468%2flanguage-contex-free%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$
You are given that the number of $b$'s and $c$'s is twice the number of $a$'s and $d$'s.
Try to create a PDA for this grammar and see if you can build it.
Start with pushing two symbols on the stack for every $a$ and $d$ and popping one symbol for every $b$ and $c$.
But there's a problem. You'll encounter an empty stack after some amount of popping. When you do, do the reverse of what you were doing till now, that is, interchange pushing and popping. This way, you can build a deterministic PDA for your grammar.
answered Dec 27 '18 at 2:42
RahulRahul
212
$endgroup$
add a comment |
$begingroup$
You are given that the number of $b$'s and $c$'s is twice the number of $a$'s and $d$'s.
Try to create a PDA for this grammar and see if you can build it.
Start with pushing two symbols on the stack for every $a$ and $d$ and popping one symbol for every $b$ and $c$.
But there's a problem. You'll encounter an empty stack after some amount of popping. When you do, do the reverse of what you were doing till now, that is, interchange pushing and popping. This way, you can build a deterministic PDA for your grammar.
answered Dec 27 '18 at 2:42
RahulRahul
212
$endgroup$
add a comment |
$begingroup$
You are given that the number of $b$'s and $c$'s is twice the number of $a$'s and $d$'s.
Try to create a PDA for this grammar and see if you can build it.
Start with pushing two symbols on the stack for every $a$ and $d$ and popping one symbol for every $b$ and $c$.
But there's a problem. You'll encounter an empty stack after some amount of popping. When you do, do the reverse of what you were doing till now, that is, interchange pushing and popping. This way, you can build a deterministic PDA for your grammar.
answered Dec 27 '18 at 2:42
RahulRahul
212
$endgroup$
You are given that the number of $b$'s and $c$'s is twice the number of $a$'s and $d$'s.
Try to create a PDA for this grammar and see if you can build it.
Start with pushing two symbols on the stack for every $a$ and $d$ and popping one symbol for every $b$ and $c$.
But there's a problem. You'll encounter an empty stack after some amount of popping. When you do, do the reverse of what you were doing till now, that is, interchange pushing and popping. This way, you can build a deterministic PDA for your grammar.
answered Dec 27 '18 at 2:42
RahulRahul
212
answered Dec 27 '18 at 2:42
RahulRahul
212
answered Dec 27 '18 at 2:42
RahulRahul
212
answered Dec 27 '18 at 2:42
RahulRahul
212
212
add a comment |
add a comment |
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%2f3053468%2flanguage-contex-free%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
