Mixing
Formal Languages - Context Free Grammar
$begingroup$
Describe the formal language over the alphabet
{
a,b,c
}
generated
by the context-free grammar whose non-terminals are
〈
S
〉
and
〈
A
〉
,
whose start symbol is
〈
S
〉
,
and whose production rules are the
following:
(1)
〈
S
〉→
a
〈
S
〉
(2)
〈
S
〉→
b
〈
A
〉
(3)
〈
A
〉→
b
〈
A
〉
(4)
〈
A
〉→
c
〈
A
〉
(5)
〈
A
〉→
c
(6)
〈
S
〉→
a
In other words, describe the structure of the strings generated by
this grammar and modify to NORMAL FORM(The normal form pasrt I am struggling with)
formal-languages context-free-grammar
asked Jan 22 at 17:44
SueSue
126
$endgroup$
|
show 3 more comments
$begingroup$
Describe the formal language over the alphabet
{
a,b,c
}
generated
by the context-free grammar whose non-terminals are
〈
S
〉
and
〈
A
〉
,
whose start symbol is
〈
S
〉
,
and whose production rules are the
following:
(1)
〈
S
〉→
a
〈
S
〉
(2)
〈
S
〉→
b
〈
A
〉
(3)
〈
A
〉→
b
〈
A
〉
(4)
〈
A
〉→
c
〈
A
〉
(5)
〈
A
〉→
c
(6)
〈
S
〉→
a
In other words, describe the structure of the strings generated by
this grammar and modify to NORMAL FORM(The normal form pasrt I am struggling with)
formal-languages context-free-grammar
asked Jan 22 at 17:44
SueSue
126
$endgroup$
$begingroup$
Im confused about how I should write my answer and how to format production rules
$endgroup$
– Sue
Jan 22 at 17:45
$begingroup$
I've made some progress, I currently have: { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } , not sure how to format it to mean that b cannot come at the end of a word... how could i do this?
$endgroup$
– Sue
Jan 22 at 18:16
$begingroup$
It seems this grammar is even regular, since all rules are of the form non-terminal produces terminal or non-terminal produces terminal followed by non-terminal (this is one of the standard forms of a regular grammar). Given this, try to express the language as a regular expression.
$endgroup$
– MHS
Jan 22 at 22:20
$begingroup$
Also your description { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } is not (yet) completely correct. There is a difference between words starting with a letter a and those starting with a letter b and what about the order of letters b and c?
$endgroup$
– MHS
Jan 22 at 22:22
$begingroup$
I tried express the language as a regular expression, is this correct?
$endgroup$
– Sue
Jan 23 at 9:52
|
show 3 more comments
$begingroup$
Describe the formal language over the alphabet
{
a,b,c
}
generated
by the context-free grammar whose non-terminals are
〈
S
〉
and
〈
A
〉
,
whose start symbol is
〈
S
〉
,
and whose production rules are the
following:
(1)
〈
S
〉→
a
〈
S
〉
(2)
〈
S
〉→
b
〈
A
〉
(3)
〈
A
〉→
b
〈
A
〉
(4)
〈
A
〉→
c
〈
A
〉
(5)
〈
A
〉→
c
(6)
〈
S
〉→
a
In other words, describe the structure of the strings generated by
this grammar and modify to NORMAL FORM(The normal form pasrt I am struggling with)
formal-languages context-free-grammar
asked Jan 22 at 17:44
SueSue
126
$endgroup$
Describe the formal language over the alphabet
{
a,b,c
}
generated
by the context-free grammar whose non-terminals are
〈
S
〉
and
〈
A
〉
,
whose start symbol is
〈
S
〉
,
and whose production rules are the
following:
(1)
〈
S
〉→
a
〈
S
〉
(2)
〈
S
〉→
b
〈
A
〉
(3)
〈
A
〉→
b
〈
A
〉
(4)
〈
A
〉→
c
〈
A
〉
(5)
〈
A
〉→
c
(6)
〈
S
〉→
a
In other words, describe the structure of the strings generated by
this grammar and modify to NORMAL FORM(The normal form pasrt I am struggling with)
formal-languages context-free-grammar
formal-languages context-free-grammar
asked Jan 22 at 17:44
SueSue
126
asked Jan 22 at 17:44
SueSue
126
edited Jan 23 at 10:56
Sue
asked Jan 22 at 17:44
SueSue
126
asked Jan 22 at 17:44
SueSue
126
asked Jan 22 at 17:44
SueSue
126
126
$begingroup$
Im confused about how I should write my answer and how to format production rules
$endgroup$
– Sue
Jan 22 at 17:45
$begingroup$
I've made some progress, I currently have: { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } , not sure how to format it to mean that b cannot come at the end of a word... how could i do this?
$endgroup$
– Sue
Jan 22 at 18:16
$begingroup$
It seems this grammar is even regular, since all rules are of the form non-terminal produces terminal or non-terminal produces terminal followed by non-terminal (this is one of the standard forms of a regular grammar). Given this, try to express the language as a regular expression.
$endgroup$
– MHS
Jan 22 at 22:20
$begingroup$
Also your description { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } is not (yet) completely correct. There is a difference between words starting with a letter a and those starting with a letter b and what about the order of letters b and c?
$endgroup$
– MHS
Jan 22 at 22:22
$begingroup$
I tried express the language as a regular expression, is this correct?
$endgroup$
– Sue
Jan 23 at 9:52
|
show 3 more comments
$begingroup$
Im confused about how I should write my answer and how to format production rules
$endgroup$
– Sue
Jan 22 at 17:45
$begingroup$
I've made some progress, I currently have: { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } , not sure how to format it to mean that b cannot come at the end of a word... how could i do this?
$endgroup$
– Sue
Jan 22 at 18:16
$begingroup$
It seems this grammar is even regular, since all rules are of the form non-terminal produces terminal or non-terminal produces terminal followed by non-terminal (this is one of the standard forms of a regular grammar). Given this, try to express the language as a regular expression.
$endgroup$
– MHS
Jan 22 at 22:20
$begingroup$
Also your description { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } is not (yet) completely correct. There is a difference between words starting with a letter a and those starting with a letter b and what about the order of letters b and c?
$endgroup$
– MHS
Jan 22 at 22:22
$begingroup$
I tried express the language as a regular expression, is this correct?
$endgroup$
– Sue
Jan 23 at 9:52
$begingroup$
Im confused about how I should write my answer and how to format production rules
$endgroup$
– Sue
Jan 22 at 17:45
$begingroup$
Im confused about how I should write my answer and how to format production rules
$endgroup$
– Sue
Jan 22 at 17:45
$begingroup$
I've made some progress, I currently have: { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } , not sure how to format it to mean that b cannot come at the end of a word... how could i do this?
$endgroup$
– Sue
Jan 22 at 18:16
$begingroup$
I've made some progress, I currently have: { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } , not sure how to format it to mean that b cannot come at the end of a word... how could i do this?
$endgroup$
– Sue
Jan 22 at 18:16
$begingroup$
It seems this grammar is even regular, since all rules are of the form non-terminal produces terminal or non-terminal produces terminal followed by non-terminal (this is one of the standard forms of a regular grammar). Given this, try to express the language as a regular expression.
$endgroup$
– MHS
Jan 22 at 22:20
$begingroup$
It seems this grammar is even regular, since all rules are of the form non-terminal produces terminal or non-terminal produces terminal followed by non-terminal (this is one of the standard forms of a regular grammar). Given this, try to express the language as a regular expression.
$endgroup$
– MHS
Jan 22 at 22:20
$begingroup$
Also your description { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } is not (yet) completely correct. There is a difference between words starting with a letter a and those starting with a letter b and what about the order of letters b and c?
$endgroup$
– MHS
Jan 22 at 22:22
$begingroup$
Also your description { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } is not (yet) completely correct. There is a difference between words starting with a letter a and those starting with a letter b and what about the order of letters b and c?
$endgroup$
– MHS
Jan 22 at 22:22
$begingroup$
I tried express the language as a regular expression, is this correct?
$endgroup$
– Sue
Jan 23 at 9:52
$begingroup$
I tried express the language as a regular expression, is this correct?
$endgroup$
– Sue
Jan 23 at 9:52
|
show 3 more comments
1 Answer
1
active
oldest
votes
$begingroup$
The language is indeed regular and can be described by the regular expression
$$ a^+ cup (a^*cdot{b,c}^*cdot c) $$
Concerning the normal form, you need to specify which normal form you are talking about. For right-regular grammars the most common one requires exactly one terminal on the right-hand side of each rule. This holds for your grammar.
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
$endgroup$
$begingroup$
I'm curious what the little cross means beside the a
$endgroup$
– Sue
Jan 23 at 12:19
$begingroup$
It is a plus. A short form for non-empty iteration: $a^+ = acdot a^*$.
$endgroup$
– Peter Leupold
Jan 23 at 12:31
1
$begingroup$
Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression.
$endgroup$
– MHS
Jan 24 at 13:56
$begingroup$
Thanks @MHS! I think I have corrected the expression.
$endgroup$
– Peter Leupold
Jan 26 at 17:26
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%2f3083452%2fformal-languages-context-free-grammar%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$
The language is indeed regular and can be described by the regular expression
$$ a^+ cup (a^*cdot{b,c}^*cdot c) $$
Concerning the normal form, you need to specify which normal form you are talking about. For right-regular grammars the most common one requires exactly one terminal on the right-hand side of each rule. This holds for your grammar.
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
$endgroup$
$begingroup$
I'm curious what the little cross means beside the a
$endgroup$
– Sue
Jan 23 at 12:19
$begingroup$
It is a plus. A short form for non-empty iteration: $a^+ = acdot a^*$.
$endgroup$
– Peter Leupold
Jan 23 at 12:31
1
$begingroup$
Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression.
$endgroup$
– MHS
Jan 24 at 13:56
$begingroup$
Thanks @MHS! I think I have corrected the expression.
$endgroup$
– Peter Leupold
Jan 26 at 17:26
add a comment |
$begingroup$
The language is indeed regular and can be described by the regular expression
$$ a^+ cup (a^*cdot{b,c}^*cdot c) $$
Concerning the normal form, you need to specify which normal form you are talking about. For right-regular grammars the most common one requires exactly one terminal on the right-hand side of each rule. This holds for your grammar.
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
$endgroup$
$begingroup$
I'm curious what the little cross means beside the a
$endgroup$
– Sue
Jan 23 at 12:19
$begingroup$
It is a plus. A short form for non-empty iteration: $a^+ = acdot a^*$.
$endgroup$
– Peter Leupold
Jan 23 at 12:31
1
$begingroup$
Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression.
$endgroup$
– MHS
Jan 24 at 13:56
$begingroup$
Thanks @MHS! I think I have corrected the expression.
$endgroup$
– Peter Leupold
Jan 26 at 17:26
add a comment |
$begingroup$
The language is indeed regular and can be described by the regular expression
$$ a^+ cup (a^*cdot{b,c}^*cdot c) $$
Concerning the normal form, you need to specify which normal form you are talking about. For right-regular grammars the most common one requires exactly one terminal on the right-hand side of each rule. This holds for your grammar.
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
$endgroup$
The language is indeed regular and can be described by the regular expression
$$ a^+ cup (a^*cdot{b,c}^*cdot c) $$
Concerning the normal form, you need to specify which normal form you are talking about. For right-regular grammars the most common one requires exactly one terminal on the right-hand side of each rule. This holds for your grammar.
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
edited Jan 26 at 17:23
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
answered Jan 23 at 12:08
Peter LeupoldPeter Leupold
62526
62526
$begingroup$
I'm curious what the little cross means beside the a
$endgroup$
– Sue
Jan 23 at 12:19
$begingroup$
It is a plus. A short form for non-empty iteration: $a^+ = acdot a^*$.
$endgroup$
– Peter Leupold
Jan 23 at 12:31
1
$begingroup$
Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression.
$endgroup$
– MHS
Jan 24 at 13:56
$begingroup$
Thanks @MHS! I think I have corrected the expression.
$endgroup$
– Peter Leupold
Jan 26 at 17:26
add a comment |
$begingroup$
I'm curious what the little cross means beside the a
$endgroup$
– Sue
Jan 23 at 12:19
$begingroup$
It is a plus. A short form for non-empty iteration: $a^+ = acdot a^*$.
$endgroup$
– Peter Leupold
Jan 23 at 12:31
1
$begingroup$
Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression.
$endgroup$
– MHS
Jan 24 at 13:56
$begingroup$
Thanks @MHS! I think I have corrected the expression.
$endgroup$
– Peter Leupold
Jan 26 at 17:26
$begingroup$
I'm curious what the little cross means beside the a
$endgroup$
– Sue
Jan 23 at 12:19
$begingroup$
I'm curious what the little cross means beside the a
$endgroup$
– Sue
Jan 23 at 12:19
$begingroup$
It is a plus. A short form for non-empty iteration: $a^+ = acdot a^*$.
$endgroup$
– Peter Leupold
Jan 23 at 12:31
$begingroup$
It is a plus. A short form for non-empty iteration: $a^+ = acdot a^*$.
$endgroup$
– Peter Leupold
Jan 23 at 12:31
1
1
$begingroup$
Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression.
$endgroup$
– MHS
Jan 24 at 13:56
$begingroup$
Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression.
$endgroup$
– MHS
Jan 24 at 13:56
$begingroup$
Thanks @MHS! I think I have corrected the expression.
$endgroup$
– Peter Leupold
Jan 26 at 17:26
$begingroup$
Thanks @MHS! I think I have corrected the expression.
$endgroup$
– Peter Leupold
Jan 26 at 17:26
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%2f3083452%2fformal-languages-context-free-grammar%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
$begingroup$
Im confused about how I should write my answer and how to format production rules
$endgroup$
– Sue
Jan 22 at 17:45
$begingroup$
I've made some progress, I currently have: { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } , not sure how to format it to mean that b cannot come at the end of a word... how could i do this?
$endgroup$
– Sue
Jan 22 at 18:16
$begingroup$
It seems this grammar is even regular, since all rules are of the form non-terminal produces terminal or non-terminal produces terminal followed by non-terminal (this is one of the standard forms of a regular grammar). Given this, try to express the language as a regular expression.
$endgroup$
– MHS
Jan 22 at 22:20
$begingroup$
Also your description { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } is not (yet) completely correct. There is a difference between words starting with a letter a and those starting with a letter b and what about the order of letters b and c?
$endgroup$
– MHS
Jan 22 at 22:22
$begingroup$
I tried express the language as a regular expression, is this correct?
$endgroup$
– Sue
Jan 23 at 9:52