Mixing
Find the language an NFA recognizes
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
For example, I have an NFA $A_n$ with alphabet $Sigma = 0, 1$.
The language recognized by this NFA is known to be $v$.
I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q_1$, plus the $q_n$ toward $s$. I know without the edge $q_n rightarrow s$, the answer should be $0,1^* cdot 1 cdot 0,1^n-1$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?
automata regular-languages finite-automata
asked 7 hours ago
John
233
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
4
down vote
favorite
For example, I have an NFA $A_n$ with alphabet $Sigma = 0, 1$.
The language recognized by this NFA is known to be $v$.
I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q_1$, plus the $q_n$ toward $s$. I know without the edge $q_n rightarrow s$, the answer should be $0,1^* cdot 1 cdot 0,1^n-1$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?
automata regular-languages finite-automata
asked 7 hours ago
John
233
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter.
– Deep Joshi
6 hours ago
Thanks for the reply but I still don't see why :(
– John
6 hours ago
Do you see multiple finite controls of automaton in the same state at any point?
– Deep Joshi
6 hours ago
I'm not sure what you meant by "multiple finite controls of automaton" (sorry, English is not my native language). But I do see that with n=2 and input=11111, there are two ways the NFA can be recognized: $s s s s q_1 q_2$ or $s q_1 q_2 s q_1 q_2$. I get it now the $1v$ part in $u1v$ - the suffix of strings in the language doesn't change with/without that extra edge, but I don't understand why there is no restrictions in the $u$ part.
– John
6 hours ago
What else I have observed is that if the input starts with 0, ensuring that the first step is $ss$, then there's only one way the input can be recognized - looping the $ss$ for the entire $u$ part, until there are $n$ letters left. The "go back to start" edge will be ignored in this case.
– John
6 hours ago
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
For example, I have an NFA $A_n$ with alphabet $Sigma = 0, 1$.
The language recognized by this NFA is known to be $v$.
I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q_1$, plus the $q_n$ toward $s$. I know without the edge $q_n rightarrow s$, the answer should be $0,1^* cdot 1 cdot 0,1^n-1$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?
automata regular-languages finite-automata
asked 7 hours ago
John
233
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
For example, I have an NFA $A_n$ with alphabet $Sigma = 0, 1$.
The language recognized by this NFA is known to be $v$.
I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q_1$, plus the $q_n$ toward $s$. I know without the edge $q_n rightarrow s$, the answer should be $0,1^* cdot 1 cdot 0,1^n-1$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?
automata regular-languages finite-automata
automata regular-languages finite-automata
asked 7 hours ago
John
233
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 hours ago
John
233
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 hours ago
John
233
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 7 hours ago
John
233
asked 7 hours ago
John
233
233
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
John is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter.
– Deep Joshi
6 hours ago
Thanks for the reply but I still don't see why :(
– John
6 hours ago
Do you see multiple finite controls of automaton in the same state at any point?
– Deep Joshi
6 hours ago
I'm not sure what you meant by "multiple finite controls of automaton" (sorry, English is not my native language). But I do see that with n=2 and input=11111, there are two ways the NFA can be recognized: $s s s s q_1 q_2$ or $s q_1 q_2 s q_1 q_2$. I get it now the $1v$ part in $u1v$ - the suffix of strings in the language doesn't change with/without that extra edge, but I don't understand why there is no restrictions in the $u$ part.
– John
6 hours ago
What else I have observed is that if the input starts with 0, ensuring that the first step is $ss$, then there's only one way the input can be recognized - looping the $ss$ for the entire $u$ part, until there are $n$ letters left. The "go back to start" edge will be ignored in this case.
– John
6 hours ago
add a comment |Â
Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter.
– Deep Joshi
6 hours ago
Thanks for the reply but I still don't see why :(
– John
6 hours ago
Do you see multiple finite controls of automaton in the same state at any point?
– Deep Joshi
6 hours ago
I'm not sure what you meant by "multiple finite controls of automaton" (sorry, English is not my native language). But I do see that with n=2 and input=11111, there are two ways the NFA can be recognized: $s s s s q_1 q_2$ or $s q_1 q_2 s q_1 q_2$. I get it now the $1v$ part in $u1v$ - the suffix of strings in the language doesn't change with/without that extra edge, but I don't understand why there is no restrictions in the $u$ part.
– John
6 hours ago
What else I have observed is that if the input starts with 0, ensuring that the first step is $ss$, then there's only one way the input can be recognized - looping the $ss$ for the entire $u$ part, until there are $n$ letters left. The "go back to start" edge will be ignored in this case.
– John
6 hours ago
Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter.
– Deep Joshi
6 hours ago
Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter.
– Deep Joshi
6 hours ago
Thanks for the reply but I still don't see why :(
– John
6 hours ago
Thanks for the reply but I still don't see why :(
– John
6 hours ago
Do you see multiple finite controls of automaton in the same state at any point?
– Deep Joshi
6 hours ago
Do you see multiple finite controls of automaton in the same state at any point?
– Deep Joshi
6 hours ago
I'm not sure what you meant by "multiple finite controls of automaton" (sorry, English is not my native language). But I do see that with n=2 and input=11111, there are two ways the NFA can be recognized: $s s s s q_1 q_2$ or $s q_1 q_2 s q_1 q_2$. I get it now the $1v$ part in $u1v$ - the suffix of strings in the language doesn't change with/without that extra edge, but I don't understand why there is no restrictions in the $u$ part.
– John
6 hours ago
I'm not sure what you meant by "multiple finite controls of automaton" (sorry, English is not my native language). But I do see that with n=2 and input=11111, there are two ways the NFA can be recognized: $s s s s q_1 q_2$ or $s q_1 q_2 s q_1 q_2$. I get it now the $1v$ part in $u1v$ - the suffix of strings in the language doesn't change with/without that extra edge, but I don't understand why there is no restrictions in the $u$ part.
– John
6 hours ago
What else I have observed is that if the input starts with 0, ensuring that the first step is $ss$, then there's only one way the input can be recognized - looping the $ss$ for the entire $u$ part, until there are $n$ letters left. The "go back to start" edge will be ignored in this case.
– John
6 hours ago
What else I have observed is that if the input starts with 0, ensuring that the first step is $ss$, then there's only one way the input can be recognized - looping the $ss$ for the entire $u$ part, until there are $n$ letters left. The "go back to start" edge will be ignored in this case.
– John
6 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Let $r=0,1^*.1.0,1^n-1$, be the RegularExpression representing the path $s$ to $q_n$.
Now including the transition from $q_n$ to $s$, $r$ becomes, $R=r.(0,1.r)^*$. In $r$, the starting $0,1^*$ is the superset of $r$'s ending $0,1^n-1$.
That is, $0,1^n-1 in 0,1^*, forall n ge 1$
$0,1 = 0,1^2-1 space implies 0,1 in 0,1^*$.
This means that in $R$, ending of the every $r$ concatenates with $0,1$ inside the brackets of $R$ to becomes $0,1^n$. Now this overlaps with $0,1^*$ from the start of $r$ to become $0,1^*$. This becomes recursive and eats up the entire regular expression.
$implies space R = r space and space R=R.(0,1.R)^*$
Hence, $R=0,1^*.1.0,1^n-1$.
Note
You can alternatively prove this by expanding and rearranging $R=r.(0,1.r)^*$.
answered 2 hours ago
RandomPerfectHashFunction
563
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Thanks! Didn't realize I can see this problem from the perspective of RE.
– John
1 hour ago
add a comment |Â
up vote
2
down vote
The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.
answered 48 mins ago
David Richerby
61.5k1594179
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Let $r=0,1^*.1.0,1^n-1$, be the RegularExpression representing the path $s$ to $q_n$.
Now including the transition from $q_n$ to $s$, $r$ becomes, $R=r.(0,1.r)^*$. In $r$, the starting $0,1^*$ is the superset of $r$'s ending $0,1^n-1$.
That is, $0,1^n-1 in 0,1^*, forall n ge 1$
$0,1 = 0,1^2-1 space implies 0,1 in 0,1^*$.
This means that in $R$, ending of the every $r$ concatenates with $0,1$ inside the brackets of $R$ to becomes $0,1^n$. Now this overlaps with $0,1^*$ from the start of $r$ to become $0,1^*$. This becomes recursive and eats up the entire regular expression.
$implies space R = r space and space R=R.(0,1.R)^*$
Hence, $R=0,1^*.1.0,1^n-1$.
Note
You can alternatively prove this by expanding and rearranging $R=r.(0,1.r)^*$.
answered 2 hours ago
RandomPerfectHashFunction
563
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Thanks! Didn't realize I can see this problem from the perspective of RE.
– John
1 hour ago
add a comment |Â
up vote
2
down vote
accepted
Let $r=0,1^*.1.0,1^n-1$, be the RegularExpression representing the path $s$ to $q_n$.
Now including the transition from $q_n$ to $s$, $r$ becomes, $R=r.(0,1.r)^*$. In $r$, the starting $0,1^*$ is the superset of $r$'s ending $0,1^n-1$.
That is, $0,1^n-1 in 0,1^*, forall n ge 1$
$0,1 = 0,1^2-1 space implies 0,1 in 0,1^*$.
This means that in $R$, ending of the every $r$ concatenates with $0,1$ inside the brackets of $R$ to becomes $0,1^n$. Now this overlaps with $0,1^*$ from the start of $r$ to become $0,1^*$. This becomes recursive and eats up the entire regular expression.
$implies space R = r space and space R=R.(0,1.R)^*$
Hence, $R=0,1^*.1.0,1^n-1$.
Note
You can alternatively prove this by expanding and rearranging $R=r.(0,1.r)^*$.
answered 2 hours ago
RandomPerfectHashFunction
563
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Thanks! Didn't realize I can see this problem from the perspective of RE.
– John
1 hour ago
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Let $r=0,1^*.1.0,1^n-1$, be the RegularExpression representing the path $s$ to $q_n$.
Now including the transition from $q_n$ to $s$, $r$ becomes, $R=r.(0,1.r)^*$. In $r$, the starting $0,1^*$ is the superset of $r$'s ending $0,1^n-1$.
That is, $0,1^n-1 in 0,1^*, forall n ge 1$
$0,1 = 0,1^2-1 space implies 0,1 in 0,1^*$.
This means that in $R$, ending of the every $r$ concatenates with $0,1$ inside the brackets of $R$ to becomes $0,1^n$. Now this overlaps with $0,1^*$ from the start of $r$ to become $0,1^*$. This becomes recursive and eats up the entire regular expression.
$implies space R = r space and space R=R.(0,1.R)^*$
Hence, $R=0,1^*.1.0,1^n-1$.
Note
You can alternatively prove this by expanding and rearranging $R=r.(0,1.r)^*$.
answered 2 hours ago
RandomPerfectHashFunction
563
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Let $r=0,1^*.1.0,1^n-1$, be the RegularExpression representing the path $s$ to $q_n$.
Now including the transition from $q_n$ to $s$, $r$ becomes, $R=r.(0,1.r)^*$. In $r$, the starting $0,1^*$ is the superset of $r$'s ending $0,1^n-1$.
That is, $0,1^n-1 in 0,1^*, forall n ge 1$
$0,1 = 0,1^2-1 space implies 0,1 in 0,1^*$.
This means that in $R$, ending of the every $r$ concatenates with $0,1$ inside the brackets of $R$ to becomes $0,1^n$. Now this overlaps with $0,1^*$ from the start of $r$ to become $0,1^*$. This becomes recursive and eats up the entire regular expression.
$implies space R = r space and space R=R.(0,1.R)^*$
Hence, $R=0,1^*.1.0,1^n-1$.
Note
You can alternatively prove this by expanding and rearranging $R=r.(0,1.r)^*$.
answered 2 hours ago
RandomPerfectHashFunction
563
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 hours ago
RandomPerfectHashFunction
563
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 2 hours ago
RandomPerfectHashFunction
563
answered 2 hours ago
RandomPerfectHashFunction
563
563
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
RandomPerfectHashFunction is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Thanks! Didn't realize I can see this problem from the perspective of RE.
– John
1 hour ago
add a comment |Â
Thanks! Didn't realize I can see this problem from the perspective of RE.
– John
1 hour ago
Thanks! Didn't realize I can see this problem from the perspective of RE.
– John
1 hour ago
Thanks! Didn't realize I can see this problem from the perspective of RE.
– John
1 hour ago
add a comment |Â
up vote
2
down vote
The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.
answered 48 mins ago
David Richerby
61.5k1594179
add a comment |Â
up vote
2
down vote
The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.
answered 48 mins ago
David Richerby
61.5k1594179
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.
answered 48 mins ago
David Richerby
61.5k1594179
The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.
answered 48 mins ago
David Richerby
61.5k1594179
answered 48 mins ago
David Richerby
61.5k1594179
answered 48 mins ago
David Richerby
61.5k1594179
answered 48 mins ago
David Richerby
61.5k1594179
61.5k1594179
add a comment |Â
add a comment |Â
John is a new contributor. Be nice, and check out our Code of Conduct.
John is a new contributor. Be nice, and check out our Code of Conduct.
John is a new contributor. Be nice, and check out our Code of Conduct.
John is a new contributor. Be nice, and check out our Code of Conduct.
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f97311%2ffind-the-language-an-nfa-recognizes%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Try to trace the automaton with n = 2 and input string 11111. You might get something that why that edge doesn't matter.
– Deep Joshi
6 hours ago
Thanks for the reply but I still don't see why :(
– John
6 hours ago
Do you see multiple finite controls of automaton in the same state at any point?
– Deep Joshi
6 hours ago
I'm not sure what you meant by "multiple finite controls of automaton" (sorry, English is not my native language). But I do see that with n=2 and input=11111, there are two ways the NFA can be recognized: $s s s s q_1 q_2$ or $s q_1 q_2 s q_1 q_2$. I get it now the $1v$ part in $u1v$ - the suffix of strings in the language doesn't change with/without that extra edge, but I don't understand why there is no restrictions in the $u$ part.
– John
6 hours ago
What else I have observed is that if the input starts with 0, ensuring that the first step is $ss$, then there's only one way the input can be recognized - looping the $ss$ for the entire $u$ part, until there are $n$ letters left. The "go back to start" edge will be ignored in this case.
– John
6 hours ago