Proof for minimum number of states for a epsilon free NFA is $2^n$
I have the following question which I could not proceed:
Let
$$L={w in Sigma^* mid text{all symbols of the alphabet occur even times in } w}.
$$
Prove that any NFA accepting $L$ requires $2^n$ states, where $n$ is the size of the alphabet $Sigma$.
I think I came up with a proof for a DFA using the Myhill-Nerode Theorem but I do not know how to generalize it to NFA's.
Edit:Relevant question is answered in https://stackoverflow.com/questions/9068873/how-do-we-know-that-an-nfa-has-a-minimum-amount-of-states .
proof-explanation automata
asked Nov 28 '18 at 2:15
Arda Akdemir
134
add a comment |
I have the following question which I could not proceed:
Let
$$L={w in Sigma^* mid text{all symbols of the alphabet occur even times in } w}.
$$
Prove that any NFA accepting $L$ requires $2^n$ states, where $n$ is the size of the alphabet $Sigma$.
I think I came up with a proof for a DFA using the Myhill-Nerode Theorem but I do not know how to generalize it to NFA's.
Edit:Relevant question is answered in https://stackoverflow.com/questions/9068873/how-do-we-know-that-an-nfa-has-a-minimum-amount-of-states .
proof-explanation automata
asked Nov 28 '18 at 2:15
Arda Akdemir
134
add a comment |
I have the following question which I could not proceed:
Let
$$L={w in Sigma^* mid text{all symbols of the alphabet occur even times in } w}.
$$
Prove that any NFA accepting $L$ requires $2^n$ states, where $n$ is the size of the alphabet $Sigma$.
I think I came up with a proof for a DFA using the Myhill-Nerode Theorem but I do not know how to generalize it to NFA's.
Edit:Relevant question is answered in https://stackoverflow.com/questions/9068873/how-do-we-know-that-an-nfa-has-a-minimum-amount-of-states .
proof-explanation automata
asked Nov 28 '18 at 2:15
Arda Akdemir
134
I have the following question which I could not proceed:
Let
$$L={w in Sigma^* mid text{all symbols of the alphabet occur even times in } w}.
$$
Prove that any NFA accepting $L$ requires $2^n$ states, where $n$ is the size of the alphabet $Sigma$.
I think I came up with a proof for a DFA using the Myhill-Nerode Theorem but I do not know how to generalize it to NFA's.
Edit:Relevant question is answered in https://stackoverflow.com/questions/9068873/how-do-we-know-that-an-nfa-has-a-minimum-amount-of-states .
proof-explanation automata
proof-explanation automata
asked Nov 28 '18 at 2:15
Arda Akdemir
134
asked Nov 28 '18 at 2:15
Arda Akdemir
134
edited Nov 29 '18 at 6:20
asked Nov 28 '18 at 2:15
Arda Akdemir
134
asked Nov 28 '18 at 2:15
Arda Akdemir
134
asked Nov 28 '18 at 2:15
Arda Akdemir
134
134
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
The answer to the relevant question refers to
a theorem of [1] that can be used to determine lower bounds on the number of states of a minimal NFA:
Theorem. Let $L subseteq Sigma^*$ be a regular language and suppose that there exist $n$ pairs of words $P = {(u_i, v_i) mid 1 leqslant i leqslant n }$ such that:
$u_iv_i in L$ for $1 leqslant i leqslant n$
$u_jv_i notin L$ for $1 leqslant i,j leqslant n$ and $i not= j$.
Then any NFA accepting $L$ has at least $n$ states.
Suppose that $Sigma = {a_1, dots, a_n}$. For each $i = (i_1, dots, i_n) in {0, 1}^n$, let $u_i = v_i = a_{i_1}^{i_1} a_{i_2}^{i_2} dotsm a_{i_n}^{i_n}$. By construction, $u_i$ and $v_i$ satisfy the conditions (1) and (2). Since $|{0, 1}^n| = 2^n$, any NFA accepting $L$ has at least $2^n$ states.
[1] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (2), pp. 75–77, (1996). DOI:10.1016/0020-0190(96)00095-6.
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
Thank you for the answer!
– Arda Akdemir
Nov 29 '18 at 6:20
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%2f3016610%2fproof-for-minimum-number-of-states-for-a-epsilon-free-nfa-is-2n%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
The answer to the relevant question refers to
a theorem of [1] that can be used to determine lower bounds on the number of states of a minimal NFA:
Theorem. Let $L subseteq Sigma^*$ be a regular language and suppose that there exist $n$ pairs of words $P = {(u_i, v_i) mid 1 leqslant i leqslant n }$ such that:
$u_iv_i in L$ for $1 leqslant i leqslant n$
$u_jv_i notin L$ for $1 leqslant i,j leqslant n$ and $i not= j$.
Then any NFA accepting $L$ has at least $n$ states.
Suppose that $Sigma = {a_1, dots, a_n}$. For each $i = (i_1, dots, i_n) in {0, 1}^n$, let $u_i = v_i = a_{i_1}^{i_1} a_{i_2}^{i_2} dotsm a_{i_n}^{i_n}$. By construction, $u_i$ and $v_i$ satisfy the conditions (1) and (2). Since $|{0, 1}^n| = 2^n$, any NFA accepting $L$ has at least $2^n$ states.
[1] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (2), pp. 75–77, (1996). DOI:10.1016/0020-0190(96)00095-6.
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
Thank you for the answer!
– Arda Akdemir
Nov 29 '18 at 6:20
add a comment |
The answer to the relevant question refers to
a theorem of [1] that can be used to determine lower bounds on the number of states of a minimal NFA:
Theorem. Let $L subseteq Sigma^*$ be a regular language and suppose that there exist $n$ pairs of words $P = {(u_i, v_i) mid 1 leqslant i leqslant n }$ such that:
$u_iv_i in L$ for $1 leqslant i leqslant n$
$u_jv_i notin L$ for $1 leqslant i,j leqslant n$ and $i not= j$.
Then any NFA accepting $L$ has at least $n$ states.
Suppose that $Sigma = {a_1, dots, a_n}$. For each $i = (i_1, dots, i_n) in {0, 1}^n$, let $u_i = v_i = a_{i_1}^{i_1} a_{i_2}^{i_2} dotsm a_{i_n}^{i_n}$. By construction, $u_i$ and $v_i$ satisfy the conditions (1) and (2). Since $|{0, 1}^n| = 2^n$, any NFA accepting $L$ has at least $2^n$ states.
[1] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (2), pp. 75–77, (1996). DOI:10.1016/0020-0190(96)00095-6.
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
Thank you for the answer!
– Arda Akdemir
Nov 29 '18 at 6:20
add a comment |
The answer to the relevant question refers to
a theorem of [1] that can be used to determine lower bounds on the number of states of a minimal NFA:
Theorem. Let $L subseteq Sigma^*$ be a regular language and suppose that there exist $n$ pairs of words $P = {(u_i, v_i) mid 1 leqslant i leqslant n }$ such that:
$u_iv_i in L$ for $1 leqslant i leqslant n$
$u_jv_i notin L$ for $1 leqslant i,j leqslant n$ and $i not= j$.
Then any NFA accepting $L$ has at least $n$ states.
Suppose that $Sigma = {a_1, dots, a_n}$. For each $i = (i_1, dots, i_n) in {0, 1}^n$, let $u_i = v_i = a_{i_1}^{i_1} a_{i_2}^{i_2} dotsm a_{i_n}^{i_n}$. By construction, $u_i$ and $v_i$ satisfy the conditions (1) and (2). Since $|{0, 1}^n| = 2^n$, any NFA accepting $L$ has at least $2^n$ states.
[1] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (2), pp. 75–77, (1996). DOI:10.1016/0020-0190(96)00095-6.
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
The answer to the relevant question refers to
a theorem of [1] that can be used to determine lower bounds on the number of states of a minimal NFA:
Theorem. Let $L subseteq Sigma^*$ be a regular language and suppose that there exist $n$ pairs of words $P = {(u_i, v_i) mid 1 leqslant i leqslant n }$ such that:
$u_iv_i in L$ for $1 leqslant i leqslant n$
$u_jv_i notin L$ for $1 leqslant i,j leqslant n$ and $i not= j$.
Then any NFA accepting $L$ has at least $n$ states.
Suppose that $Sigma = {a_1, dots, a_n}$. For each $i = (i_1, dots, i_n) in {0, 1}^n$, let $u_i = v_i = a_{i_1}^{i_1} a_{i_2}^{i_2} dotsm a_{i_n}^{i_n}$. By construction, $u_i$ and $v_i$ satisfy the conditions (1) and (2). Since $|{0, 1}^n| = 2^n$, any NFA accepting $L$ has at least $2^n$ states.
[1] I. Glaister and J. Shallit, A lower bound technique for the size of nondeterministic finite automata. Information Processing Letters 59 (2), pp. 75–77, (1996). DOI:10.1016/0020-0190(96)00095-6.
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
answered Nov 28 '18 at 17:36
J.-E. Pin
18.3k21754
18.3k21754
Thank you for the answer!
– Arda Akdemir
Nov 29 '18 at 6:20
add a comment |
Thank you for the answer!
– Arda Akdemir
Nov 29 '18 at 6:20
Thank you for the answer!
– Arda Akdemir
Nov 29 '18 at 6:20
Thank you for the answer!
– Arda Akdemir
Nov 29 '18 at 6:20
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%2f3016610%2fproof-for-minimum-number-of-states-for-a-epsilon-free-nfa-is-2n%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
