Mixing
Non-regular language whose prefix language is regular
Clash Royale CLAN TAG#URR8PPP
up vote
2
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.
regular-languages
edited 1 hour ago
Yuval Filmus
183k12171332
asked 5 hours ago
hsnsd
1111
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
2
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.
regular-languages
edited 1 hour ago
Yuval Filmus
183k12171332
asked 5 hours ago
hsnsd
1111
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
2
down vote
favorite
up vote
2
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.
regular-languages
edited 1 hour ago
Yuval Filmus
183k12171332
asked 5 hours ago
hsnsd
1111
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.
regular-languages
regular-languages
edited 1 hour ago
Yuval Filmus
183k12171332
asked 5 hours ago
hsnsd
1111
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 1 hour ago
Yuval Filmus
183k12171332
asked 5 hours ago
hsnsd
1111
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 1 hour ago
Yuval Filmus
183k12171332
edited 1 hour ago
Yuval Filmus
183k12171332
edited 1 hour ago
Yuval Filmus
183k12171332
183k12171332
asked 5 hours ago
hsnsd
1111
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 5 hours ago
hsnsd
1111
asked 5 hours ago
hsnsd
1111
1111
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.
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
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 4 hours ago
Apass.Jack
2,367223
add a comment |Â
up vote
0
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 1 hour ago
Yuval Filmus
183k12171332
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
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 4 hours ago
Apass.Jack
2,367223
add a comment |Â
up vote
2
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 4 hours ago
Apass.Jack
2,367223
add a comment |Â
up vote
2
down vote
up vote
2
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 4 hours ago
Apass.Jack
2,367223
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 4 hours ago
Apass.Jack
2,367223
answered 4 hours ago
Apass.Jack
2,367223
answered 4 hours ago
Apass.Jack
2,367223
answered 4 hours ago
Apass.Jack
2,367223
2,367223
add a comment |Â
add a comment |Â
up vote
0
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 1 hour ago
Yuval Filmus
183k12171332
add a comment |Â
up vote
0
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 1 hour ago
Yuval Filmus
183k12171332
add a comment |Â
up vote
0
down vote
up vote
0
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 1 hour ago
Yuval Filmus
183k12171332
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 1 hour ago
Yuval Filmus
183k12171332
answered 1 hour ago
Yuval Filmus
183k12171332
answered 1 hour ago
Yuval Filmus
183k12171332
answered 1 hour ago
Yuval Filmus
183k12171332
183k12171332
add a comment |Â
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