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?
Can the product of any two aperiodic functions which are defined on the entire number line be periodic?
Looking for a soft substance that doesn't dissolve underwater
Website returning plaintext password
Nominativus cum infinitivo
Can a US state pass/enforce a law stating that a group of people owe money to the state government?
What are these arcade games in Ghostbusters 1984?
Is the field of q-series 'dead'?
Caught student / friend cheating on the final exam that I proctored
Dad jokes are fun
Can I tell a prospective employee that everyone in the team is leaving?
First Match - awk
Can I summon an otherworldly creature with the Gate spell without knowing its true name?
How should I introduce map drawing to my players?
What is a Power on Reset IC?
Using credit/debit card details vs swiping a card in a payment (credit card) terminal
Why did the person in charge of a principality not just declare themself king?
Have 1.5% of all nuclear reactors ever built melted down?
Is it truly impossible to tell what a CPU is doing?
What is a fully qualified name?
What could a self-sustaining lunar colony slowly lose that would ultimately prove fatal?
How to respond to upset student?
How can I tell if I'm being too picky as a referee?
Which European Languages are not Indo-European?
Is "cool" appropriate or offensive to use in IMs?
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.2k11246
asked May 18 at 14:51
CilencoCilenco
24817
$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.2k11246
asked May 18 at 14:51
CilencoCilenco
24817
$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.2k11246
asked May 18 at 14:51
CilencoCilenco
24817
$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.2k11246
asked May 18 at 14:51
CilencoCilenco
24817
edited May 18 at 18:13
Apass.Jack
16.2k11246
asked May 18 at 14:51
CilencoCilenco
24817
edited May 18 at 18:13
Apass.Jack
16.2k11246
edited May 18 at 18:13
Apass.Jack
16.2k11246
edited May 18 at 18:13
Apass.Jack
16.2k11246
16.2k11246
asked May 18 at 14:51
CilencoCilenco
24817
asked May 18 at 14:51
CilencoCilenco
24817
asked May 18 at 14:51
CilencoCilenco
24817
24817
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.2k11246
$endgroup$
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
yesterday
$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
yesterday
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.2k11246
$endgroup$
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
yesterday
$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
yesterday
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.2k11246
$endgroup$
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
yesterday
$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
yesterday
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.2k11246
$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.2k11246
answered May 18 at 16:56
Apass.JackApass.Jack
16.2k11246
answered May 18 at 16:56
Apass.JackApass.Jack
16.2k11246
answered May 18 at 16:56
Apass.JackApass.Jack
16.2k11246
16.2k11246
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
yesterday
$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
yesterday
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
yesterday
$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
yesterday
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
yesterday
$begingroup$
Using this would give me the word as well as the indices of the dominos in reverse order right?
$endgroup$
– Cilenco
yesterday
$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
yesterday
$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
yesterday
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
