What is the complement of a language?
If given any language L, how do I find the complement of said language?
I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-recognizable if the complement of that language, $overline{L}$, is recognizable.
But given a specific language, I have a hard time figuring out what the actual complement is, and can thus not figure out if that complement is recognizable. An example problem is:
Is the following language co-recognizable?
$L$ = {$<M>$ | $M$ is a
turing machine, and $1010 notin{L(M)}$}
computability
asked 21 hours ago
JakirJakir
261
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
If given any language L, how do I find the complement of said language?
I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-recognizable if the complement of that language, $overline{L}$, is recognizable.
But given a specific language, I have a hard time figuring out what the actual complement is, and can thus not figure out if that complement is recognizable. An example problem is:
Is the following language co-recognizable?
$L$ = {$<M>$ | $M$ is a
turing machine, and $1010 notin{L(M)}$}
computability
asked 21 hours ago
JakirJakir
261
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
If given any language L, how do I find the complement of said language?
I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-recognizable if the complement of that language, $overline{L}$, is recognizable.
But given a specific language, I have a hard time figuring out what the actual complement is, and can thus not figure out if that complement is recognizable. An example problem is:
Is the following language co-recognizable?
$L$ = {$<M>$ | $M$ is a
turing machine, and $1010 notin{L(M)}$}
computability
asked 21 hours ago
JakirJakir
261
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
If given any language L, how do I find the complement of said language?
I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-recognizable if the complement of that language, $overline{L}$, is recognizable.
But given a specific language, I have a hard time figuring out what the actual complement is, and can thus not figure out if that complement is recognizable. An example problem is:
Is the following language co-recognizable?
$L$ = {$<M>$ | $M$ is a
turing machine, and $1010 notin{L(M)}$}
computability
computability
asked 21 hours ago
JakirJakir
261
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 21 hours ago
JakirJakir
261
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 21 hours ago
JakirJakir
261
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 21 hours ago
JakirJakir
261
asked 21 hours ago
JakirJakir
261
261
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Jakir is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything not in the set.
In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume ${0,1}$.
So in this case, the complement of that language is:
The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.
Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.
answered 21 hours ago
DraconisDraconis
3,730615
Finding the complement is particularly easy (read: mechanizable) if the the language is given as a predicate subset: Rewrite $L = {<M>|M text{is a TM and} 1010 notin L(M)}$ as $L = {w in {0,1}^* | w = <M>, M text{is a TM and} 1010 notin L(M)} = {w in {0,1}^* | P(w)}$ with $P$ being the predicate in $w$. Now the complement simply is ${w in {0,1}^* | neg P(w)}$. And $neg P(w) equiv w neq <M> lor (w = <M> wedge M text{ TM} wedge 1010 in L(M))$.
– ComFreek
7 hours ago
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: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
});
}
});
Jakir is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcs.stackexchange.com%2fquestions%2f102810%2fwhat-is-the-complement-of-a-language%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
Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything not in the set.
In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume ${0,1}$.
So in this case, the complement of that language is:
The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.
Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.
answered 21 hours ago
DraconisDraconis
3,730615
Finding the complement is particularly easy (read: mechanizable) if the the language is given as a predicate subset: Rewrite $L = {<M>|M text{is a TM and} 1010 notin L(M)}$ as $L = {w in {0,1}^* | w = <M>, M text{is a TM and} 1010 notin L(M)} = {w in {0,1}^* | P(w)}$ with $P$ being the predicate in $w$. Now the complement simply is ${w in {0,1}^* | neg P(w)}$. And $neg P(w) equiv w neq <M> lor (w = <M> wedge M text{ TM} wedge 1010 in L(M))$.
– ComFreek
7 hours ago
add a comment |
Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything not in the set.
In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume ${0,1}$.
So in this case, the complement of that language is:
The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.
Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.
answered 21 hours ago
DraconisDraconis
3,730615
Finding the complement is particularly easy (read: mechanizable) if the the language is given as a predicate subset: Rewrite $L = {<M>|M text{is a TM and} 1010 notin L(M)}$ as $L = {w in {0,1}^* | w = <M>, M text{is a TM and} 1010 notin L(M)} = {w in {0,1}^* | P(w)}$ with $P$ being the predicate in $w$. Now the complement simply is ${w in {0,1}^* | neg P(w)}$. And $neg P(w) equiv w neq <M> lor (w = <M> wedge M text{ TM} wedge 1010 in L(M))$.
– ComFreek
7 hours ago
add a comment |
Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything not in the set.
In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume ${0,1}$.
So in this case, the complement of that language is:
The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.
Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.
answered 21 hours ago
DraconisDraconis
3,730615
Remember that a language is defined as a set of strings. The complement of a language is thus the complement of that set, defined in the usual way: everything not in the set.
In practice, when talking about the complement of a language, there's usually a particular alphabet you're interested in (which you can infer from context). If all else fails, assume ${0,1}$.
So in this case, the complement of that language is:
The set of all binary strings $s$, such that either $s$ isn't a valid encoded Turing machine, or the machine encoded by $s$ accepts $1010$.
Hint: the problem of whether a string $s$ is a valid encoded Turing machine or not is known to be decidable. So you only need to worry about the second clause.
answered 21 hours ago
DraconisDraconis
3,730615
answered 21 hours ago
DraconisDraconis
3,730615
answered 21 hours ago
DraconisDraconis
3,730615
answered 21 hours ago
DraconisDraconis
3,730615
3,730615
Finding the complement is particularly easy (read: mechanizable) if the the language is given as a predicate subset: Rewrite $L = {<M>|M text{is a TM and} 1010 notin L(M)}$ as $L = {w in {0,1}^* | w = <M>, M text{is a TM and} 1010 notin L(M)} = {w in {0,1}^* | P(w)}$ with $P$ being the predicate in $w$. Now the complement simply is ${w in {0,1}^* | neg P(w)}$. And $neg P(w) equiv w neq <M> lor (w = <M> wedge M text{ TM} wedge 1010 in L(M))$.
– ComFreek
7 hours ago
add a comment |
Finding the complement is particularly easy (read: mechanizable) if the the language is given as a predicate subset: Rewrite $L = {<M>|M text{is a TM and} 1010 notin L(M)}$ as $L = {w in {0,1}^* | w = <M>, M text{is a TM and} 1010 notin L(M)} = {w in {0,1}^* | P(w)}$ with $P$ being the predicate in $w$. Now the complement simply is ${w in {0,1}^* | neg P(w)}$. And $neg P(w) equiv w neq <M> lor (w = <M> wedge M text{ TM} wedge 1010 in L(M))$.
– ComFreek
7 hours ago
Finding the complement is particularly easy (read: mechanizable) if the the language is given as a predicate subset: Rewrite $L = {<M>|M text{is a TM and} 1010 notin L(M)}$ as $L = {w in {0,1}^* | w = <M>, M text{is a TM and} 1010 notin L(M)} = {w in {0,1}^* | P(w)}$ with $P$ being the predicate in $w$. Now the complement simply is ${w in {0,1}^* | neg P(w)}$. And $neg P(w) equiv w neq <M> lor (w = <M> wedge M text{ TM} wedge 1010 in L(M))$.
– ComFreek
7 hours ago
Finding the complement is particularly easy (read: mechanizable) if the the language is given as a predicate subset: Rewrite $L = {<M>|M text{is a TM and} 1010 notin L(M)}$ as $L = {w in {0,1}^* | w = <M>, M text{is a TM and} 1010 notin L(M)} = {w in {0,1}^* | P(w)}$ with $P$ being the predicate in $w$. Now the complement simply is ${w in {0,1}^* | neg P(w)}$. And $neg P(w) equiv w neq <M> lor (w = <M> wedge M text{ TM} wedge 1010 in L(M))$.
– ComFreek
7 hours ago
add a comment |
Jakir is a new contributor. Be nice, and check out our Code of Conduct.
Jakir is a new contributor. Be nice, and check out our Code of Conduct.
Jakir is a new contributor. Be nice, and check out our Code of Conduct.
Jakir is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f102810%2fwhat-is-the-complement-of-a-language%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