Mixing
How to transition from context-free grammar $G$ to to context-free grammar which starts and ends with...
$begingroup$
Given context-free grammar $G$ whose terminal letters are ${a,b,c,d}$ how can we transition to context-free grammar which contains the words from the language that $G$ creates but which start with $a$ and end with $d$?
I guess we could create new production rules where for example $Ato aX$ from $G$ would also be in $G'$ but how can we determine whether a production rule for middle state come from some rule which starts with $a$ and eventually end with $d$?
context-free-grammar
asked Jan 24 at 13:48
YosYos
1,1631823
$endgroup$
add a comment |
$begingroup$
Given context-free grammar $G$ whose terminal letters are ${a,b,c,d}$ how can we transition to context-free grammar which contains the words from the language that $G$ creates but which start with $a$ and end with $d$?
I guess we could create new production rules where for example $Ato aX$ from $G$ would also be in $G'$ but how can we determine whether a production rule for middle state come from some rule which starts with $a$ and eventually end with $d$?
context-free-grammar
asked Jan 24 at 13:48
YosYos
1,1631823
$endgroup$
add a comment |
$begingroup$
Given context-free grammar $G$ whose terminal letters are ${a,b,c,d}$ how can we transition to context-free grammar which contains the words from the language that $G$ creates but which start with $a$ and end with $d$?
I guess we could create new production rules where for example $Ato aX$ from $G$ would also be in $G'$ but how can we determine whether a production rule for middle state come from some rule which starts with $a$ and eventually end with $d$?
context-free-grammar
asked Jan 24 at 13:48
YosYos
1,1631823
$endgroup$
Given context-free grammar $G$ whose terminal letters are ${a,b,c,d}$ how can we transition to context-free grammar which contains the words from the language that $G$ creates but which start with $a$ and end with $d$?
I guess we could create new production rules where for example $Ato aX$ from $G$ would also be in $G'$ but how can we determine whether a production rule for middle state come from some rule which starts with $a$ and eventually end with $d$?
context-free-grammar
context-free-grammar
asked Jan 24 at 13:48
YosYos
1,1631823
asked Jan 24 at 13:48
YosYos
1,1631823
asked Jan 24 at 13:48
YosYos
1,1631823
asked Jan 24 at 13:48
YosYos
1,1631823
asked Jan 24 at 13:48
YosYos
1,1631823
1,1631823
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Note that with the constuction from the question "How to define a grammar which creates a language from words of another grammar without one of the letters?" you see how messengers can be sent inside the derivation (or derivation tree) to perform certain actions or to check certain properties of the tree.
In your case there are two such actions: (1) the first symbol should be an $a$ (2) the last symbol should be a $d$. This calls for two markers, or in other words two new copies of each of the nonterminals. The first and last symbols of the derivation $A_f$ and $A_ell$.
If $Ato alpha $ is in the original set of productions $P$ then it is also in the new set $P'$. For the new copy $A_f$ we have cases to consider. If $alpha$ starts with $a$, so $alpha =abeta$ then $A_fto abeta$ is in $P'$. Also, when $alpha$ starts with a nonterminal, so $alpha=Bbeta$, then we get $A_fto B_falpha$ in $P'$.
Similarly for the final letter $d$ and variables $A_ell$.
Finally the construction is complicated by the fact that initially the axiom is marked by both $f$ and $ell$.
Sometimes it is easier to assume that the original grammar is in a kind of normal form. In this case Chomsky normal form seems best. Those grammars have only productions of the type $Ato BC$ or $Ato t$. The simplicity of this format means there are much less cases to consider.
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
$endgroup$
$begingroup$
But when we get a production of type $Ato talpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $Ato talpha$ is the first symbol then $Ato talpha$ is $t=a$?
$endgroup$
– Yos
Jan 26 at 12:05
1
$begingroup$
When I wrote $Ato talpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string.
$endgroup$
– Hendrik Jan
Jan 26 at 22:42
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%2f3085897%2fhow-to-transition-from-context-free-grammar-g-to-to-context-free-grammar-which%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$
Note that with the constuction from the question "How to define a grammar which creates a language from words of another grammar without one of the letters?" you see how messengers can be sent inside the derivation (or derivation tree) to perform certain actions or to check certain properties of the tree.
In your case there are two such actions: (1) the first symbol should be an $a$ (2) the last symbol should be a $d$. This calls for two markers, or in other words two new copies of each of the nonterminals. The first and last symbols of the derivation $A_f$ and $A_ell$.
If $Ato alpha $ is in the original set of productions $P$ then it is also in the new set $P'$. For the new copy $A_f$ we have cases to consider. If $alpha$ starts with $a$, so $alpha =abeta$ then $A_fto abeta$ is in $P'$. Also, when $alpha$ starts with a nonterminal, so $alpha=Bbeta$, then we get $A_fto B_falpha$ in $P'$.
Similarly for the final letter $d$ and variables $A_ell$.
Finally the construction is complicated by the fact that initially the axiom is marked by both $f$ and $ell$.
Sometimes it is easier to assume that the original grammar is in a kind of normal form. In this case Chomsky normal form seems best. Those grammars have only productions of the type $Ato BC$ or $Ato t$. The simplicity of this format means there are much less cases to consider.
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
$endgroup$
$begingroup$
But when we get a production of type $Ato talpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $Ato talpha$ is the first symbol then $Ato talpha$ is $t=a$?
$endgroup$
– Yos
Jan 26 at 12:05
1
$begingroup$
When I wrote $Ato talpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string.
$endgroup$
– Hendrik Jan
Jan 26 at 22:42
add a comment |
$begingroup$
Note that with the constuction from the question "How to define a grammar which creates a language from words of another grammar without one of the letters?" you see how messengers can be sent inside the derivation (or derivation tree) to perform certain actions or to check certain properties of the tree.
In your case there are two such actions: (1) the first symbol should be an $a$ (2) the last symbol should be a $d$. This calls for two markers, or in other words two new copies of each of the nonterminals. The first and last symbols of the derivation $A_f$ and $A_ell$.
If $Ato alpha $ is in the original set of productions $P$ then it is also in the new set $P'$. For the new copy $A_f$ we have cases to consider. If $alpha$ starts with $a$, so $alpha =abeta$ then $A_fto abeta$ is in $P'$. Also, when $alpha$ starts with a nonterminal, so $alpha=Bbeta$, then we get $A_fto B_falpha$ in $P'$.
Similarly for the final letter $d$ and variables $A_ell$.
Finally the construction is complicated by the fact that initially the axiom is marked by both $f$ and $ell$.
Sometimes it is easier to assume that the original grammar is in a kind of normal form. In this case Chomsky normal form seems best. Those grammars have only productions of the type $Ato BC$ or $Ato t$. The simplicity of this format means there are much less cases to consider.
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
$endgroup$
$begingroup$
But when we get a production of type $Ato talpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $Ato talpha$ is the first symbol then $Ato talpha$ is $t=a$?
$endgroup$
– Yos
Jan 26 at 12:05
1
$begingroup$
When I wrote $Ato talpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string.
$endgroup$
– Hendrik Jan
Jan 26 at 22:42
add a comment |
$begingroup$
Note that with the constuction from the question "How to define a grammar which creates a language from words of another grammar without one of the letters?" you see how messengers can be sent inside the derivation (or derivation tree) to perform certain actions or to check certain properties of the tree.
In your case there are two such actions: (1) the first symbol should be an $a$ (2) the last symbol should be a $d$. This calls for two markers, or in other words two new copies of each of the nonterminals. The first and last symbols of the derivation $A_f$ and $A_ell$.
If $Ato alpha $ is in the original set of productions $P$ then it is also in the new set $P'$. For the new copy $A_f$ we have cases to consider. If $alpha$ starts with $a$, so $alpha =abeta$ then $A_fto abeta$ is in $P'$. Also, when $alpha$ starts with a nonterminal, so $alpha=Bbeta$, then we get $A_fto B_falpha$ in $P'$.
Similarly for the final letter $d$ and variables $A_ell$.
Finally the construction is complicated by the fact that initially the axiom is marked by both $f$ and $ell$.
Sometimes it is easier to assume that the original grammar is in a kind of normal form. In this case Chomsky normal form seems best. Those grammars have only productions of the type $Ato BC$ or $Ato t$. The simplicity of this format means there are much less cases to consider.
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
$endgroup$
Note that with the constuction from the question "How to define a grammar which creates a language from words of another grammar without one of the letters?" you see how messengers can be sent inside the derivation (or derivation tree) to perform certain actions or to check certain properties of the tree.
In your case there are two such actions: (1) the first symbol should be an $a$ (2) the last symbol should be a $d$. This calls for two markers, or in other words two new copies of each of the nonterminals. The first and last symbols of the derivation $A_f$ and $A_ell$.
If $Ato alpha $ is in the original set of productions $P$ then it is also in the new set $P'$. For the new copy $A_f$ we have cases to consider. If $alpha$ starts with $a$, so $alpha =abeta$ then $A_fto abeta$ is in $P'$. Also, when $alpha$ starts with a nonterminal, so $alpha=Bbeta$, then we get $A_fto B_falpha$ in $P'$.
Similarly for the final letter $d$ and variables $A_ell$.
Finally the construction is complicated by the fact that initially the axiom is marked by both $f$ and $ell$.
Sometimes it is easier to assume that the original grammar is in a kind of normal form. In this case Chomsky normal form seems best. Those grammars have only productions of the type $Ato BC$ or $Ato t$. The simplicity of this format means there are much less cases to consider.
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
edited Jan 26 at 22:37
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
answered Jan 26 at 11:29
Hendrik JanHendrik Jan
1,733818
1,733818
$begingroup$
But when we get a production of type $Ato talpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $Ato talpha$ is the first symbol then $Ato talpha$ is $t=a$?
$endgroup$
– Yos
Jan 26 at 12:05
1
$begingroup$
When I wrote $Ato talpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string.
$endgroup$
– Hendrik Jan
Jan 26 at 22:42
add a comment |
$begingroup$
But when we get a production of type $Ato talpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $Ato talpha$ is the first symbol then $Ato talpha$ is $t=a$?
$endgroup$
– Yos
Jan 26 at 12:05
1
$begingroup$
When I wrote $Ato talpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string.
$endgroup$
– Hendrik Jan
Jan 26 at 22:42
$begingroup$
But when we get a production of type $Ato talpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $Ato talpha$ is the first symbol then $Ato talpha$ is $t=a$?
$endgroup$
– Yos
Jan 26 at 12:05
$begingroup$
But when we get a production of type $Ato talpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $Ato talpha$ is the first symbol then $Ato talpha$ is $t=a$?
$endgroup$
– Yos
Jan 26 at 12:05
1
1
$begingroup$
When I wrote $Ato talpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string.
$endgroup$
– Hendrik Jan
Jan 26 at 22:42
$begingroup$
When I wrote $Ato talpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string.
$endgroup$
– Hendrik Jan
Jan 26 at 22:42
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%2f3085897%2fhow-to-transition-from-context-free-grammar-g-to-to-context-free-grammar-which%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
