Mixing
CFG for constituent tree of As Bs and as and bs
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
1
I have the following constituent tree, and I am confused on how to find the context-free grammar as I am not used to these notations of As and Bs.
S
/
A A
/ |
A B a
/ |
A B b
| |
a b
I thought of the following CFG:
S -> AA
A -> AB
A -> a
B -> b
Does this make sense?
grammar abstract-syntax-tree context-free-grammar lexical-analysis formal-languages
asked Jan 3 at 10:01
user102859user102859
183119
add a comment |
1
I have the following constituent tree, and I am confused on how to find the context-free grammar as I am not used to these notations of As and Bs.
S
/
A A
/ |
A B a
/ |
A B b
| |
a b
I thought of the following CFG:
S -> AA
A -> AB
A -> a
B -> b
Does this make sense?
grammar abstract-syntax-tree context-free-grammar lexical-analysis formal-languages
asked Jan 3 at 10:01
user102859user102859
183119
1
Your problem in understrained. A language is defined by an arbitrary set of strings. You show only one string here: abab. If that is the language, then S -> abab; and S -> XX; X->ab; are two perfectly valid different CFGs that work. How will you choose? If abab is not the only instance of the langauge, then you don't have enough information to define any mechanism for generating the language, let alone a CFG.
– Ira Baxter
Jan 3 at 11:39
I think what you have done is very reasonable. If this is the only information you are given, you can infer the grammar for which this parse tree was generated has at least the terminals a and b, at least the nonterminals S, A and B, and at least the productions you've shown. Sure, the language may have other grammars that generate it, but they wouldn't have this parse tree if they didn't have at least what you show.
– Patrick87
Jan 8 at 15:47
add a comment |
1
1
1
I have the following constituent tree, and I am confused on how to find the context-free grammar as I am not used to these notations of As and Bs.
S
/
A A
/ |
A B a
/ |
A B b
| |
a b
I thought of the following CFG:
S -> AA
A -> AB
A -> a
B -> b
Does this make sense?
grammar abstract-syntax-tree context-free-grammar lexical-analysis formal-languages
asked Jan 3 at 10:01
user102859user102859
183119
I have the following constituent tree, and I am confused on how to find the context-free grammar as I am not used to these notations of As and Bs.
S
/
A A
/ |
A B a
/ |
A B b
| |
a b
I thought of the following CFG:
S -> AA
A -> AB
A -> a
B -> b
Does this make sense?
grammar abstract-syntax-tree context-free-grammar lexical-analysis formal-languages
grammar abstract-syntax-tree context-free-grammar lexical-analysis formal-languages
asked Jan 3 at 10:01
user102859user102859
183119
asked Jan 3 at 10:01
user102859user102859
183119
edited Jan 3 at 10:24
user102859
asked Jan 3 at 10:01
user102859user102859
183119
asked Jan 3 at 10:01
user102859user102859
183119
asked Jan 3 at 10:01
user102859user102859
183119
183119
1
Your problem in understrained. A language is defined by an arbitrary set of strings. You show only one string here: abab. If that is the language, then S -> abab; and S -> XX; X->ab; are two perfectly valid different CFGs that work. How will you choose? If abab is not the only instance of the langauge, then you don't have enough information to define any mechanism for generating the language, let alone a CFG.
– Ira Baxter
Jan 3 at 11:39
I think what you have done is very reasonable. If this is the only information you are given, you can infer the grammar for which this parse tree was generated has at least the terminals a and b, at least the nonterminals S, A and B, and at least the productions you've shown. Sure, the language may have other grammars that generate it, but they wouldn't have this parse tree if they didn't have at least what you show.
– Patrick87
Jan 8 at 15:47
add a comment |
1
Your problem in understrained. A language is defined by an arbitrary set of strings. You show only one string here: abab. If that is the language, then S -> abab; and S -> XX; X->ab; are two perfectly valid different CFGs that work. How will you choose? If abab is not the only instance of the langauge, then you don't have enough information to define any mechanism for generating the language, let alone a CFG.
– Ira Baxter
Jan 3 at 11:39
I think what you have done is very reasonable. If this is the only information you are given, you can infer the grammar for which this parse tree was generated has at least the terminals a and b, at least the nonterminals S, A and B, and at least the productions you've shown. Sure, the language may have other grammars that generate it, but they wouldn't have this parse tree if they didn't have at least what you show.
– Patrick87
Jan 8 at 15:47
1
1
Your problem in understrained. A language is defined by an arbitrary set of strings. You show only one string here: abab. If that is the language, then S -> abab; and S -> XX; X->ab; are two perfectly valid different CFGs that work. How will you choose? If abab is not the only instance of the langauge, then you don't have enough information to define any mechanism for generating the language, let alone a CFG.
– Ira Baxter
Jan 3 at 11:39
Your problem in understrained. A language is defined by an arbitrary set of strings. You show only one string here: abab. If that is the language, then S -> abab; and S -> XX; X->ab; are two perfectly valid different CFGs that work. How will you choose? If abab is not the only instance of the langauge, then you don't have enough information to define any mechanism for generating the language, let alone a CFG.
– Ira Baxter
Jan 3 at 11:39
I think what you have done is very reasonable. If this is the only information you are given, you can infer the grammar for which this parse tree was generated has at least the terminals a and b, at least the nonterminals S, A and B, and at least the productions you've shown. Sure, the language may have other grammars that generate it, but they wouldn't have this parse tree if they didn't have at least what you show.
– Patrick87
Jan 8 at 15:47
I think what you have done is very reasonable. If this is the only information you are given, you can infer the grammar for which this parse tree was generated has at least the terminals a and b, at least the nonterminals S, A and B, and at least the productions you've shown. Sure, the language may have other grammars that generate it, but they wouldn't have this parse tree if they didn't have at least what you show.
– Patrick87
Jan 8 at 15:47
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
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%2fstackoverflow.com%2fquestions%2f54019999%2fcfg-for-constituent-tree-of-as-bs-and-as-and-bs%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
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- 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.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
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%2fstackoverflow.com%2fquestions%2f54019999%2fcfg-for-constituent-tree-of-as-bs-and-as-and-bs%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
Your problem in understrained. A language is defined by an arbitrary set of strings. You show only one string here: abab. If that is the language, then S -> abab; and S -> XX; X->ab; are two perfectly valid different CFGs that work. How will you choose? If abab is not the only instance of the langauge, then you don't have enough information to define any mechanism for generating the language, let alone a CFG.
– Ira Baxter
Jan 3 at 11:39
I think what you have done is very reasonable. If this is the only information you are given, you can infer the grammar for which this parse tree was generated has at least the terminals a and b, at least the nonterminals S, A and B, and at least the productions you've shown. Sure, the language may have other grammars that generate it, but they wouldn't have this parse tree if they didn't have at least what you show.
– Patrick87
Jan 8 at 15:47