Non-regular language whose prefix language is regular
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I understand that prefix of a regular language is regular, but I am unable to get my head around this:
Give an example of a non-regular language $A ⊆ 0, 1^*$ for which $operatornamePrefix(A)$ is regular.
formal-languages regular-languages
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
asked Oct 4 at 0:34
hsnsd
1071
New contributor
hsnsd 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
0
down vote
favorite
I understand that prefix of a regular language is regular, but I am unable to get my head around this:
Give an example of a non-regular language $A ⊆ 0, 1^*$ for which $operatornamePrefix(A)$ is regular.
formal-languages regular-languages
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
asked Oct 4 at 0:34
hsnsd
1071
New contributor
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael♦
Oct 4 at 8:37
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I understand that prefix of a regular language is regular, but I am unable to get my head around this:
Give an example of a non-regular language $A ⊆ 0, 1^*$ for which $operatornamePrefix(A)$ is regular.
formal-languages regular-languages
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
asked Oct 4 at 0:34
hsnsd
1071
New contributor
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I understand that prefix of a regular language is regular, but I am unable to get my head around this:
Give an example of a non-regular language $A ⊆ 0, 1^*$ for which $operatornamePrefix(A)$ is regular.
formal-languages regular-languages
formal-languages regular-languages
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
asked Oct 4 at 0:34
hsnsd
1071
New contributor
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
asked Oct 4 at 0:34
hsnsd
1071
New contributor
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
edited Oct 4 at 8:38
Raphael♦
56.3k22138305
56.3k22138305
asked Oct 4 at 0:34
hsnsd
1071
New contributor
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Oct 4 at 0:34
hsnsd
1071
asked Oct 4 at 0:34
hsnsd
1071
1071
New contributor
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
hsnsd is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael♦
Oct 4 at 8:37
add a comment |Â
Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael♦
Oct 4 at 8:37
Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael♦
Oct 4 at 8:37
Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael♦
Oct 4 at 8:37
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
The language of palindromes is not a regular language. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. So the prefix language of the language of palindromes is the entire language, which is a regular language.
answered Oct 4 at 1:03
Apass.Jack
2,528224
1
Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $0^p: where p is prime $ or $0^n!: n is natural$
– Bader Abu Radi
Oct 4 at 6:03
How can computer science educators ever win this race? It's not fair.
– reinierpost
Oct 4 at 6:25
Please consider not to encourage undesirable posting behaviour.
– Raphael♦
Oct 4 at 8:37
1
@reinierpost I think it'd help your point if you elaborated what the problem is from your perspective.
– Raphael♦
Oct 4 at 8:37
@Raphael, got it. I am going to update my answer with that advice and also an extra exercise. The prefix-closed language is, in fact, quite interesting.
– Apass.Jack
Oct 4 at 14:10
 |Â
show 1 more comment
up vote
2
down vote
The other answer gives a particular example of a language fitting your bill. You can also show that almost all languages satisfy your condition.
Fix an alphabet $Sigma$, and let $L$ be a random language over $Sigma$ sampled by putting in each $w in Sigma^*$ with probability 1/2. Since there are only countably many regular languages, almost surely $L$ is not regular. Conversely, for every fixed $x in Sigma^*$, almost surely one of the infinitely many words $y in Sigma^*$ is such that $xy in L$. Since there are only countably many words in $Sigma^*$, it follows that almost surely the prefix language of $L$ is $Sigma^*$, which is regular.
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
2
Nice. And in fact over a single letter alphabet every language has a regular prefix language.
– Hendrik Jan
Oct 4 at 9:58
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
The language of palindromes is not a regular language. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. So the prefix language of the language of palindromes is the entire language, which is a regular language.
answered Oct 4 at 1:03
Apass.Jack
2,528224
1
Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $0^p: where p is prime $ or $0^n!: n is natural$
– Bader Abu Radi
Oct 4 at 6:03
How can computer science educators ever win this race? It's not fair.
– reinierpost
Oct 4 at 6:25
Please consider not to encourage undesirable posting behaviour.
– Raphael♦
Oct 4 at 8:37
1
@reinierpost I think it'd help your point if you elaborated what the problem is from your perspective.
– Raphael♦
Oct 4 at 8:37
@Raphael, got it. I am going to update my answer with that advice and also an extra exercise. The prefix-closed language is, in fact, quite interesting.
– Apass.Jack
Oct 4 at 14:10
 |Â
show 1 more comment
up vote
3
down vote
The language of palindromes is not a regular language. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. So the prefix language of the language of palindromes is the entire language, which is a regular language.
answered Oct 4 at 1:03
Apass.Jack
2,528224
1
Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $0^p: where p is prime $ or $0^n!: n is natural$
– Bader Abu Radi
Oct 4 at 6:03
How can computer science educators ever win this race? It's not fair.
– reinierpost
Oct 4 at 6:25
Please consider not to encourage undesirable posting behaviour.
– Raphael♦
Oct 4 at 8:37
1
@reinierpost I think it'd help your point if you elaborated what the problem is from your perspective.
– Raphael♦
Oct 4 at 8:37
@Raphael, got it. I am going to update my answer with that advice and also an extra exercise. The prefix-closed language is, in fact, quite interesting.
– Apass.Jack
Oct 4 at 14:10
 |Â
show 1 more comment
up vote
3
down vote
up vote
3
down vote
The language of palindromes is not a regular language. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. So the prefix language of the language of palindromes is the entire language, which is a regular language.
answered Oct 4 at 1:03
Apass.Jack
2,528224
The language of palindromes is not a regular language. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. So the prefix language of the language of palindromes is the entire language, which is a regular language.
answered Oct 4 at 1:03
Apass.Jack
2,528224
answered Oct 4 at 1:03
Apass.Jack
2,528224
answered Oct 4 at 1:03
Apass.Jack
2,528224
answered Oct 4 at 1:03
Apass.Jack
2,528224
2,528224
1
Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $0^p: where p is prime $ or $0^n!: n is natural$
– Bader Abu Radi
Oct 4 at 6:03
How can computer science educators ever win this race? It's not fair.
– reinierpost
Oct 4 at 6:25
Please consider not to encourage undesirable posting behaviour.
– Raphael♦
Oct 4 at 8:37
1
@reinierpost I think it'd help your point if you elaborated what the problem is from your perspective.
– Raphael♦
Oct 4 at 8:37
@Raphael, got it. I am going to update my answer with that advice and also an extra exercise. The prefix-closed language is, in fact, quite interesting.
– Apass.Jack
Oct 4 at 14:10
 |Â
show 1 more comment
1
Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $0^p: where p is prime $ or $0^n!: n is natural$
– Bader Abu Radi
Oct 4 at 6:03
How can computer science educators ever win this race? It's not fair.
– reinierpost
Oct 4 at 6:25
Please consider not to encourage undesirable posting behaviour.
– Raphael♦
Oct 4 at 8:37
1
@reinierpost I think it'd help your point if you elaborated what the problem is from your perspective.
– Raphael♦
Oct 4 at 8:37
@Raphael, got it. I am going to update my answer with that advice and also an extra exercise. The prefix-closed language is, in fact, quite interesting.
– Apass.Jack
Oct 4 at 14:10
1
1
Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $0^p: where p is prime $ or $0^n!: n is natural$
– Bader Abu Radi
Oct 4 at 6:03
Correct and if you want something that works with unary alphabet. You can consider the following non-regular languages: $0^p: where p is prime $ or $0^n!: n is natural$
– Bader Abu Radi
Oct 4 at 6:03
How can computer science educators ever win this race? It's not fair.
– reinierpost
Oct 4 at 6:25
How can computer science educators ever win this race? It's not fair.
– reinierpost
Oct 4 at 6:25
Please consider not to encourage undesirable posting behaviour.
– Raphael♦
Oct 4 at 8:37
Please consider not to encourage undesirable posting behaviour.
– Raphael♦
Oct 4 at 8:37
1
1
@reinierpost I think it'd help your point if you elaborated what the problem is from your perspective.
– Raphael♦
Oct 4 at 8:37
@reinierpost I think it'd help your point if you elaborated what the problem is from your perspective.
– Raphael♦
Oct 4 at 8:37
@Raphael, got it. I am going to update my answer with that advice and also an extra exercise. The prefix-closed language is, in fact, quite interesting.
– Apass.Jack
Oct 4 at 14:10
@Raphael, got it. I am going to update my answer with that advice and also an extra exercise. The prefix-closed language is, in fact, quite interesting.
– Apass.Jack
Oct 4 at 14:10
 |Â
show 1 more comment
up vote
2
down vote
The other answer gives a particular example of a language fitting your bill. You can also show that almost all languages satisfy your condition.
Fix an alphabet $Sigma$, and let $L$ be a random language over $Sigma$ sampled by putting in each $w in Sigma^*$ with probability 1/2. Since there are only countably many regular languages, almost surely $L$ is not regular. Conversely, for every fixed $x in Sigma^*$, almost surely one of the infinitely many words $y in Sigma^*$ is such that $xy in L$. Since there are only countably many words in $Sigma^*$, it follows that almost surely the prefix language of $L$ is $Sigma^*$, which is regular.
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
2
Nice. And in fact over a single letter alphabet every language has a regular prefix language.
– Hendrik Jan
Oct 4 at 9:58
add a comment |Â
up vote
2
down vote
The other answer gives a particular example of a language fitting your bill. You can also show that almost all languages satisfy your condition.
Fix an alphabet $Sigma$, and let $L$ be a random language over $Sigma$ sampled by putting in each $w in Sigma^*$ with probability 1/2. Since there are only countably many regular languages, almost surely $L$ is not regular. Conversely, for every fixed $x in Sigma^*$, almost surely one of the infinitely many words $y in Sigma^*$ is such that $xy in L$. Since there are only countably many words in $Sigma^*$, it follows that almost surely the prefix language of $L$ is $Sigma^*$, which is regular.
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
2
Nice. And in fact over a single letter alphabet every language has a regular prefix language.
– Hendrik Jan
Oct 4 at 9:58
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The other answer gives a particular example of a language fitting your bill. You can also show that almost all languages satisfy your condition.
Fix an alphabet $Sigma$, and let $L$ be a random language over $Sigma$ sampled by putting in each $w in Sigma^*$ with probability 1/2. Since there are only countably many regular languages, almost surely $L$ is not regular. Conversely, for every fixed $x in Sigma^*$, almost surely one of the infinitely many words $y in Sigma^*$ is such that $xy in L$. Since there are only countably many words in $Sigma^*$, it follows that almost surely the prefix language of $L$ is $Sigma^*$, which is regular.
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
The other answer gives a particular example of a language fitting your bill. You can also show that almost all languages satisfy your condition.
Fix an alphabet $Sigma$, and let $L$ be a random language over $Sigma$ sampled by putting in each $w in Sigma^*$ with probability 1/2. Since there are only countably many regular languages, almost surely $L$ is not regular. Conversely, for every fixed $x in Sigma^*$, almost surely one of the infinitely many words $y in Sigma^*$ is such that $xy in L$. Since there are only countably many words in $Sigma^*$, it follows that almost surely the prefix language of $L$ is $Sigma^*$, which is regular.
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
answered Oct 4 at 3:48
Yuval Filmus
183k12171333
183k12171333
2
Nice. And in fact over a single letter alphabet every language has a regular prefix language.
– Hendrik Jan
Oct 4 at 9:58
add a comment |Â
2
Nice. And in fact over a single letter alphabet every language has a regular prefix language.
– Hendrik Jan
Oct 4 at 9:58
2
2
Nice. And in fact over a single letter alphabet every language has a regular prefix language.
– Hendrik Jan
Oct 4 at 9:58
Nice. And in fact over a single letter alphabet every language has a regular prefix language.
– Hendrik Jan
Oct 4 at 9:58
add a comment |Â
hsnsd is a new contributor. Be nice, and check out our Code of Conduct.
hsnsd is a new contributor. Be nice, and check out our Code of Conduct.
hsnsd is a new contributor. Be nice, and check out our Code of Conduct.
hsnsd 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%2f98112%2fnon-regular-language-whose-prefix-language-is-regular%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
Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered.
– Raphael♦
Oct 4 at 8:37