Can a DFA be designed to accept any language?
The answer given by our instructor to this question is FALSE.
However, I think it has to be true. Take this DFA that accepts sigma star.
- Q -> {s_1}
- q_0 -> s_1
- sigma -> {a, b}
- F -> {s_1}
- delta -> {s_1[sigma] -> s_1}
That means this language necessarily accepts (sigma star) star, This is the set of all languages, including non-regular ones like {a^nb^n | n > 1}. It seems to me then that non-regular languages would be accepted as they are a subset of the language this DFA describes.
It seems to me like this DFA would accept any language.
dfa
asked Jan 19 at 3:10
AntithesisAntithesis
1017
add a comment |
The answer given by our instructor to this question is FALSE.
However, I think it has to be true. Take this DFA that accepts sigma star.
- Q -> {s_1}
- q_0 -> s_1
- sigma -> {a, b}
- F -> {s_1}
- delta -> {s_1[sigma] -> s_1}
That means this language necessarily accepts (sigma star) star, This is the set of all languages, including non-regular ones like {a^nb^n | n > 1}. It seems to me then that non-regular languages would be accepted as they are a subset of the language this DFA describes.
It seems to me like this DFA would accept any language.
dfa
asked Jan 19 at 3:10
AntithesisAntithesis
1017
add a comment |
The answer given by our instructor to this question is FALSE.
However, I think it has to be true. Take this DFA that accepts sigma star.
- Q -> {s_1}
- q_0 -> s_1
- sigma -> {a, b}
- F -> {s_1}
- delta -> {s_1[sigma] -> s_1}
That means this language necessarily accepts (sigma star) star, This is the set of all languages, including non-regular ones like {a^nb^n | n > 1}. It seems to me then that non-regular languages would be accepted as they are a subset of the language this DFA describes.
It seems to me like this DFA would accept any language.
dfa
asked Jan 19 at 3:10
AntithesisAntithesis
1017
The answer given by our instructor to this question is FALSE.
However, I think it has to be true. Take this DFA that accepts sigma star.
- Q -> {s_1}
- q_0 -> s_1
- sigma -> {a, b}
- F -> {s_1}
- delta -> {s_1[sigma] -> s_1}
That means this language necessarily accepts (sigma star) star, This is the set of all languages, including non-regular ones like {a^nb^n | n > 1}. It seems to me then that non-regular languages would be accepted as they are a subset of the language this DFA describes.
It seems to me like this DFA would accept any language.
dfa
dfa
asked Jan 19 at 3:10
AntithesisAntithesis
1017
asked Jan 19 at 3:10
AntithesisAntithesis
1017
edited Jan 19 at 3:23
Antithesis
asked Jan 19 at 3:10
AntithesisAntithesis
1017
asked Jan 19 at 3:10
AntithesisAntithesis
1017
asked Jan 19 at 3:10
AntithesisAntithesis
1017
1017
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
Recognizing a language implies rejecting strings that don't belong in that language, not just accepting strings that do belong. The fact that you can build an automaton that accepts every string doesn't mean you can build an automaton that accepts the specific strings you need to accept and rejects everything else.
This remains true with your edit; the language accepted by an automaton is the set of all words the automaton accepts. Arbitrary subsets of that set do not count as languages accepted by that automaton. ("The language accepted by an automaton" and "the language recognized by an automaton" are synonymous.)
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
I accidentally mixed up the words recognizing and accepting. I was deliberating on this problem for awhile and started getting my thoughts mixed up. The question asks if a DFA can "accept" any language.
– Antithesis
Jan 19 at 3:23
@Antithesis: Answer expanded. It sounds like you have your definitions mixed up.
– user2357112
Jan 19 at 3:27
That makes sense, I took Formal Language Theory a few years ago, but now taking a compilers course in graduate school. Some of the math has been mixed up. Out of curiosity, how is ambiguity dealt with? i.e., how do you know some DFA computes sigma star vs some other language?
– Antithesis
Jan 19 at 3:36
@Antithesis: What ambiguity? A DFA is deterministic.
– user2357112
Jan 19 at 3:54
The ambiguity of what language a DFA is computing. If you have some DFA as a computing system, it seems like it would be really hard to determine if the accepted language is sigma star. Of course it fairly obvious if you have the state diagram.
– Antithesis
Jan 19 at 4:01
|
show 1 more comment
Σ* isn't the set of all languages. It's the single language that includes all strings.
DFAs cannot recognize any language that require an infinite number of states. For example, a^nb^n (the language containing an equal number of a's and b's). For each i, set of valid suffixes after a^i are different, so each a^i must lead to a different state and the number i is unbounded.
See: https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
Yeah, I got my definitions mixed up I think. For some reason I thought acceptance meant simply that all words in the language would be valid for a DFA. Which is wrong!
– Antithesis
Jan 19 at 3:51
add a comment |
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
});
}
});
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%2f54263751%2fcan-a-dfa-be-designed-to-accept-any-language%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Recognizing a language implies rejecting strings that don't belong in that language, not just accepting strings that do belong. The fact that you can build an automaton that accepts every string doesn't mean you can build an automaton that accepts the specific strings you need to accept and rejects everything else.
This remains true with your edit; the language accepted by an automaton is the set of all words the automaton accepts. Arbitrary subsets of that set do not count as languages accepted by that automaton. ("The language accepted by an automaton" and "the language recognized by an automaton" are synonymous.)
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
I accidentally mixed up the words recognizing and accepting. I was deliberating on this problem for awhile and started getting my thoughts mixed up. The question asks if a DFA can "accept" any language.
– Antithesis
Jan 19 at 3:23
@Antithesis: Answer expanded. It sounds like you have your definitions mixed up.
– user2357112
Jan 19 at 3:27
That makes sense, I took Formal Language Theory a few years ago, but now taking a compilers course in graduate school. Some of the math has been mixed up. Out of curiosity, how is ambiguity dealt with? i.e., how do you know some DFA computes sigma star vs some other language?
– Antithesis
Jan 19 at 3:36
@Antithesis: What ambiguity? A DFA is deterministic.
– user2357112
Jan 19 at 3:54
The ambiguity of what language a DFA is computing. If you have some DFA as a computing system, it seems like it would be really hard to determine if the accepted language is sigma star. Of course it fairly obvious if you have the state diagram.
– Antithesis
Jan 19 at 4:01
|
show 1 more comment
Recognizing a language implies rejecting strings that don't belong in that language, not just accepting strings that do belong. The fact that you can build an automaton that accepts every string doesn't mean you can build an automaton that accepts the specific strings you need to accept and rejects everything else.
This remains true with your edit; the language accepted by an automaton is the set of all words the automaton accepts. Arbitrary subsets of that set do not count as languages accepted by that automaton. ("The language accepted by an automaton" and "the language recognized by an automaton" are synonymous.)
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
I accidentally mixed up the words recognizing and accepting. I was deliberating on this problem for awhile and started getting my thoughts mixed up. The question asks if a DFA can "accept" any language.
– Antithesis
Jan 19 at 3:23
@Antithesis: Answer expanded. It sounds like you have your definitions mixed up.
– user2357112
Jan 19 at 3:27
That makes sense, I took Formal Language Theory a few years ago, but now taking a compilers course in graduate school. Some of the math has been mixed up. Out of curiosity, how is ambiguity dealt with? i.e., how do you know some DFA computes sigma star vs some other language?
– Antithesis
Jan 19 at 3:36
@Antithesis: What ambiguity? A DFA is deterministic.
– user2357112
Jan 19 at 3:54
The ambiguity of what language a DFA is computing. If you have some DFA as a computing system, it seems like it would be really hard to determine if the accepted language is sigma star. Of course it fairly obvious if you have the state diagram.
– Antithesis
Jan 19 at 4:01
|
show 1 more comment
Recognizing a language implies rejecting strings that don't belong in that language, not just accepting strings that do belong. The fact that you can build an automaton that accepts every string doesn't mean you can build an automaton that accepts the specific strings you need to accept and rejects everything else.
This remains true with your edit; the language accepted by an automaton is the set of all words the automaton accepts. Arbitrary subsets of that set do not count as languages accepted by that automaton. ("The language accepted by an automaton" and "the language recognized by an automaton" are synonymous.)
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
Recognizing a language implies rejecting strings that don't belong in that language, not just accepting strings that do belong. The fact that you can build an automaton that accepts every string doesn't mean you can build an automaton that accepts the specific strings you need to accept and rejects everything else.
This remains true with your edit; the language accepted by an automaton is the set of all words the automaton accepts. Arbitrary subsets of that set do not count as languages accepted by that automaton. ("The language accepted by an automaton" and "the language recognized by an automaton" are synonymous.)
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
edited Jan 19 at 3:26
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
answered Jan 19 at 3:18
user2357112user2357112
153k12162255
153k12162255
I accidentally mixed up the words recognizing and accepting. I was deliberating on this problem for awhile and started getting my thoughts mixed up. The question asks if a DFA can "accept" any language.
– Antithesis
Jan 19 at 3:23
@Antithesis: Answer expanded. It sounds like you have your definitions mixed up.
– user2357112
Jan 19 at 3:27
That makes sense, I took Formal Language Theory a few years ago, but now taking a compilers course in graduate school. Some of the math has been mixed up. Out of curiosity, how is ambiguity dealt with? i.e., how do you know some DFA computes sigma star vs some other language?
– Antithesis
Jan 19 at 3:36
@Antithesis: What ambiguity? A DFA is deterministic.
– user2357112
Jan 19 at 3:54
The ambiguity of what language a DFA is computing. If you have some DFA as a computing system, it seems like it would be really hard to determine if the accepted language is sigma star. Of course it fairly obvious if you have the state diagram.
– Antithesis
Jan 19 at 4:01
|
show 1 more comment
I accidentally mixed up the words recognizing and accepting. I was deliberating on this problem for awhile and started getting my thoughts mixed up. The question asks if a DFA can "accept" any language.
– Antithesis
Jan 19 at 3:23
@Antithesis: Answer expanded. It sounds like you have your definitions mixed up.
– user2357112
Jan 19 at 3:27
That makes sense, I took Formal Language Theory a few years ago, but now taking a compilers course in graduate school. Some of the math has been mixed up. Out of curiosity, how is ambiguity dealt with? i.e., how do you know some DFA computes sigma star vs some other language?
– Antithesis
Jan 19 at 3:36
@Antithesis: What ambiguity? A DFA is deterministic.
– user2357112
Jan 19 at 3:54
The ambiguity of what language a DFA is computing. If you have some DFA as a computing system, it seems like it would be really hard to determine if the accepted language is sigma star. Of course it fairly obvious if you have the state diagram.
– Antithesis
Jan 19 at 4:01
I accidentally mixed up the words recognizing and accepting. I was deliberating on this problem for awhile and started getting my thoughts mixed up. The question asks if a DFA can "accept" any language.
– Antithesis
Jan 19 at 3:23
I accidentally mixed up the words recognizing and accepting. I was deliberating on this problem for awhile and started getting my thoughts mixed up. The question asks if a DFA can "accept" any language.
– Antithesis
Jan 19 at 3:23
@Antithesis: Answer expanded. It sounds like you have your definitions mixed up.
– user2357112
Jan 19 at 3:27
@Antithesis: Answer expanded. It sounds like you have your definitions mixed up.
– user2357112
Jan 19 at 3:27
That makes sense, I took Formal Language Theory a few years ago, but now taking a compilers course in graduate school. Some of the math has been mixed up. Out of curiosity, how is ambiguity dealt with? i.e., how do you know some DFA computes sigma star vs some other language?
– Antithesis
Jan 19 at 3:36
That makes sense, I took Formal Language Theory a few years ago, but now taking a compilers course in graduate school. Some of the math has been mixed up. Out of curiosity, how is ambiguity dealt with? i.e., how do you know some DFA computes sigma star vs some other language?
– Antithesis
Jan 19 at 3:36
@Antithesis: What ambiguity? A DFA is deterministic.
– user2357112
Jan 19 at 3:54
@Antithesis: What ambiguity? A DFA is deterministic.
– user2357112
Jan 19 at 3:54
The ambiguity of what language a DFA is computing. If you have some DFA as a computing system, it seems like it would be really hard to determine if the accepted language is sigma star. Of course it fairly obvious if you have the state diagram.
– Antithesis
Jan 19 at 4:01
The ambiguity of what language a DFA is computing. If you have some DFA as a computing system, it seems like it would be really hard to determine if the accepted language is sigma star. Of course it fairly obvious if you have the state diagram.
– Antithesis
Jan 19 at 4:01
|
show 1 more comment
Σ* isn't the set of all languages. It's the single language that includes all strings.
DFAs cannot recognize any language that require an infinite number of states. For example, a^nb^n (the language containing an equal number of a's and b's). For each i, set of valid suffixes after a^i are different, so each a^i must lead to a different state and the number i is unbounded.
See: https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
Yeah, I got my definitions mixed up I think. For some reason I thought acceptance meant simply that all words in the language would be valid for a DFA. Which is wrong!
– Antithesis
Jan 19 at 3:51
add a comment |
Σ* isn't the set of all languages. It's the single language that includes all strings.
DFAs cannot recognize any language that require an infinite number of states. For example, a^nb^n (the language containing an equal number of a's and b's). For each i, set of valid suffixes after a^i are different, so each a^i must lead to a different state and the number i is unbounded.
See: https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
Yeah, I got my definitions mixed up I think. For some reason I thought acceptance meant simply that all words in the language would be valid for a DFA. Which is wrong!
– Antithesis
Jan 19 at 3:51
add a comment |
Σ* isn't the set of all languages. It's the single language that includes all strings.
DFAs cannot recognize any language that require an infinite number of states. For example, a^nb^n (the language containing an equal number of a's and b's). For each i, set of valid suffixes after a^i are different, so each a^i must lead to a different state and the number i is unbounded.
See: https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
Σ* isn't the set of all languages. It's the single language that includes all strings.
DFAs cannot recognize any language that require an infinite number of states. For example, a^nb^n (the language containing an equal number of a's and b's). For each i, set of valid suffixes after a^i are different, so each a^i must lead to a different state and the number i is unbounded.
See: https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
answered Jan 19 at 3:26
Matt TimmermansMatt Timmermans
19.4k11632
19.4k11632
Yeah, I got my definitions mixed up I think. For some reason I thought acceptance meant simply that all words in the language would be valid for a DFA. Which is wrong!
– Antithesis
Jan 19 at 3:51
add a comment |
Yeah, I got my definitions mixed up I think. For some reason I thought acceptance meant simply that all words in the language would be valid for a DFA. Which is wrong!
– Antithesis
Jan 19 at 3:51
Yeah, I got my definitions mixed up I think. For some reason I thought acceptance meant simply that all words in the language would be valid for a DFA. Which is wrong!
– Antithesis
Jan 19 at 3:51
Yeah, I got my definitions mixed up I think. For some reason I thought acceptance meant simply that all words in the language would be valid for a DFA. Which is wrong!
– Antithesis
Jan 19 at 3:51
add a comment |
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.
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%2f54263751%2fcan-a-dfa-be-designed-to-accept-any-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
