How to define a grammar which creates a language from words of another grammar without one of the letters?
$begingroup$
Let $G=(V,T,P,S)$ be a context-free grammar without $epsilon$ rules. Define a context-free grammar $G'$ which creates a language which consists of all words from $L(G)$ without one of the letters of a word which belongs to $L(G)$. For example, if $abin L(G)$ then $ain L(G')$ and $bin L(G')$.
The solution to the problem is as follows:
Let $G'=(Vcup V', T,P',S')$.
$$
forall (Ato alpha)in Pimplies (Ato alpha)in P'\
forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha Bgamma)in P'\
forall (Ato alpha tgamma)in P, tin Timplies (Ato alphagamma)in P'
$$
Why $forall (Ato alpha Bgamma)in P'$, because $alpha, gamma$ are strings of stack symbols (not just letters) hence they cannot be divided (like for example, $forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha)in P'quadlandquad (Ato gamma)in P'$)?
proof-explanation formal-languages
asked Dec 15 '18 at 9:17
YosYos
1,1631823
$endgroup$
add a comment |
$begingroup$
Let $G=(V,T,P,S)$ be a context-free grammar without $epsilon$ rules. Define a context-free grammar $G'$ which creates a language which consists of all words from $L(G)$ without one of the letters of a word which belongs to $L(G)$. For example, if $abin L(G)$ then $ain L(G')$ and $bin L(G')$.
The solution to the problem is as follows:
Let $G'=(Vcup V', T,P',S')$.
$$
forall (Ato alpha)in Pimplies (Ato alpha)in P'\
forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha Bgamma)in P'\
forall (Ato alpha tgamma)in P, tin Timplies (Ato alphagamma)in P'
$$
Why $forall (Ato alpha Bgamma)in P'$, because $alpha, gamma$ are strings of stack symbols (not just letters) hence they cannot be divided (like for example, $forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha)in P'quadlandquad (Ato gamma)in P'$)?
proof-explanation formal-languages
asked Dec 15 '18 at 9:17
YosYos
1,1631823
$endgroup$
1
$begingroup$
I’m afraid I don’t understand what you are asking, but it may help to know there are some typos in the solution as written. The RHS is the second line should be $(A’ to alpha B’ gamma) in P’$ and the RHS in the third line should be $(A’to alphagamma) in P’$.
$endgroup$
– Erick Wong
Dec 24 '18 at 2:51
add a comment |
$begingroup$
Let $G=(V,T,P,S)$ be a context-free grammar without $epsilon$ rules. Define a context-free grammar $G'$ which creates a language which consists of all words from $L(G)$ without one of the letters of a word which belongs to $L(G)$. For example, if $abin L(G)$ then $ain L(G')$ and $bin L(G')$.
The solution to the problem is as follows:
Let $G'=(Vcup V', T,P',S')$.
$$
forall (Ato alpha)in Pimplies (Ato alpha)in P'\
forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha Bgamma)in P'\
forall (Ato alpha tgamma)in P, tin Timplies (Ato alphagamma)in P'
$$
Why $forall (Ato alpha Bgamma)in P'$, because $alpha, gamma$ are strings of stack symbols (not just letters) hence they cannot be divided (like for example, $forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha)in P'quadlandquad (Ato gamma)in P'$)?
proof-explanation formal-languages
asked Dec 15 '18 at 9:17
YosYos
1,1631823
$endgroup$
Let $G=(V,T,P,S)$ be a context-free grammar without $epsilon$ rules. Define a context-free grammar $G'$ which creates a language which consists of all words from $L(G)$ without one of the letters of a word which belongs to $L(G)$. For example, if $abin L(G)$ then $ain L(G')$ and $bin L(G')$.
The solution to the problem is as follows:
Let $G'=(Vcup V', T,P',S')$.
$$
forall (Ato alpha)in Pimplies (Ato alpha)in P'\
forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha Bgamma)in P'\
forall (Ato alpha tgamma)in P, tin Timplies (Ato alphagamma)in P'
$$
Why $forall (Ato alpha Bgamma)in P'$, because $alpha, gamma$ are strings of stack symbols (not just letters) hence they cannot be divided (like for example, $forall (Ato alpha Bgamma)in P, Bin Vimplies (Ato alpha)in P'quadlandquad (Ato gamma)in P'$)?
proof-explanation formal-languages
proof-explanation formal-languages
asked Dec 15 '18 at 9:17
YosYos
1,1631823
asked Dec 15 '18 at 9:17
YosYos
1,1631823
asked Dec 15 '18 at 9:17
YosYos
1,1631823
asked Dec 15 '18 at 9:17
YosYos
1,1631823
asked Dec 15 '18 at 9:17
YosYos
1,1631823
1,1631823
1
$begingroup$
I’m afraid I don’t understand what you are asking, but it may help to know there are some typos in the solution as written. The RHS is the second line should be $(A’ to alpha B’ gamma) in P’$ and the RHS in the third line should be $(A’to alphagamma) in P’$.
$endgroup$
– Erick Wong
Dec 24 '18 at 2:51
add a comment |
1
$begingroup$
I’m afraid I don’t understand what you are asking, but it may help to know there are some typos in the solution as written. The RHS is the second line should be $(A’ to alpha B’ gamma) in P’$ and the RHS in the third line should be $(A’to alphagamma) in P’$.
$endgroup$
– Erick Wong
Dec 24 '18 at 2:51
1
1
$begingroup$
I’m afraid I don’t understand what you are asking, but it may help to know there are some typos in the solution as written. The RHS is the second line should be $(A’ to alpha B’ gamma) in P’$ and the RHS in the third line should be $(A’to alphagamma) in P’$.
$endgroup$
– Erick Wong
Dec 24 '18 at 2:51
$begingroup$
I’m afraid I don’t understand what you are asking, but it may help to know there are some typos in the solution as written. The RHS is the second line should be $(A’ to alpha B’ gamma) in P’$ and the RHS in the third line should be $(A’to alphagamma) in P’$.
$endgroup$
– Erick Wong
Dec 24 '18 at 2:51
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
In your solution you missed some essential primes.
The idea is that the new grammar is just as the original one, except that it loses one of the generated symbols. But it should be clear that there is exactly one terminal that disappears. The primed symbol has the "task" of (not) generating that disappearing terminal. It hands this task to one of its successors.
Axiom $S'$, just like $S$, but remember a symbol has to be deleted in the derivation that follows.
If $Ato alphain P$ then $Ato alphain P'$ (Unprimed symbols behave as before.)
If $Ato alpha Bgammain P$ then $A'to alpha B' gammain P'$ (The task is delegated to a successor)
If $Ato alpha tgammain P$ ($t$ terminal) then $A'to alpha gammain P'$ (no more primes, terminal was deleted)
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
$endgroup$
$begingroup$
I have a similar question here maybe it will interest you as well math.stackexchange.com/questions/3085897/…
$endgroup$
– Yos
Jan 24 at 13:49
add a comment |
$begingroup$
Thanks for the post, stuck with the same problem. Yos, I think that in your question you mess grammar and pushdown automata representation (which has stack). In this case, I think that in the solution you've published, α,γ∈$bigl((V∪V′)∪Tbigr)^ast$. I'd be glad if anyone could approve that.
As for me, from the given notation, it is still unclear when the transmission from V to V' variables happens.
answered Dec 30 '18 at 23:47
grikogriko
12
$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%2f3040309%2fhow-to-define-a-grammar-which-creates-a-language-from-words-of-another-grammar-w%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In your solution you missed some essential primes.
The idea is that the new grammar is just as the original one, except that it loses one of the generated symbols. But it should be clear that there is exactly one terminal that disappears. The primed symbol has the "task" of (not) generating that disappearing terminal. It hands this task to one of its successors.
Axiom $S'$, just like $S$, but remember a symbol has to be deleted in the derivation that follows.
If $Ato alphain P$ then $Ato alphain P'$ (Unprimed symbols behave as before.)
If $Ato alpha Bgammain P$ then $A'to alpha B' gammain P'$ (The task is delegated to a successor)
If $Ato alpha tgammain P$ ($t$ terminal) then $A'to alpha gammain P'$ (no more primes, terminal was deleted)
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
$endgroup$
$begingroup$
I have a similar question here maybe it will interest you as well math.stackexchange.com/questions/3085897/…
$endgroup$
– Yos
Jan 24 at 13:49
add a comment |
$begingroup$
In your solution you missed some essential primes.
The idea is that the new grammar is just as the original one, except that it loses one of the generated symbols. But it should be clear that there is exactly one terminal that disappears. The primed symbol has the "task" of (not) generating that disappearing terminal. It hands this task to one of its successors.
Axiom $S'$, just like $S$, but remember a symbol has to be deleted in the derivation that follows.
If $Ato alphain P$ then $Ato alphain P'$ (Unprimed symbols behave as before.)
If $Ato alpha Bgammain P$ then $A'to alpha B' gammain P'$ (The task is delegated to a successor)
If $Ato alpha tgammain P$ ($t$ terminal) then $A'to alpha gammain P'$ (no more primes, terminal was deleted)
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
$endgroup$
$begingroup$
I have a similar question here maybe it will interest you as well math.stackexchange.com/questions/3085897/…
$endgroup$
– Yos
Jan 24 at 13:49
add a comment |
$begingroup$
In your solution you missed some essential primes.
The idea is that the new grammar is just as the original one, except that it loses one of the generated symbols. But it should be clear that there is exactly one terminal that disappears. The primed symbol has the "task" of (not) generating that disappearing terminal. It hands this task to one of its successors.
Axiom $S'$, just like $S$, but remember a symbol has to be deleted in the derivation that follows.
If $Ato alphain P$ then $Ato alphain P'$ (Unprimed symbols behave as before.)
If $Ato alpha Bgammain P$ then $A'to alpha B' gammain P'$ (The task is delegated to a successor)
If $Ato alpha tgammain P$ ($t$ terminal) then $A'to alpha gammain P'$ (no more primes, terminal was deleted)
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
$endgroup$
In your solution you missed some essential primes.
The idea is that the new grammar is just as the original one, except that it loses one of the generated symbols. But it should be clear that there is exactly one terminal that disappears. The primed symbol has the "task" of (not) generating that disappearing terminal. It hands this task to one of its successors.
Axiom $S'$, just like $S$, but remember a symbol has to be deleted in the derivation that follows.
If $Ato alphain P$ then $Ato alphain P'$ (Unprimed symbols behave as before.)
If $Ato alpha Bgammain P$ then $A'to alpha B' gammain P'$ (The task is delegated to a successor)
If $Ato alpha tgammain P$ ($t$ terminal) then $A'to alpha gammain P'$ (no more primes, terminal was deleted)
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
edited Jan 24 at 8:10
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
answered Jan 24 at 2:25
Hendrik JanHendrik Jan
1,733818
1,733818
$begingroup$
I have a similar question here maybe it will interest you as well math.stackexchange.com/questions/3085897/…
$endgroup$
– Yos
Jan 24 at 13:49
add a comment |
$begingroup$
I have a similar question here maybe it will interest you as well math.stackexchange.com/questions/3085897/…
$endgroup$
– Yos
Jan 24 at 13:49
$begingroup$
I have a similar question here maybe it will interest you as well math.stackexchange.com/questions/3085897/…
$endgroup$
– Yos
Jan 24 at 13:49
$begingroup$
I have a similar question here maybe it will interest you as well math.stackexchange.com/questions/3085897/…
$endgroup$
– Yos
Jan 24 at 13:49
add a comment |
$begingroup$
Thanks for the post, stuck with the same problem. Yos, I think that in your question you mess grammar and pushdown automata representation (which has stack). In this case, I think that in the solution you've published, α,γ∈$bigl((V∪V′)∪Tbigr)^ast$. I'd be glad if anyone could approve that.
As for me, from the given notation, it is still unclear when the transmission from V to V' variables happens.
answered Dec 30 '18 at 23:47
grikogriko
12
$endgroup$
add a comment |
$begingroup$
Thanks for the post, stuck with the same problem. Yos, I think that in your question you mess grammar and pushdown automata representation (which has stack). In this case, I think that in the solution you've published, α,γ∈$bigl((V∪V′)∪Tbigr)^ast$. I'd be glad if anyone could approve that.
As for me, from the given notation, it is still unclear when the transmission from V to V' variables happens.
answered Dec 30 '18 at 23:47
grikogriko
12
$endgroup$
add a comment |
$begingroup$
Thanks for the post, stuck with the same problem. Yos, I think that in your question you mess grammar and pushdown automata representation (which has stack). In this case, I think that in the solution you've published, α,γ∈$bigl((V∪V′)∪Tbigr)^ast$. I'd be glad if anyone could approve that.
As for me, from the given notation, it is still unclear when the transmission from V to V' variables happens.
answered Dec 30 '18 at 23:47
grikogriko
12
$endgroup$
Thanks for the post, stuck with the same problem. Yos, I think that in your question you mess grammar and pushdown automata representation (which has stack). In this case, I think that in the solution you've published, α,γ∈$bigl((V∪V′)∪Tbigr)^ast$. I'd be glad if anyone could approve that.
As for me, from the given notation, it is still unclear when the transmission from V to V' variables happens.
answered Dec 30 '18 at 23:47
grikogriko
12
edited Dec 31 '18 at 0:09
answered Dec 30 '18 at 23:47
grikogriko
12
answered Dec 30 '18 at 23:47
grikogriko
12
answered Dec 30 '18 at 23:47
grikogriko
12
12
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%2f3040309%2fhow-to-define-a-grammar-which-creates-a-language-from-words-of-another-grammar-w%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
1
$begingroup$
I’m afraid I don’t understand what you are asking, but it may help to know there are some typos in the solution as written. The RHS is the second line should be $(A’ to alpha B’ gamma) in P’$ and the RHS in the third line should be $(A’to alphagamma) in P’$.
$endgroup$
– Erick Wong
Dec 24 '18 at 2:51