which of the following languages over $Sigma {0,1,$}$ are regular?
$begingroup$
i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation.
(languages over $Sigma {0,1,$}$)
1)$x_i,y_i,z_i in {0,1}$ for every $1leq n$, so that $x_1y_1z_1...x_ny_nz_n|x_n....x_1+y_n...y_1=z_n....z_1$
2){x$y$z | x + y = z} ($x,y,z in {0,1}^+ $)
3)number of combinations of 01 in w = number of combinations 10 in w ($w in {0,1}^*$)
my try:
1)not regular because n not seem to be bounded, and regular languages should have a finite boundary. however, maybe because of the addition i am missing something and it is actually bounded, but i think that it is not regular because the previous explanation.
2)since it is a finite set, we can use the pumping lemma to assert it is a bounded and thus a regular language.
3)not regular because number of combinations can be infinity, and because of the pumping lemma, a regular language should have a finite boundary.
for some reason when i try to use latex, it removes my {}, which are neccesary in logic and automata, and i don't know how to handle it to make it more readable.
tried to do my best and explain what i did and why and hope it's correct. if not, please correct me so i can learn from your answers and my mistakes and improve.
thank you very much!
computer-science automata
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
$endgroup$
|
show 1 more comment
$begingroup$
i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation.
(languages over $Sigma {0,1,$}$)
1)$x_i,y_i,z_i in {0,1}$ for every $1leq n$, so that $x_1y_1z_1...x_ny_nz_n|x_n....x_1+y_n...y_1=z_n....z_1$
2){x$y$z | x + y = z} ($x,y,z in {0,1}^+ $)
3)number of combinations of 01 in w = number of combinations 10 in w ($w in {0,1}^*$)
my try:
1)not regular because n not seem to be bounded, and regular languages should have a finite boundary. however, maybe because of the addition i am missing something and it is actually bounded, but i think that it is not regular because the previous explanation.
2)since it is a finite set, we can use the pumping lemma to assert it is a bounded and thus a regular language.
3)not regular because number of combinations can be infinity, and because of the pumping lemma, a regular language should have a finite boundary.
for some reason when i try to use latex, it removes my {}, which are neccesary in logic and automata, and i don't know how to handle it to make it more readable.
tried to do my best and explain what i did and why and hope it's correct. if not, please correct me so i can learn from your answers and my mistakes and improve.
thank you very much!
computer-science automata
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
$endgroup$
$begingroup$
In latex, you need to do this:{cdot}to get ${cdot}$. The backslash must immediately precede each brace.
$endgroup$
– amWhy
Dec 2 '18 at 20:43
$begingroup$
thank you very much!
$endgroup$
– mathnoobie
Dec 2 '18 at 20:44
$begingroup$
Why not apply the indication you received in the comment above, and correct the title and body of your question?
$endgroup$
– Did
Dec 2 '18 at 21:49
$begingroup$
@did: fixed it, could you help with my question please?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:22
$begingroup$
"fixed it" No, you did not.
$endgroup$
– Did
Dec 2 '18 at 22:39
|
show 1 more comment
$begingroup$
i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation.
(languages over $Sigma {0,1,$}$)
1)$x_i,y_i,z_i in {0,1}$ for every $1leq n$, so that $x_1y_1z_1...x_ny_nz_n|x_n....x_1+y_n...y_1=z_n....z_1$
2){x$y$z | x + y = z} ($x,y,z in {0,1}^+ $)
3)number of combinations of 01 in w = number of combinations 10 in w ($w in {0,1}^*$)
my try:
1)not regular because n not seem to be bounded, and regular languages should have a finite boundary. however, maybe because of the addition i am missing something and it is actually bounded, but i think that it is not regular because the previous explanation.
2)since it is a finite set, we can use the pumping lemma to assert it is a bounded and thus a regular language.
3)not regular because number of combinations can be infinity, and because of the pumping lemma, a regular language should have a finite boundary.
for some reason when i try to use latex, it removes my {}, which are neccesary in logic and automata, and i don't know how to handle it to make it more readable.
tried to do my best and explain what i did and why and hope it's correct. if not, please correct me so i can learn from your answers and my mistakes and improve.
thank you very much!
computer-science automata
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
$endgroup$
i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation.
(languages over $Sigma {0,1,$}$)
1)$x_i,y_i,z_i in {0,1}$ for every $1leq n$, so that $x_1y_1z_1...x_ny_nz_n|x_n....x_1+y_n...y_1=z_n....z_1$
2){x$y$z | x + y = z} ($x,y,z in {0,1}^+ $)
3)number of combinations of 01 in w = number of combinations 10 in w ($w in {0,1}^*$)
my try:
1)not regular because n not seem to be bounded, and regular languages should have a finite boundary. however, maybe because of the addition i am missing something and it is actually bounded, but i think that it is not regular because the previous explanation.
2)since it is a finite set, we can use the pumping lemma to assert it is a bounded and thus a regular language.
3)not regular because number of combinations can be infinity, and because of the pumping lemma, a regular language should have a finite boundary.
for some reason when i try to use latex, it removes my {}, which are neccesary in logic and automata, and i don't know how to handle it to make it more readable.
tried to do my best and explain what i did and why and hope it's correct. if not, please correct me so i can learn from your answers and my mistakes and improve.
thank you very much!
computer-science automata
computer-science automata
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
edited Dec 3 '18 at 9:38
mathnoobie
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
asked Dec 2 '18 at 20:42
mathnoobiemathnoobie
93
93
$begingroup$
In latex, you need to do this:{cdot}to get ${cdot}$. The backslash must immediately precede each brace.
$endgroup$
– amWhy
Dec 2 '18 at 20:43
$begingroup$
thank you very much!
$endgroup$
– mathnoobie
Dec 2 '18 at 20:44
$begingroup$
Why not apply the indication you received in the comment above, and correct the title and body of your question?
$endgroup$
– Did
Dec 2 '18 at 21:49
$begingroup$
@did: fixed it, could you help with my question please?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:22
$begingroup$
"fixed it" No, you did not.
$endgroup$
– Did
Dec 2 '18 at 22:39
|
show 1 more comment
$begingroup$
In latex, you need to do this:{cdot}to get ${cdot}$. The backslash must immediately precede each brace.
$endgroup$
– amWhy
Dec 2 '18 at 20:43
$begingroup$
thank you very much!
$endgroup$
– mathnoobie
Dec 2 '18 at 20:44
$begingroup$
Why not apply the indication you received in the comment above, and correct the title and body of your question?
$endgroup$
– Did
Dec 2 '18 at 21:49
$begingroup$
@did: fixed it, could you help with my question please?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:22
$begingroup$
"fixed it" No, you did not.
$endgroup$
– Did
Dec 2 '18 at 22:39
$begingroup$
In latex, you need to do this:
{cdot} to get ${cdot}$. The backslash must immediately precede each brace.$endgroup$
– amWhy
Dec 2 '18 at 20:43
$begingroup$
In latex, you need to do this:
{cdot} to get ${cdot}$. The backslash must immediately precede each brace.$endgroup$
– amWhy
Dec 2 '18 at 20:43
$begingroup$
thank you very much!
$endgroup$
– mathnoobie
Dec 2 '18 at 20:44
$begingroup$
thank you very much!
$endgroup$
– mathnoobie
Dec 2 '18 at 20:44
$begingroup$
Why not apply the indication you received in the comment above, and correct the title and body of your question?
$endgroup$
– Did
Dec 2 '18 at 21:49
$begingroup$
Why not apply the indication you received in the comment above, and correct the title and body of your question?
$endgroup$
– Did
Dec 2 '18 at 21:49
$begingroup$
@did: fixed it, could you help with my question please?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:22
$begingroup$
@did: fixed it, could you help with my question please?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:22
$begingroup$
"fixed it" No, you did not.
$endgroup$
– Did
Dec 2 '18 at 22:39
$begingroup$
"fixed it" No, you did not.
$endgroup$
– Did
Dec 2 '18 at 22:39
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
A regular language is one that can be represented by a finite state automata, which is a very simple "machine" that doesn't have the ability to store any memory. That should give you a hint as to whether something is regular or not.
For instance, in the second language:
{xyz | x + y = z} (x,y,z∈ {0,1}+)
The value for "z" is dependent upon knowing the values of x and y, but these simple FSAs have no way of remembering that information. Keep in mind that the pumping lemma can be used to prove that this (and other languages) are NOT regular, but it cannot be used to prove that a language IS regular as you're asserting in your second point.
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
$endgroup$
$begingroup$
regarding what you've said, it seems that either 0 +1 = 1 or 1 + 0 = 1, but is that enough to assert it's finite? i really didn't understand your comment. were the other also incorrect?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:25
$begingroup$
A language being finite or infinite doesn't imply it is regular or irregular. Take the language A = { x* | x ∈ { 0,1 } }. The language A is the set of all values that satisfy the given rule. This includes: empty string, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, ... , etc. The possibilities are infinite, and yet the language is regular and can be expressed by an FSA.
$endgroup$
– Dopevoponop
Dec 3 '18 at 0:37
$begingroup$
so if i understood what you said, could you tell me if now it's correct? 1)regular as the number of elements is equal(because of n), so it doesn't require special memory to "remember it". 2)you cannot remember the result and information, so it cannot be a regular language 3) also not a regular language as you can not remember the amount of 01 in w to compare with the amount of 10 in w. is it correct now?
$endgroup$
– mathnoobie
Dec 3 '18 at 8:17
$begingroup$
Honestly, I'm a bit confused about the notation used in the first language, so it's hard to give you an answer on this one. It seems like just an elongated version of language two where there are just multiple groups of these xyz patterns all next to each other. The subscript n doesn't actually mean anything other then just grouping them together, and so it can't be used as a means of storing anything as you seem to imply.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:02
$begingroup$
Your take on language 2 is correct, although that isn't a very exhaustive proof. You could use the pumping lemma to do this by assuming some pumping length P (it's not important what this number actually is), then make some string that satisfies the criteria of the language and is also longer than the pumping length P. This would necessity that some portion of your word can be "pumped" or just repeated however many times (or none at all). In order to prove that a language is not regular, you must show that there exists no substring that can be pumped like this and still be in the language.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:09
|
show 3 more comments
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%2f3023149%2fwhich-of-the-following-languages-over-sigma-0-1-are-regular%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$
A regular language is one that can be represented by a finite state automata, which is a very simple "machine" that doesn't have the ability to store any memory. That should give you a hint as to whether something is regular or not.
For instance, in the second language:
{xyz | x + y = z} (x,y,z∈ {0,1}+)
The value for "z" is dependent upon knowing the values of x and y, but these simple FSAs have no way of remembering that information. Keep in mind that the pumping lemma can be used to prove that this (and other languages) are NOT regular, but it cannot be used to prove that a language IS regular as you're asserting in your second point.
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
$endgroup$
$begingroup$
regarding what you've said, it seems that either 0 +1 = 1 or 1 + 0 = 1, but is that enough to assert it's finite? i really didn't understand your comment. were the other also incorrect?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:25
$begingroup$
A language being finite or infinite doesn't imply it is regular or irregular. Take the language A = { x* | x ∈ { 0,1 } }. The language A is the set of all values that satisfy the given rule. This includes: empty string, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, ... , etc. The possibilities are infinite, and yet the language is regular and can be expressed by an FSA.
$endgroup$
– Dopevoponop
Dec 3 '18 at 0:37
$begingroup$
so if i understood what you said, could you tell me if now it's correct? 1)regular as the number of elements is equal(because of n), so it doesn't require special memory to "remember it". 2)you cannot remember the result and information, so it cannot be a regular language 3) also not a regular language as you can not remember the amount of 01 in w to compare with the amount of 10 in w. is it correct now?
$endgroup$
– mathnoobie
Dec 3 '18 at 8:17
$begingroup$
Honestly, I'm a bit confused about the notation used in the first language, so it's hard to give you an answer on this one. It seems like just an elongated version of language two where there are just multiple groups of these xyz patterns all next to each other. The subscript n doesn't actually mean anything other then just grouping them together, and so it can't be used as a means of storing anything as you seem to imply.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:02
$begingroup$
Your take on language 2 is correct, although that isn't a very exhaustive proof. You could use the pumping lemma to do this by assuming some pumping length P (it's not important what this number actually is), then make some string that satisfies the criteria of the language and is also longer than the pumping length P. This would necessity that some portion of your word can be "pumped" or just repeated however many times (or none at all). In order to prove that a language is not regular, you must show that there exists no substring that can be pumped like this and still be in the language.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:09
|
show 3 more comments
$begingroup$
A regular language is one that can be represented by a finite state automata, which is a very simple "machine" that doesn't have the ability to store any memory. That should give you a hint as to whether something is regular or not.
For instance, in the second language:
{xyz | x + y = z} (x,y,z∈ {0,1}+)
The value for "z" is dependent upon knowing the values of x and y, but these simple FSAs have no way of remembering that information. Keep in mind that the pumping lemma can be used to prove that this (and other languages) are NOT regular, but it cannot be used to prove that a language IS regular as you're asserting in your second point.
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
$endgroup$
$begingroup$
regarding what you've said, it seems that either 0 +1 = 1 or 1 + 0 = 1, but is that enough to assert it's finite? i really didn't understand your comment. were the other also incorrect?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:25
$begingroup$
A language being finite or infinite doesn't imply it is regular or irregular. Take the language A = { x* | x ∈ { 0,1 } }. The language A is the set of all values that satisfy the given rule. This includes: empty string, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, ... , etc. The possibilities are infinite, and yet the language is regular and can be expressed by an FSA.
$endgroup$
– Dopevoponop
Dec 3 '18 at 0:37
$begingroup$
so if i understood what you said, could you tell me if now it's correct? 1)regular as the number of elements is equal(because of n), so it doesn't require special memory to "remember it". 2)you cannot remember the result and information, so it cannot be a regular language 3) also not a regular language as you can not remember the amount of 01 in w to compare with the amount of 10 in w. is it correct now?
$endgroup$
– mathnoobie
Dec 3 '18 at 8:17
$begingroup$
Honestly, I'm a bit confused about the notation used in the first language, so it's hard to give you an answer on this one. It seems like just an elongated version of language two where there are just multiple groups of these xyz patterns all next to each other. The subscript n doesn't actually mean anything other then just grouping them together, and so it can't be used as a means of storing anything as you seem to imply.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:02
$begingroup$
Your take on language 2 is correct, although that isn't a very exhaustive proof. You could use the pumping lemma to do this by assuming some pumping length P (it's not important what this number actually is), then make some string that satisfies the criteria of the language and is also longer than the pumping length P. This would necessity that some portion of your word can be "pumped" or just repeated however many times (or none at all). In order to prove that a language is not regular, you must show that there exists no substring that can be pumped like this and still be in the language.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:09
|
show 3 more comments
$begingroup$
A regular language is one that can be represented by a finite state automata, which is a very simple "machine" that doesn't have the ability to store any memory. That should give you a hint as to whether something is regular or not.
For instance, in the second language:
{xyz | x + y = z} (x,y,z∈ {0,1}+)
The value for "z" is dependent upon knowing the values of x and y, but these simple FSAs have no way of remembering that information. Keep in mind that the pumping lemma can be used to prove that this (and other languages) are NOT regular, but it cannot be used to prove that a language IS regular as you're asserting in your second point.
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
$endgroup$
A regular language is one that can be represented by a finite state automata, which is a very simple "machine" that doesn't have the ability to store any memory. That should give you a hint as to whether something is regular or not.
For instance, in the second language:
{xyz | x + y = z} (x,y,z∈ {0,1}+)
The value for "z" is dependent upon knowing the values of x and y, but these simple FSAs have no way of remembering that information. Keep in mind that the pumping lemma can be used to prove that this (and other languages) are NOT regular, but it cannot be used to prove that a language IS regular as you're asserting in your second point.
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
answered Dec 2 '18 at 21:44
DopevoponopDopevoponop
866
866
$begingroup$
regarding what you've said, it seems that either 0 +1 = 1 or 1 + 0 = 1, but is that enough to assert it's finite? i really didn't understand your comment. were the other also incorrect?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:25
$begingroup$
A language being finite or infinite doesn't imply it is regular or irregular. Take the language A = { x* | x ∈ { 0,1 } }. The language A is the set of all values that satisfy the given rule. This includes: empty string, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, ... , etc. The possibilities are infinite, and yet the language is regular and can be expressed by an FSA.
$endgroup$
– Dopevoponop
Dec 3 '18 at 0:37
$begingroup$
so if i understood what you said, could you tell me if now it's correct? 1)regular as the number of elements is equal(because of n), so it doesn't require special memory to "remember it". 2)you cannot remember the result and information, so it cannot be a regular language 3) also not a regular language as you can not remember the amount of 01 in w to compare with the amount of 10 in w. is it correct now?
$endgroup$
– mathnoobie
Dec 3 '18 at 8:17
$begingroup$
Honestly, I'm a bit confused about the notation used in the first language, so it's hard to give you an answer on this one. It seems like just an elongated version of language two where there are just multiple groups of these xyz patterns all next to each other. The subscript n doesn't actually mean anything other then just grouping them together, and so it can't be used as a means of storing anything as you seem to imply.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:02
$begingroup$
Your take on language 2 is correct, although that isn't a very exhaustive proof. You could use the pumping lemma to do this by assuming some pumping length P (it's not important what this number actually is), then make some string that satisfies the criteria of the language and is also longer than the pumping length P. This would necessity that some portion of your word can be "pumped" or just repeated however many times (or none at all). In order to prove that a language is not regular, you must show that there exists no substring that can be pumped like this and still be in the language.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:09
|
show 3 more comments
$begingroup$
regarding what you've said, it seems that either 0 +1 = 1 or 1 + 0 = 1, but is that enough to assert it's finite? i really didn't understand your comment. were the other also incorrect?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:25
$begingroup$
A language being finite or infinite doesn't imply it is regular or irregular. Take the language A = { x* | x ∈ { 0,1 } }. The language A is the set of all values that satisfy the given rule. This includes: empty string, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, ... , etc. The possibilities are infinite, and yet the language is regular and can be expressed by an FSA.
$endgroup$
– Dopevoponop
Dec 3 '18 at 0:37
$begingroup$
so if i understood what you said, could you tell me if now it's correct? 1)regular as the number of elements is equal(because of n), so it doesn't require special memory to "remember it". 2)you cannot remember the result and information, so it cannot be a regular language 3) also not a regular language as you can not remember the amount of 01 in w to compare with the amount of 10 in w. is it correct now?
$endgroup$
– mathnoobie
Dec 3 '18 at 8:17
$begingroup$
Honestly, I'm a bit confused about the notation used in the first language, so it's hard to give you an answer on this one. It seems like just an elongated version of language two where there are just multiple groups of these xyz patterns all next to each other. The subscript n doesn't actually mean anything other then just grouping them together, and so it can't be used as a means of storing anything as you seem to imply.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:02
$begingroup$
Your take on language 2 is correct, although that isn't a very exhaustive proof. You could use the pumping lemma to do this by assuming some pumping length P (it's not important what this number actually is), then make some string that satisfies the criteria of the language and is also longer than the pumping length P. This would necessity that some portion of your word can be "pumped" or just repeated however many times (or none at all). In order to prove that a language is not regular, you must show that there exists no substring that can be pumped like this and still be in the language.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:09
$begingroup$
regarding what you've said, it seems that either 0 +1 = 1 or 1 + 0 = 1, but is that enough to assert it's finite? i really didn't understand your comment. were the other also incorrect?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:25
$begingroup$
regarding what you've said, it seems that either 0 +1 = 1 or 1 + 0 = 1, but is that enough to assert it's finite? i really didn't understand your comment. were the other also incorrect?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:25
$begingroup$
A language being finite or infinite doesn't imply it is regular or irregular. Take the language A = { x* | x ∈ { 0,1 } }. The language A is the set of all values that satisfy the given rule. This includes: empty string, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, ... , etc. The possibilities are infinite, and yet the language is regular and can be expressed by an FSA.
$endgroup$
– Dopevoponop
Dec 3 '18 at 0:37
$begingroup$
A language being finite or infinite doesn't imply it is regular or irregular. Take the language A = { x* | x ∈ { 0,1 } }. The language A is the set of all values that satisfy the given rule. This includes: empty string, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, ... , etc. The possibilities are infinite, and yet the language is regular and can be expressed by an FSA.
$endgroup$
– Dopevoponop
Dec 3 '18 at 0:37
$begingroup$
so if i understood what you said, could you tell me if now it's correct? 1)regular as the number of elements is equal(because of n), so it doesn't require special memory to "remember it". 2)you cannot remember the result and information, so it cannot be a regular language 3) also not a regular language as you can not remember the amount of 01 in w to compare with the amount of 10 in w. is it correct now?
$endgroup$
– mathnoobie
Dec 3 '18 at 8:17
$begingroup$
so if i understood what you said, could you tell me if now it's correct? 1)regular as the number of elements is equal(because of n), so it doesn't require special memory to "remember it". 2)you cannot remember the result and information, so it cannot be a regular language 3) also not a regular language as you can not remember the amount of 01 in w to compare with the amount of 10 in w. is it correct now?
$endgroup$
– mathnoobie
Dec 3 '18 at 8:17
$begingroup$
Honestly, I'm a bit confused about the notation used in the first language, so it's hard to give you an answer on this one. It seems like just an elongated version of language two where there are just multiple groups of these xyz patterns all next to each other. The subscript n doesn't actually mean anything other then just grouping them together, and so it can't be used as a means of storing anything as you seem to imply.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:02
$begingroup$
Honestly, I'm a bit confused about the notation used in the first language, so it's hard to give you an answer on this one. It seems like just an elongated version of language two where there are just multiple groups of these xyz patterns all next to each other. The subscript n doesn't actually mean anything other then just grouping them together, and so it can't be used as a means of storing anything as you seem to imply.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:02
$begingroup$
Your take on language 2 is correct, although that isn't a very exhaustive proof. You could use the pumping lemma to do this by assuming some pumping length P (it's not important what this number actually is), then make some string that satisfies the criteria of the language and is also longer than the pumping length P. This would necessity that some portion of your word can be "pumped" or just repeated however many times (or none at all). In order to prove that a language is not regular, you must show that there exists no substring that can be pumped like this and still be in the language.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:09
$begingroup$
Your take on language 2 is correct, although that isn't a very exhaustive proof. You could use the pumping lemma to do this by assuming some pumping length P (it's not important what this number actually is), then make some string that satisfies the criteria of the language and is also longer than the pumping length P. This would necessity that some portion of your word can be "pumped" or just repeated however many times (or none at all). In order to prove that a language is not regular, you must show that there exists no substring that can be pumped like this and still be in the language.
$endgroup$
– Dopevoponop
Dec 3 '18 at 9:09
|
show 3 more comments
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%2f3023149%2fwhich-of-the-following-languages-over-sigma-0-1-are-regular%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$
In latex, you need to do this:
{cdot}to get ${cdot}$. The backslash must immediately precede each brace.$endgroup$
– amWhy
Dec 2 '18 at 20:43
$begingroup$
thank you very much!
$endgroup$
– mathnoobie
Dec 2 '18 at 20:44
$begingroup$
Why not apply the indication you received in the comment above, and correct the title and body of your question?
$endgroup$
– Did
Dec 2 '18 at 21:49
$begingroup$
@did: fixed it, could you help with my question please?
$endgroup$
– mathnoobie
Dec 2 '18 at 22:22
$begingroup$
"fixed it" No, you did not.
$endgroup$
– Did
Dec 2 '18 at 22:39