Define a DFA that accepts all even length binary strings that don't contain the substring “111”?
up vote
1
down vote
favorite
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated!
Hi, thanks so much to everyone who's commented. I've made some updates to my answer, and I think it works now, but I'm still not sure. Here's an updated photo below.
finite-automata discrete-mathematics
New contributor
add a comment |
up vote
1
down vote
favorite
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated!
Hi, thanks so much to everyone who's commented. I've made some updates to my answer, and I think it works now, but I'm still not sure. Here's an updated photo below.
finite-automata discrete-mathematics
New contributor
1
I think you would have to keep track of parity. One set of states for an odd number of bits seen, another for an even number.
– Tom Zych
6 hours ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated!
Hi, thanks so much to everyone who's commented. I've made some updates to my answer, and I think it works now, but I'm still not sure. Here's an updated photo below.
finite-automata discrete-mathematics
New contributor
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated!
Hi, thanks so much to everyone who's commented. I've made some updates to my answer, and I think it works now, but I'm still not sure. Here's an updated photo below.
finite-automata discrete-mathematics
finite-automata discrete-mathematics
New contributor
New contributor
edited 4 hours ago
New contributor
asked 7 hours ago
bmsh
92
92
New contributor
New contributor
1
I think you would have to keep track of parity. One set of states for an odd number of bits seen, another for an even number.
– Tom Zych
6 hours ago
add a comment |
1
I think you would have to keep track of parity. One set of states for an odd number of bits seen, another for an even number.
– Tom Zych
6 hours ago
1
1
I think you would have to keep track of parity. One set of states for an odd number of bits seen, another for an even number.
– Tom Zych
6 hours ago
I think you would have to keep track of parity. One set of states for an odd number of bits seen, another for an even number.
– Tom Zych
6 hours ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w in {0,1}^*$ or $epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$.
and so on...
Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w in {0,1}^*$ or $epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w in {0,1}^*$, and you've read odd number of letters ($epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$, and you've read odd number of letters.
And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states
Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.
New contributor
This is much, much better than your other answer. Thanks!
– David Richerby
5 hours ago
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w in {0,1}^*$ or $epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$.
and so on...
Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w in {0,1}^*$ or $epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w in {0,1}^*$, and you've read odd number of letters ($epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$, and you've read odd number of letters.
And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states
Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.
New contributor
This is much, much better than your other answer. Thanks!
– David Richerby
5 hours ago
add a comment |
up vote
2
down vote
Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w in {0,1}^*$ or $epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$.
and so on...
Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w in {0,1}^*$ or $epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w in {0,1}^*$, and you've read odd number of letters ($epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$, and you've read odd number of letters.
And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states
Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.
New contributor
This is much, much better than your other answer. Thanks!
– David Richerby
5 hours ago
add a comment |
up vote
2
down vote
up vote
2
down vote
Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w in {0,1}^*$ or $epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$.
and so on...
Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w in {0,1}^*$ or $epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w in {0,1}^*$, and you've read odd number of letters ($epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$, and you've read odd number of letters.
And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states
Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.
New contributor
Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w in {0,1}^*$ or $epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$.
and so on...
Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w in {0,1}^*$ or $epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w in {0,1}^*$, and you've read odd number of letters ($epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w in {0,1}^*$ or $1$, and you've read odd number of letters.
And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states
Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.
New contributor
New contributor
answered 6 hours ago
shahaf finder
211
211
New contributor
New contributor
This is much, much better than your other answer. Thanks!
– David Richerby
5 hours ago
add a comment |
This is much, much better than your other answer. Thanks!
– David Richerby
5 hours ago
This is much, much better than your other answer. Thanks!
– David Richerby
5 hours ago
This is much, much better than your other answer. Thanks!
– David Richerby
5 hours ago
add a comment |
bmsh is a new contributor. Be nice, and check out our Code of Conduct.
bmsh is a new contributor. Be nice, and check out our Code of Conduct.
bmsh is a new contributor. Be nice, and check out our Code of Conduct.
bmsh 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.
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%2fcs.stackexchange.com%2fquestions%2f101297%2fdefine-a-dfa-that-accepts-all-even-length-binary-strings-that-dont-contain-the%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
1
I think you would have to keep track of parity. One set of states for an odd number of bits seen, another for an even number.
– Tom Zych
6 hours ago