What is the complement of a language?
$begingroup$
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 Jan 13 at 17:21
JakirJakir
261
$endgroup$
add a comment |
$begingroup$
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 Jan 13 at 17:21
JakirJakir
261
$endgroup$
add a comment |
$begingroup$
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 Jan 13 at 17:21
JakirJakir
261
$endgroup$
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 Jan 13 at 17:21
JakirJakir
261
asked Jan 13 at 17:21
JakirJakir
261
asked Jan 13 at 17:21
JakirJakir
261
asked Jan 13 at 17:21
JakirJakir
261
asked Jan 13 at 17:21
JakirJakir
261
261
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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 Jan 13 at 17:54
DraconisDraconis
4,175617
$endgroup$
$begingroup$
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))$.
$endgroup$
– ComFreek
Jan 14 at 7:59
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
});
}
});
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
$begingroup$
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 Jan 13 at 17:54
DraconisDraconis
4,175617
$endgroup$
$begingroup$
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))$.
$endgroup$
– ComFreek
Jan 14 at 7:59
add a comment |
$begingroup$
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 Jan 13 at 17:54
DraconisDraconis
4,175617
$endgroup$
$begingroup$
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))$.
$endgroup$
– ComFreek
Jan 14 at 7:59
add a comment |
$begingroup$
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 Jan 13 at 17:54
DraconisDraconis
4,175617
$endgroup$
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 Jan 13 at 17:54
DraconisDraconis
4,175617
answered Jan 13 at 17:54
DraconisDraconis
4,175617
answered Jan 13 at 17:54
DraconisDraconis
4,175617
answered Jan 13 at 17:54
DraconisDraconis
4,175617
4,175617
$begingroup$
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))$.
$endgroup$
– ComFreek
Jan 14 at 7:59
add a comment |
$begingroup$
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))$.
$endgroup$
– ComFreek
Jan 14 at 7:59
$begingroup$
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))$.
$endgroup$
– ComFreek
Jan 14 at 7:59
$begingroup$
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))$.
$endgroup$
– ComFreek
Jan 14 at 7:59
add a comment |
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
