Drawing a dfsa where L is a set of strings that contains at most 4 zeros
For each of the following languages over alphabet $Σ = {0, 1}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are correct.
Use as few states as possible in your DFSA.
(a) $L_1 = {x: text{x is a set of string that contains at most 4 zeros} }$
The regex is
$$R_1 = 1^{∗} + 1^{∗}01^{∗} + 1^{∗}01^{∗}01^{∗} + 1^*01^*01^*01^* + 1^*01^*01^*01^*01^*$$
How would I draw the dfsa for it?
computer-science automata regular-language
edited Nov 27 '18 at 10:17
dkaeae
304311
asked Nov 5 '18 at 10:20
shah
384
add a comment |
For each of the following languages over alphabet $Σ = {0, 1}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are correct.
Use as few states as possible in your DFSA.
(a) $L_1 = {x: text{x is a set of string that contains at most 4 zeros} }$
The regex is
$$R_1 = 1^{∗} + 1^{∗}01^{∗} + 1^{∗}01^{∗}01^{∗} + 1^*01^*01^*01^* + 1^*01^*01^*01^*01^*$$
How would I draw the dfsa for it?
computer-science automata regular-language
edited Nov 27 '18 at 10:17
dkaeae
304311
asked Nov 5 '18 at 10:20
shah
384
add a comment |
For each of the following languages over alphabet $Σ = {0, 1}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are correct.
Use as few states as possible in your DFSA.
(a) $L_1 = {x: text{x is a set of string that contains at most 4 zeros} }$
The regex is
$$R_1 = 1^{∗} + 1^{∗}01^{∗} + 1^{∗}01^{∗}01^{∗} + 1^*01^*01^*01^* + 1^*01^*01^*01^*01^*$$
How would I draw the dfsa for it?
computer-science automata regular-language
edited Nov 27 '18 at 10:17
dkaeae
304311
asked Nov 5 '18 at 10:20
shah
384
For each of the following languages over alphabet $Σ = {0, 1}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are correct.
Use as few states as possible in your DFSA.
(a) $L_1 = {x: text{x is a set of string that contains at most 4 zeros} }$
The regex is
$$R_1 = 1^{∗} + 1^{∗}01^{∗} + 1^{∗}01^{∗}01^{∗} + 1^*01^*01^*01^* + 1^*01^*01^*01^*01^*$$
How would I draw the dfsa for it?
computer-science automata regular-language
computer-science automata regular-language
edited Nov 27 '18 at 10:17
dkaeae
304311
asked Nov 5 '18 at 10:20
shah
384
edited Nov 27 '18 at 10:17
dkaeae
304311
asked Nov 5 '18 at 10:20
shah
384
edited Nov 27 '18 at 10:17
dkaeae
304311
edited Nov 27 '18 at 10:17
dkaeae
304311
edited Nov 27 '18 at 10:17
dkaeae
304311
304311
asked Nov 5 '18 at 10:20
shah
384
asked Nov 5 '18 at 10:20
shah
384
asked Nov 5 '18 at 10:20
shah
384
384
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Here are the state transitions:
$s_0rightarrow_1 s_0$,
$s_0rightarrow_0 s_1$,
$s_1rightarrow_1 s_1$,
$s_1rightarrow_0 s_2$,
$s_2rightarrow_1 s_2$,
$s_2rightarrow_0 s_3$,
$s_3rightarrow_1 s_3$,
$s_3rightarrow_0 s_4$,
$s_4rightarrow_1 s_4$.
$s_0$ is the starting state and all states are final states.
Start in state $s_0$. Produce any number of 1's and then exit or read 0 and move to state $s_1$. In state $s_1$ produce any number of 1's and then exit or read 0 and move to state $s_2$, and so on.
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$
– shah
Nov 5 '18 at 10:38
Depends on the definition. Are you allowed to have $epsilon$ transitions (empty word)?
– Wuestenfux
Nov 5 '18 at 10:41
A DFSA is a 5-tuple $M = (Q, Sigma, delta, s, f)$. Q is the set of states, $Sigma$ is the input alphabet, $delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $epsilon$ transition
– shah
Nov 5 '18 at 10:44
1
So you can have a set of accepting states, not just one.
– Wuestenfux
Nov 5 '18 at 10:46
Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too
– shah
Nov 5 '18 at 10:51
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%2f2985571%2fdrawing-a-dfsa-where-l-is-a-set-of-strings-that-contains-at-most-4-zeros%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
Here are the state transitions:
$s_0rightarrow_1 s_0$,
$s_0rightarrow_0 s_1$,
$s_1rightarrow_1 s_1$,
$s_1rightarrow_0 s_2$,
$s_2rightarrow_1 s_2$,
$s_2rightarrow_0 s_3$,
$s_3rightarrow_1 s_3$,
$s_3rightarrow_0 s_4$,
$s_4rightarrow_1 s_4$.
$s_0$ is the starting state and all states are final states.
Start in state $s_0$. Produce any number of 1's and then exit or read 0 and move to state $s_1$. In state $s_1$ produce any number of 1's and then exit or read 0 and move to state $s_2$, and so on.
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$
– shah
Nov 5 '18 at 10:38
Depends on the definition. Are you allowed to have $epsilon$ transitions (empty word)?
– Wuestenfux
Nov 5 '18 at 10:41
A DFSA is a 5-tuple $M = (Q, Sigma, delta, s, f)$. Q is the set of states, $Sigma$ is the input alphabet, $delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $epsilon$ transition
– shah
Nov 5 '18 at 10:44
1
So you can have a set of accepting states, not just one.
– Wuestenfux
Nov 5 '18 at 10:46
Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too
– shah
Nov 5 '18 at 10:51
add a comment |
Here are the state transitions:
$s_0rightarrow_1 s_0$,
$s_0rightarrow_0 s_1$,
$s_1rightarrow_1 s_1$,
$s_1rightarrow_0 s_2$,
$s_2rightarrow_1 s_2$,
$s_2rightarrow_0 s_3$,
$s_3rightarrow_1 s_3$,
$s_3rightarrow_0 s_4$,
$s_4rightarrow_1 s_4$.
$s_0$ is the starting state and all states are final states.
Start in state $s_0$. Produce any number of 1's and then exit or read 0 and move to state $s_1$. In state $s_1$ produce any number of 1's and then exit or read 0 and move to state $s_2$, and so on.
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$
– shah
Nov 5 '18 at 10:38
Depends on the definition. Are you allowed to have $epsilon$ transitions (empty word)?
– Wuestenfux
Nov 5 '18 at 10:41
A DFSA is a 5-tuple $M = (Q, Sigma, delta, s, f)$. Q is the set of states, $Sigma$ is the input alphabet, $delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $epsilon$ transition
– shah
Nov 5 '18 at 10:44
1
So you can have a set of accepting states, not just one.
– Wuestenfux
Nov 5 '18 at 10:46
Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too
– shah
Nov 5 '18 at 10:51
add a comment |
Here are the state transitions:
$s_0rightarrow_1 s_0$,
$s_0rightarrow_0 s_1$,
$s_1rightarrow_1 s_1$,
$s_1rightarrow_0 s_2$,
$s_2rightarrow_1 s_2$,
$s_2rightarrow_0 s_3$,
$s_3rightarrow_1 s_3$,
$s_3rightarrow_0 s_4$,
$s_4rightarrow_1 s_4$.
$s_0$ is the starting state and all states are final states.
Start in state $s_0$. Produce any number of 1's and then exit or read 0 and move to state $s_1$. In state $s_1$ produce any number of 1's and then exit or read 0 and move to state $s_2$, and so on.
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
Here are the state transitions:
$s_0rightarrow_1 s_0$,
$s_0rightarrow_0 s_1$,
$s_1rightarrow_1 s_1$,
$s_1rightarrow_0 s_2$,
$s_2rightarrow_1 s_2$,
$s_2rightarrow_0 s_3$,
$s_3rightarrow_1 s_3$,
$s_3rightarrow_0 s_4$,
$s_4rightarrow_1 s_4$.
$s_0$ is the starting state and all states are final states.
Start in state $s_0$. Produce any number of 1's and then exit or read 0 and move to state $s_1$. In state $s_1$ produce any number of 1's and then exit or read 0 and move to state $s_2$, and so on.
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
edited Nov 5 '18 at 11:12
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
answered Nov 5 '18 at 10:25
Wuestenfux
3,5791411
3,5791411
Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$
– shah
Nov 5 '18 at 10:38
Depends on the definition. Are you allowed to have $epsilon$ transitions (empty word)?
– Wuestenfux
Nov 5 '18 at 10:41
A DFSA is a 5-tuple $M = (Q, Sigma, delta, s, f)$. Q is the set of states, $Sigma$ is the input alphabet, $delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $epsilon$ transition
– shah
Nov 5 '18 at 10:44
1
So you can have a set of accepting states, not just one.
– Wuestenfux
Nov 5 '18 at 10:46
Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too
– shah
Nov 5 '18 at 10:51
add a comment |
Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$
– shah
Nov 5 '18 at 10:38
Depends on the definition. Are you allowed to have $epsilon$ transitions (empty word)?
– Wuestenfux
Nov 5 '18 at 10:41
A DFSA is a 5-tuple $M = (Q, Sigma, delta, s, f)$. Q is the set of states, $Sigma$ is the input alphabet, $delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $epsilon$ transition
– shah
Nov 5 '18 at 10:44
1
So you can have a set of accepting states, not just one.
– Wuestenfux
Nov 5 '18 at 10:46
Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too
– shah
Nov 5 '18 at 10:51
Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$
– shah
Nov 5 '18 at 10:38
Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$
– shah
Nov 5 '18 at 10:38
Depends on the definition. Are you allowed to have $epsilon$ transitions (empty word)?
– Wuestenfux
Nov 5 '18 at 10:41
Depends on the definition. Are you allowed to have $epsilon$ transitions (empty word)?
– Wuestenfux
Nov 5 '18 at 10:41
A DFSA is a 5-tuple $M = (Q, Sigma, delta, s, f)$. Q is the set of states, $Sigma$ is the input alphabet, $delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $epsilon$ transition
– shah
Nov 5 '18 at 10:44
A DFSA is a 5-tuple $M = (Q, Sigma, delta, s, f)$. Q is the set of states, $Sigma$ is the input alphabet, $delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $epsilon$ transition
– shah
Nov 5 '18 at 10:44
1
1
So you can have a set of accepting states, not just one.
– Wuestenfux
Nov 5 '18 at 10:46
So you can have a set of accepting states, not just one.
– Wuestenfux
Nov 5 '18 at 10:46
Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too
– shah
Nov 5 '18 at 10:51
Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too
– shah
Nov 5 '18 at 10:51
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2fmath.stackexchange.com%2fquestions%2f2985571%2fdrawing-a-dfsa-where-l-is-a-set-of-strings-that-contains-at-most-4-zeros%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
