0
$\begingroup$

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the complement of EQPDA to solve this but I am honestly really unsure. Any tips that could point me in the right direction or solutions to this or similar problems?

Here is one attempt to solve this problem:
DifferentPDADFA = {<M1, M2> | M1 is a PDA and M2 is a PDA, L(M1) != L(M2)}
Write a turing machine, C, to decide the language of M1
Write a turing machine, D, to decide the language of M2
ALLCFG = {<G, w> | G is a CFG, L(G)=Σ*}
ALLCFG' = {<G, w> | G is a CFG, L(G) != Σ*}
Since ALLCFG is known to be undecidable, its complement ALLCFG' is also undeciable.
Use turing machine A, which simulates ALLCFG'.
AllCFG' <ₘ L
F -> Input <D, P, w>:
1. Construct Turing Machine Y to simulate PDA P
Y<P, w>:
On Input X:
1. Ignore Input X
2. Convert our PDA P to a CFG G (page 147)
3. Simulate A with <G, w> and return what A returns.
2. Construct Turing Machine Z to simulate DFA D
Z<D, w>:
On Input X:
1. Ignore Input X, accept.

Output <Z, Y>

Since Z ignores all inputs the language accepted by L(Z) is always Σ*.
If A accepts <G, w> then L(Y) != Σ*, therefore L(Y) != L(Z).
If A rejects <G, w> then L(Y) must be Σ*, therefore L(Y) = L(Z).
Therefore A accepting <G, w> <=> L(Y) != L(Z)
Since we know that ALLCFG' is undeciable, L is also undeciable.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Here is a tip. List all undecidable problems that involve context-free languages or PDA that are explained in your textbook/lecture notes. Does any one of them involve a regular language? Tell us about them. $\endgroup$
    – John L.
    Commented Apr 29, 2022 at 2:55
  • $\begingroup$ Here is another tip. Have you searched PDA DFA undecidability or, what might be better, context-free regular undecidability? $\endgroup$
    – John L.
    Commented Apr 29, 2022 at 3:23
  • $\begingroup$ Thanks for replying. I did find two proofs that stood out a possible solutions. ACFG and EQCFG. ACFG is proving whether a CFG generates some string W is decidable. EQCFG uses ACFG to prove whether or not the language of two CFG is equivalent, it is undecidable. Would it be possible to convert my DFA and PDA to CFGs and then use EQCFG to determine if two language are equal but return the opposite of what a TM deciding EQCFG would return? $\endgroup$
    – akysu
    Commented Apr 29, 2022 at 3:23
  • 1
    $\begingroup$ Another idea I had is to construct two TMs one that will accept all strings to represent L(M1), so L(M1) = Σ*, and the other uses a TM that decides ECFG to see if it generates string W, to represent L(M2). ECFG simply tells us if a CFG is empty or not. We can then reduce this to Atm compliment because when when because when the TM that decides ECFG accepts our CFG, we end up with L(M1) != L(M2), since L(M2) = ∅, and when that TM rejects we end up with L(M2) = Σ*, meaning L(M1) and L(M2) are equal. I am not sure if this captures my idea well, I can write it out formally if needed? $\endgroup$
    – akysu
    Commented Apr 29, 2022 at 3:33
  • $\begingroup$ Congratulations! I was afraid that your textbook did not cover ALLCFG. Well, it is somewhat deceptive since apparently, there is no regular language involves in ALLCFG. Well, in fact, $\Sigma^*$ is one of the simplest and most useful languages. $\endgroup$
    – John L.
    Commented Apr 29, 2022 at 17:22

1 Answer 1

Reset to default
0
$\begingroup$

Let $Different_{DFA,PDA} = \{<M_1,M_2> \vert \ M_1 \text{ is a DFA and } M_2 \text{ is a PDA where } L(M_1) \neq L(M_2)\}$, we want to show that this language is undecidable

Let $ALL_\text{CFG} = \{<G> | \text{ G is a CFG and } L(G) = Σ^*\}$, as we know this language is undecidable, hence its complement, ${\overline{ALL}}_\text{CFG} = \{<G> | \text{ G is a CFG and } L(G) \neq Σ^*\}$, is also undecidable

We will reduce ${\overline{ALL}}_\text{CFG}$ to $Different_{DFA,PDA}$, hence showing that the latter is undecidable

The following machine $F$ computes the reduction $f$

$F$ = “On input :

  1. Convert $G$ into an equivalent $PDA$ $P$
  2. Let $D$ be the $DFA$ recognising the language $\Sigma^*$
  3. output $<D,P>$”

If $L(G) \neq \Sigma^*$, then $L(P) \neq L(D)$, and so $<D,P> \in Different_{DFA,PDA}$

If $L(G) = \Sigma^*$, then $L(P) = L(D)$, and so $<D,P> \notin Different_{DFA,PDA}$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.