Mixing
Deterministic finite automata (DFA) (have odd length or end with aaa)
$begingroup$
Is my attempt is true or where am I wrong?
DFA : The set of strings over ${a, b} $ that have odd length or end with $aaa$.
automata finite-automata
edited Mar 24 '16 at 21:01
3SAT
6,34121234
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
$endgroup$
add a comment |
$begingroup$
Is my attempt is true or where am I wrong?
DFA : The set of strings over ${a, b} $ that have odd length or end with $aaa$.
automata finite-automata
edited Mar 24 '16 at 21:01
3SAT
6,34121234
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
$endgroup$
$begingroup$
Did you try finding a smaller automaton?
$endgroup$
– k.stm
Mar 24 '16 at 20:29
$begingroup$
@k.stm Yes, I tried but I couldn't find.Is this true?
$endgroup$
– zxccxz
Mar 24 '16 at 20:30
$begingroup$
Haven’t checked it. Actually, you probably do need eight states. Have you tried organizing them? Can you tell us what each of the states $1$, …, $8$ describe? (Oh, you have nine states – I think you can toss one.)
$endgroup$
– k.stm
Mar 24 '16 at 20:33
$begingroup$
@k.stm there are 8 states.It is hard to describe what each of states describe.
$endgroup$
– zxccxz
Mar 24 '16 at 20:41
$begingroup$
It looks correct to me, but the best thing to do is to run it in your computer
$endgroup$
– 3SAT
Mar 24 '16 at 20:58
add a comment |
$begingroup$
Is my attempt is true or where am I wrong?
DFA : The set of strings over ${a, b} $ that have odd length or end with $aaa$.
automata finite-automata
edited Mar 24 '16 at 21:01
3SAT
6,34121234
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
$endgroup$
Is my attempt is true or where am I wrong?
DFA : The set of strings over ${a, b} $ that have odd length or end with $aaa$.
automata finite-automata
automata finite-automata
edited Mar 24 '16 at 21:01
3SAT
6,34121234
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
edited Mar 24 '16 at 21:01
3SAT
6,34121234
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
edited Mar 24 '16 at 21:01
3SAT
6,34121234
edited Mar 24 '16 at 21:01
3SAT
6,34121234
edited Mar 24 '16 at 21:01
3SAT
6,34121234
6,34121234
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
asked Mar 24 '16 at 20:23
zxccxzzxccxz
415
415
$begingroup$
Did you try finding a smaller automaton?
$endgroup$
– k.stm
Mar 24 '16 at 20:29
$begingroup$
@k.stm Yes, I tried but I couldn't find.Is this true?
$endgroup$
– zxccxz
Mar 24 '16 at 20:30
$begingroup$
Haven’t checked it. Actually, you probably do need eight states. Have you tried organizing them? Can you tell us what each of the states $1$, …, $8$ describe? (Oh, you have nine states – I think you can toss one.)
$endgroup$
– k.stm
Mar 24 '16 at 20:33
$begingroup$
@k.stm there are 8 states.It is hard to describe what each of states describe.
$endgroup$
– zxccxz
Mar 24 '16 at 20:41
$begingroup$
It looks correct to me, but the best thing to do is to run it in your computer
$endgroup$
– 3SAT
Mar 24 '16 at 20:58
add a comment |
$begingroup$
Did you try finding a smaller automaton?
$endgroup$
– k.stm
Mar 24 '16 at 20:29
$begingroup$
@k.stm Yes, I tried but I couldn't find.Is this true?
$endgroup$
– zxccxz
Mar 24 '16 at 20:30
$begingroup$
Haven’t checked it. Actually, you probably do need eight states. Have you tried organizing them? Can you tell us what each of the states $1$, …, $8$ describe? (Oh, you have nine states – I think you can toss one.)
$endgroup$
– k.stm
Mar 24 '16 at 20:33
$begingroup$
@k.stm there are 8 states.It is hard to describe what each of states describe.
$endgroup$
– zxccxz
Mar 24 '16 at 20:41
$begingroup$
It looks correct to me, but the best thing to do is to run it in your computer
$endgroup$
– 3SAT
Mar 24 '16 at 20:58
$begingroup$
Did you try finding a smaller automaton?
$endgroup$
– k.stm
Mar 24 '16 at 20:29
$begingroup$
Did you try finding a smaller automaton?
$endgroup$
– k.stm
Mar 24 '16 at 20:29
$begingroup$
@k.stm Yes, I tried but I couldn't find.Is this true?
$endgroup$
– zxccxz
Mar 24 '16 at 20:30
$begingroup$
@k.stm Yes, I tried but I couldn't find.Is this true?
$endgroup$
– zxccxz
Mar 24 '16 at 20:30
$begingroup$
Haven’t checked it. Actually, you probably do need eight states. Have you tried organizing them? Can you tell us what each of the states $1$, …, $8$ describe? (Oh, you have nine states – I think you can toss one.)
$endgroup$
– k.stm
Mar 24 '16 at 20:33
$begingroup$
Haven’t checked it. Actually, you probably do need eight states. Have you tried organizing them? Can you tell us what each of the states $1$, …, $8$ describe? (Oh, you have nine states – I think you can toss one.)
$endgroup$
– k.stm
Mar 24 '16 at 20:33
$begingroup$
@k.stm there are 8 states.It is hard to describe what each of states describe.
$endgroup$
– zxccxz
Mar 24 '16 at 20:41
$begingroup$
@k.stm there are 8 states.It is hard to describe what each of states describe.
$endgroup$
– zxccxz
Mar 24 '16 at 20:41
$begingroup$
It looks correct to me, but the best thing to do is to run it in your computer
$endgroup$
– 3SAT
Mar 24 '16 at 20:58
$begingroup$
It looks correct to me, but the best thing to do is to run it in your computer
$endgroup$
– 3SAT
Mar 24 '16 at 20:58
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Your automaton is correct but it is not minimal. The minimal automaton only has 5 states. Actually, you can obtain it by minimising your automaton. You will then identify states 2 and 4, states 3 and 5 and states 6 and 8.
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
$endgroup$
$begingroup$
Of states $1$ and $4$, only one is an accepting state,so identifying them will lead to an inequivalent automaton. You mean $2$ and $4$, I presume.
$endgroup$
– k.stm
Mar 25 '16 at 9:26
$begingroup$
The empty word neither has odd length nor ends in $mathtt {aaa}$.
$endgroup$
– k.stm
Mar 25 '16 at 9:33
$begingroup$
There are two states 1 in the picture. Let us call $0$ the initial state to avoid any confusion.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:36
$begingroup$
No, the initial state is $1$, the other one is a $2$.
$endgroup$
– k.stm
Mar 25 '16 at 9:36
$begingroup$
OK, let me correct my answer accordingly.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:38
add a comment |
$begingroup$
Here’s a way to think about the language and the minimal finite automaton describing it:
Whenever you have began typing up a word $u$, there are eight cases you need to consider when trying to finish the word by a suffix $v$ so that the entire word $uv$ will end up in the language. And actually, they split up as $2 × 4$ cases:
How long is $u$?
- $u$ has an even number of letters.
- $u$ has an odd number of letters.
How does $u$ end?
- $u$ does not end in $mathtt a$ (by either being empty or ending in $mathtt b$).
- $u$ ends in $mathtt a$ (but not in $mathtt {aa}$).
- $u$ ends in $mathtt {aa}$ (but not in $mathtt {aaa}$).
- $u$ ends in $mathtt {aaa}$ (or in a suffix with even more $mathtt a$s).
Think about it, that’s all that matters! You should try to check your automaton using that point of view yourself. Try to think of the states in your automaton as encoding that information.
(If you don’t manage to do so or need another pair of eyes, leave a comment.)
This point of view is an insight coming from the Myhill–Nerode theorem.
This answer probably conveys the impression that one needs eight states for any automaton recognizing the given language. That’s because I thought so. But I was wrong. Nevertheless, the procedure given in my answer still works, and one can even see which cases actually behave in the same way and should therefore be considered equivalent.
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
$endgroup$
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%2f1712122%2fdeterministic-finite-automata-dfa-have-odd-length-or-end-with-aaa%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
$begingroup$
Your automaton is correct but it is not minimal. The minimal automaton only has 5 states. Actually, you can obtain it by minimising your automaton. You will then identify states 2 and 4, states 3 and 5 and states 6 and 8.
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
$endgroup$
$begingroup$
Of states $1$ and $4$, only one is an accepting state,so identifying them will lead to an inequivalent automaton. You mean $2$ and $4$, I presume.
$endgroup$
– k.stm
Mar 25 '16 at 9:26
$begingroup$
The empty word neither has odd length nor ends in $mathtt {aaa}$.
$endgroup$
– k.stm
Mar 25 '16 at 9:33
$begingroup$
There are two states 1 in the picture. Let us call $0$ the initial state to avoid any confusion.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:36
$begingroup$
No, the initial state is $1$, the other one is a $2$.
$endgroup$
– k.stm
Mar 25 '16 at 9:36
$begingroup$
OK, let me correct my answer accordingly.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:38
add a comment |
$begingroup$
Your automaton is correct but it is not minimal. The minimal automaton only has 5 states. Actually, you can obtain it by minimising your automaton. You will then identify states 2 and 4, states 3 and 5 and states 6 and 8.
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
$endgroup$
$begingroup$
Of states $1$ and $4$, only one is an accepting state,so identifying them will lead to an inequivalent automaton. You mean $2$ and $4$, I presume.
$endgroup$
– k.stm
Mar 25 '16 at 9:26
$begingroup$
The empty word neither has odd length nor ends in $mathtt {aaa}$.
$endgroup$
– k.stm
Mar 25 '16 at 9:33
$begingroup$
There are two states 1 in the picture. Let us call $0$ the initial state to avoid any confusion.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:36
$begingroup$
No, the initial state is $1$, the other one is a $2$.
$endgroup$
– k.stm
Mar 25 '16 at 9:36
$begingroup$
OK, let me correct my answer accordingly.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:38
add a comment |
$begingroup$
Your automaton is correct but it is not minimal. The minimal automaton only has 5 states. Actually, you can obtain it by minimising your automaton. You will then identify states 2 and 4, states 3 and 5 and states 6 and 8.
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
$endgroup$
Your automaton is correct but it is not minimal. The minimal automaton only has 5 states. Actually, you can obtain it by minimising your automaton. You will then identify states 2 and 4, states 3 and 5 and states 6 and 8.
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
edited Mar 25 '16 at 9:38
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
answered Mar 25 '16 at 5:01
J.-E. PinJ.-E. Pin
18.4k21754
18.4k21754
$begingroup$
Of states $1$ and $4$, only one is an accepting state,so identifying them will lead to an inequivalent automaton. You mean $2$ and $4$, I presume.
$endgroup$
– k.stm
Mar 25 '16 at 9:26
$begingroup$
The empty word neither has odd length nor ends in $mathtt {aaa}$.
$endgroup$
– k.stm
Mar 25 '16 at 9:33
$begingroup$
There are two states 1 in the picture. Let us call $0$ the initial state to avoid any confusion.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:36
$begingroup$
No, the initial state is $1$, the other one is a $2$.
$endgroup$
– k.stm
Mar 25 '16 at 9:36
$begingroup$
OK, let me correct my answer accordingly.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:38
add a comment |
$begingroup$
Of states $1$ and $4$, only one is an accepting state,so identifying them will lead to an inequivalent automaton. You mean $2$ and $4$, I presume.
$endgroup$
– k.stm
Mar 25 '16 at 9:26
$begingroup$
The empty word neither has odd length nor ends in $mathtt {aaa}$.
$endgroup$
– k.stm
Mar 25 '16 at 9:33
$begingroup$
There are two states 1 in the picture. Let us call $0$ the initial state to avoid any confusion.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:36
$begingroup$
No, the initial state is $1$, the other one is a $2$.
$endgroup$
– k.stm
Mar 25 '16 at 9:36
$begingroup$
OK, let me correct my answer accordingly.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:38
$begingroup$
Of states $1$ and $4$, only one is an accepting state,so identifying them will lead to an inequivalent automaton. You mean $2$ and $4$, I presume.
$endgroup$
– k.stm
Mar 25 '16 at 9:26
$begingroup$
Of states $1$ and $4$, only one is an accepting state,so identifying them will lead to an inequivalent automaton. You mean $2$ and $4$, I presume.
$endgroup$
– k.stm
Mar 25 '16 at 9:26
$begingroup$
The empty word neither has odd length nor ends in $mathtt {aaa}$.
$endgroup$
– k.stm
Mar 25 '16 at 9:33
$begingroup$
The empty word neither has odd length nor ends in $mathtt {aaa}$.
$endgroup$
– k.stm
Mar 25 '16 at 9:33
$begingroup$
There are two states 1 in the picture. Let us call $0$ the initial state to avoid any confusion.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:36
$begingroup$
There are two states 1 in the picture. Let us call $0$ the initial state to avoid any confusion.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:36
$begingroup$
No, the initial state is $1$, the other one is a $2$.
$endgroup$
– k.stm
Mar 25 '16 at 9:36
$begingroup$
No, the initial state is $1$, the other one is a $2$.
$endgroup$
– k.stm
Mar 25 '16 at 9:36
$begingroup$
OK, let me correct my answer accordingly.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:38
$begingroup$
OK, let me correct my answer accordingly.
$endgroup$
– J.-E. Pin
Mar 25 '16 at 9:38
add a comment |
$begingroup$
Here’s a way to think about the language and the minimal finite automaton describing it:
Whenever you have began typing up a word $u$, there are eight cases you need to consider when trying to finish the word by a suffix $v$ so that the entire word $uv$ will end up in the language. And actually, they split up as $2 × 4$ cases:
How long is $u$?
- $u$ has an even number of letters.
- $u$ has an odd number of letters.
How does $u$ end?
- $u$ does not end in $mathtt a$ (by either being empty or ending in $mathtt b$).
- $u$ ends in $mathtt a$ (but not in $mathtt {aa}$).
- $u$ ends in $mathtt {aa}$ (but not in $mathtt {aaa}$).
- $u$ ends in $mathtt {aaa}$ (or in a suffix with even more $mathtt a$s).
Think about it, that’s all that matters! You should try to check your automaton using that point of view yourself. Try to think of the states in your automaton as encoding that information.
(If you don’t manage to do so or need another pair of eyes, leave a comment.)
This point of view is an insight coming from the Myhill–Nerode theorem.
This answer probably conveys the impression that one needs eight states for any automaton recognizing the given language. That’s because I thought so. But I was wrong. Nevertheless, the procedure given in my answer still works, and one can even see which cases actually behave in the same way and should therefore be considered equivalent.
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
$endgroup$
add a comment |
$begingroup$
Here’s a way to think about the language and the minimal finite automaton describing it:
Whenever you have began typing up a word $u$, there are eight cases you need to consider when trying to finish the word by a suffix $v$ so that the entire word $uv$ will end up in the language. And actually, they split up as $2 × 4$ cases:
How long is $u$?
- $u$ has an even number of letters.
- $u$ has an odd number of letters.
How does $u$ end?
- $u$ does not end in $mathtt a$ (by either being empty or ending in $mathtt b$).
- $u$ ends in $mathtt a$ (but not in $mathtt {aa}$).
- $u$ ends in $mathtt {aa}$ (but not in $mathtt {aaa}$).
- $u$ ends in $mathtt {aaa}$ (or in a suffix with even more $mathtt a$s).
Think about it, that’s all that matters! You should try to check your automaton using that point of view yourself. Try to think of the states in your automaton as encoding that information.
(If you don’t manage to do so or need another pair of eyes, leave a comment.)
This point of view is an insight coming from the Myhill–Nerode theorem.
This answer probably conveys the impression that one needs eight states for any automaton recognizing the given language. That’s because I thought so. But I was wrong. Nevertheless, the procedure given in my answer still works, and one can even see which cases actually behave in the same way and should therefore be considered equivalent.
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
$endgroup$
add a comment |
$begingroup$
Here’s a way to think about the language and the minimal finite automaton describing it:
Whenever you have began typing up a word $u$, there are eight cases you need to consider when trying to finish the word by a suffix $v$ so that the entire word $uv$ will end up in the language. And actually, they split up as $2 × 4$ cases:
How long is $u$?
- $u$ has an even number of letters.
- $u$ has an odd number of letters.
How does $u$ end?
- $u$ does not end in $mathtt a$ (by either being empty or ending in $mathtt b$).
- $u$ ends in $mathtt a$ (but not in $mathtt {aa}$).
- $u$ ends in $mathtt {aa}$ (but not in $mathtt {aaa}$).
- $u$ ends in $mathtt {aaa}$ (or in a suffix with even more $mathtt a$s).
Think about it, that’s all that matters! You should try to check your automaton using that point of view yourself. Try to think of the states in your automaton as encoding that information.
(If you don’t manage to do so or need another pair of eyes, leave a comment.)
This point of view is an insight coming from the Myhill–Nerode theorem.
This answer probably conveys the impression that one needs eight states for any automaton recognizing the given language. That’s because I thought so. But I was wrong. Nevertheless, the procedure given in my answer still works, and one can even see which cases actually behave in the same way and should therefore be considered equivalent.
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
$endgroup$
Here’s a way to think about the language and the minimal finite automaton describing it:
Whenever you have began typing up a word $u$, there are eight cases you need to consider when trying to finish the word by a suffix $v$ so that the entire word $uv$ will end up in the language. And actually, they split up as $2 × 4$ cases:
How long is $u$?
- $u$ has an even number of letters.
- $u$ has an odd number of letters.
How does $u$ end?
- $u$ does not end in $mathtt a$ (by either being empty or ending in $mathtt b$).
- $u$ ends in $mathtt a$ (but not in $mathtt {aa}$).
- $u$ ends in $mathtt {aa}$ (but not in $mathtt {aaa}$).
- $u$ ends in $mathtt {aaa}$ (or in a suffix with even more $mathtt a$s).
Think about it, that’s all that matters! You should try to check your automaton using that point of view yourself. Try to think of the states in your automaton as encoding that information.
(If you don’t manage to do so or need another pair of eyes, leave a comment.)
This point of view is an insight coming from the Myhill–Nerode theorem.
This answer probably conveys the impression that one needs eight states for any automaton recognizing the given language. That’s because I thought so. But I was wrong. Nevertheless, the procedure given in my answer still works, and one can even see which cases actually behave in the same way and should therefore be considered equivalent.
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
edited Mar 26 '16 at 7:25
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
answered Mar 24 '16 at 21:05
k.stmk.stm
10.8k22249
10.8k22249
add a comment |
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.
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%2f1712122%2fdeterministic-finite-automata-dfa-have-odd-length-or-end-with-aaa%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
$begingroup$
Did you try finding a smaller automaton?
$endgroup$
– k.stm
Mar 24 '16 at 20:29
$begingroup$
@k.stm Yes, I tried but I couldn't find.Is this true?
$endgroup$
– zxccxz
Mar 24 '16 at 20:30
$begingroup$
Haven’t checked it. Actually, you probably do need eight states. Have you tried organizing them? Can you tell us what each of the states $1$, …, $8$ describe? (Oh, you have nine states – I think you can toss one.)
$endgroup$
– k.stm
Mar 24 '16 at 20:33
$begingroup$
@k.stm there are 8 states.It is hard to describe what each of states describe.
$endgroup$
– zxccxz
Mar 24 '16 at 20:41
$begingroup$
It looks correct to me, but the best thing to do is to run it in your computer
$endgroup$
– 3SAT
Mar 24 '16 at 20:58