How to prove the emptiness of intersection of two context free languages is undecidable?Are these two languages context free?Is the intersection of two context free languages recursively enumerable?Prove that context free languages are not closed under swapping prefixes and suffixesHow to prove that a language is context-free?Intersection of context free with regular languagesExamples of context-free languages with a non-context-free complementsWhy is deciding regularity of a context-free language undecidable?Can an intersection of two context-free languages be an undecidable language?decidability about intersection of regular language and context free languageUndecidable problem intersection of two DCFL languages is DCFL?
Explain Ant-Man's "not it" scene from Avengers: Endgame
Why don't B747s start takeoffs with full throttle?
How to connect an offset point symbol to its original position in QGIS?
Chopin: marche funèbre bar 15 impossible place
What is the right way to float a home lab?
Did Darth Vader wear the same suit for 20+ years?
California: "For quality assurance, this phone call is being recorded"
Who operates delivery flights for commercial airlines?
What do we gain with higher order logics?
How could a possessed body begin to rot and decay while it is still alive?
What flavor of zksnark in tezos
Credit card offering 0.5 miles for every cent rounded up. Too good to be true?
The ring of global sections of a regular scheme
Initialize an std::array algorithmically at compile time
Why were the Night's Watch required to be celibate?
What is a simple, physical situation where complex numbers emerge naturally?
Past participle agreement with the subject in the case of pronominal verbs
Count down from 0 to 5 seconds and repeat
Do I include animal companions when calculating difficulty of an encounter?
How to pass a regex when finding a directory path in bash?
Traffic law UK, pedestrians
What does War Machine's "Canopy! Canopy!" line mean in "Avengers: Endgame"?
Is it a problem that pull requests are approved without any comments
Why does a helium balloon rise?
How to prove the emptiness of intersection of two context free languages is undecidable?
Are these two languages context free?Is the intersection of two context free languages recursively enumerable?Prove that context free languages are not closed under swapping prefixes and suffixesHow to prove that a language is context-free?Intersection of context free with regular languagesExamples of context-free languages with a non-context-free complementsWhy is deciding regularity of a context-free language undecidable?Can an intersection of two context-free languages be an undecidable language?decidability about intersection of regular language and context free languageUndecidable problem intersection of two DCFL languages is DCFL?
$begingroup$
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe have a book or paper I should investigate?
formal-languages context-free reference-request undecidability
edited May 18 at 18:13
Apass.Jack
16.4k11246
asked May 18 at 14:51
CilencoCilenco
25517
$endgroup$
add a comment |
$begingroup$
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe have a book or paper I should investigate?
formal-languages context-free reference-request undecidability
edited May 18 at 18:13
Apass.Jack
16.4k11246
asked May 18 at 14:51
CilencoCilenco
25517
$endgroup$
add a comment |
$begingroup$
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe have a book or paper I should investigate?
formal-languages context-free reference-request undecidability
edited May 18 at 18:13
Apass.Jack
16.4k11246
asked May 18 at 14:51
CilencoCilenco
25517
$endgroup$
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.
Do you maybe have a book or paper I should investigate?
formal-languages context-free reference-request undecidability
formal-languages context-free reference-request undecidability
edited May 18 at 18:13
Apass.Jack
16.4k11246
asked May 18 at 14:51
CilencoCilenco
25517
edited May 18 at 18:13
Apass.Jack
16.4k11246
asked May 18 at 14:51
CilencoCilenco
25517
edited May 18 at 18:13
Apass.Jack
16.4k11246
edited May 18 at 18:13
Apass.Jack
16.4k11246
edited May 18 at 18:13
Apass.Jack
16.4k11246
16.4k11246
asked May 18 at 14:51
CilencoCilenco
25517
asked May 18 at 14:51
CilencoCilenco
25517
asked May 18 at 14:51
CilencoCilenco
25517
25517
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.
Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set $d_1,cdots,d_n$ of dominos where, for $i=1,cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars
$$Wto w_1Wd_1mid w_2Wd_2midcdotsmid w_nWd_nmid w_1d_1mid w_2d_2midcdotsmid w_nd_n$$
and
$$Xto x_1Xd_1mid x_2Xd_2midcdotsmid x_nXd_nmid x_1d_1mid x_2d_2midcdotsmid x_nd_n.$$
Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
$endgroup$
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
May 22 at 9:48
$begingroup$
Let $s$ be generated by $W$, i.e., $s=w_i_1w_i_2cdots w_i_kd_i_kcdots d_i_2d_i_1$. If it is also generated by $X$, then $s=x_i_1x_i_2cdots x_i_kd_i_kcdots d_i_2d_i_1$. Cancelling $d_i_kcdots d_i_2d_i_1$, we get $w_i_1w_i_2cdots w_i_k=x_i_1x_i_2cdots x_i_k$. Treating $d_i$ as the domino $dfracw_ix_i$, we get $d_i_1d_i_2cdots d_i_k=dfracw_i_1x_i_1dfracw_i_2x_i_2cdotsdfracw_i_nx_i_n$, where the top and bottom are the same string.
$endgroup$
– Apass.Jack
May 22 at 21:35
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
,
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%2fcs.stackexchange.com%2fquestions%2f109510%2fhow-to-prove-the-emptiness-of-intersection-of-two-context-free-languages-is-unde%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
$begingroup$
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.
Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set $d_1,cdots,d_n$ of dominos where, for $i=1,cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars
$$Wto w_1Wd_1mid w_2Wd_2midcdotsmid w_nWd_nmid w_1d_1mid w_2d_2midcdotsmid w_nd_n$$
and
$$Xto x_1Xd_1mid x_2Xd_2midcdotsmid x_nXd_nmid x_1d_1mid x_2d_2midcdotsmid x_nd_n.$$
Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
$endgroup$
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
May 22 at 9:48
$begingroup$
Let $s$ be generated by $W$, i.e., $s=w_i_1w_i_2cdots w_i_kd_i_kcdots d_i_2d_i_1$. If it is also generated by $X$, then $s=x_i_1x_i_2cdots x_i_kd_i_kcdots d_i_2d_i_1$. Cancelling $d_i_kcdots d_i_2d_i_1$, we get $w_i_1w_i_2cdots w_i_k=x_i_1x_i_2cdots x_i_k$. Treating $d_i$ as the domino $dfracw_ix_i$, we get $d_i_1d_i_2cdots d_i_k=dfracw_i_1x_i_1dfracw_i_2x_i_2cdotsdfracw_i_nx_i_n$, where the top and bottom are the same string.
$endgroup$
– Apass.Jack
May 22 at 21:35
add a comment |
$begingroup$
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.
Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set $d_1,cdots,d_n$ of dominos where, for $i=1,cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars
$$Wto w_1Wd_1mid w_2Wd_2midcdotsmid w_nWd_nmid w_1d_1mid w_2d_2midcdotsmid w_nd_n$$
and
$$Xto x_1Xd_1mid x_2Xd_2midcdotsmid x_nXd_nmid x_1d_1mid x_2d_2midcdotsmid x_nd_n.$$
Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
$endgroup$
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
May 22 at 9:48
$begingroup$
Let $s$ be generated by $W$, i.e., $s=w_i_1w_i_2cdots w_i_kd_i_kcdots d_i_2d_i_1$. If it is also generated by $X$, then $s=x_i_1x_i_2cdots x_i_kd_i_kcdots d_i_2d_i_1$. Cancelling $d_i_kcdots d_i_2d_i_1$, we get $w_i_1w_i_2cdots w_i_k=x_i_1x_i_2cdots x_i_k$. Treating $d_i$ as the domino $dfracw_ix_i$, we get $d_i_1d_i_2cdots d_i_k=dfracw_i_1x_i_1dfracw_i_2x_i_2cdotsdfracw_i_nx_i_n$, where the top and bottom are the same string.
$endgroup$
– Apass.Jack
May 22 at 21:35
add a comment |
$begingroup$
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.
Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set $d_1,cdots,d_n$ of dominos where, for $i=1,cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars
$$Wto w_1Wd_1mid w_2Wd_2midcdotsmid w_nWd_nmid w_1d_1mid w_2d_2midcdotsmid w_nd_n$$
and
$$Xto x_1Xd_1mid x_2Xd_2midcdotsmid x_nXd_nmid x_1d_1mid x_2d_2midcdotsmid x_nd_n.$$
Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
$endgroup$
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.
Proof: By a reduction of post correspondence problem (which is known to be undecidable) to the empty intersection problem.
Given a set $d_1,cdots,d_n$ of dominos where, for $i=1,cdots,n$, the top string of $d_i$ is $w_i$ and the bottom string of $d_i = x_i$. Consider the context-free grammars
$$Wto w_1Wd_1mid w_2Wd_2midcdotsmid w_nWd_nmid w_1d_1mid w_2d_2midcdotsmid w_nd_n$$
and
$$Xto x_1Xd_1mid x_2Xd_2midcdotsmid x_nXd_nmid x_1d_1mid x_2d_2midcdotsmid x_nd_n.$$
Now notice that the given instance of PCS has a match exactly when the intersection of the languages generated by the resulting grammars above is nonempty.
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
answered May 18 at 16:56
Apass.JackApass.Jack
16.4k11246
16.4k11246
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
May 22 at 9:48
$begingroup$
Let $s$ be generated by $W$, i.e., $s=w_i_1w_i_2cdots w_i_kd_i_kcdots d_i_2d_i_1$. If it is also generated by $X$, then $s=x_i_1x_i_2cdots x_i_kd_i_kcdots d_i_2d_i_1$. Cancelling $d_i_kcdots d_i_2d_i_1$, we get $w_i_1w_i_2cdots w_i_k=x_i_1x_i_2cdots x_i_k$. Treating $d_i$ as the domino $dfracw_ix_i$, we get $d_i_1d_i_2cdots d_i_k=dfracw_i_1x_i_1dfracw_i_2x_i_2cdotsdfracw_i_nx_i_n$, where the top and bottom are the same string.
$endgroup$
– Apass.Jack
May 22 at 21:35
add a comment |
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
May 22 at 9:48
$begingroup$
Let $s$ be generated by $W$, i.e., $s=w_i_1w_i_2cdots w_i_kd_i_kcdots d_i_2d_i_1$. If it is also generated by $X$, then $s=x_i_1x_i_2cdots x_i_kd_i_kcdots d_i_2d_i_1$. Cancelling $d_i_kcdots d_i_2d_i_1$, we get $w_i_1w_i_2cdots w_i_k=x_i_1x_i_2cdots x_i_k$. Treating $d_i$ as the domino $dfracw_ix_i$, we get $d_i_1d_i_2cdots d_i_k=dfracw_i_1x_i_1dfracw_i_2x_i_2cdotsdfracw_i_nx_i_n$, where the top and bottom are the same string.
$endgroup$
– Apass.Jack
May 22 at 21:35
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
May 22 at 9:48
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
May 22 at 9:48
$begingroup$
Let $s$ be generated by $W$, i.e., $s=w_i_1w_i_2cdots w_i_kd_i_kcdots d_i_2d_i_1$. If it is also generated by $X$, then $s=x_i_1x_i_2cdots x_i_kd_i_kcdots d_i_2d_i_1$. Cancelling $d_i_kcdots d_i_2d_i_1$, we get $w_i_1w_i_2cdots w_i_k=x_i_1x_i_2cdots x_i_k$. Treating $d_i$ as the domino $dfracw_ix_i$, we get $d_i_1d_i_2cdots d_i_k=dfracw_i_1x_i_1dfracw_i_2x_i_2cdotsdfracw_i_nx_i_n$, where the top and bottom are the same string.
$endgroup$
– Apass.Jack
May 22 at 21:35
$begingroup$
Let $s$ be generated by $W$, i.e., $s=w_i_1w_i_2cdots w_i_kd_i_kcdots d_i_2d_i_1$. If it is also generated by $X$, then $s=x_i_1x_i_2cdots x_i_kd_i_kcdots d_i_2d_i_1$. Cancelling $d_i_kcdots d_i_2d_i_1$, we get $w_i_1w_i_2cdots w_i_k=x_i_1x_i_2cdots x_i_k$. Treating $d_i$ as the domino $dfracw_ix_i$, we get $d_i_1d_i_2cdots d_i_k=dfracw_i_1x_i_1dfracw_i_2x_i_2cdotsdfracw_i_nx_i_n$, where the top and bottom are the same string.
$endgroup$
– Apass.Jack
May 22 at 21:35
add a comment |
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f109510%2fhow-to-prove-the-emptiness-of-intersection-of-two-context-free-languages-is-unde%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
