<p>The language <span class="math-container">$$EQ_{CFG} = \{\langle G_1,G_2 \rangle ~|~ G_1,G_2 \text{ are context free and } L(G_1) = L(G_2)\}$$</span> is known to be undecidable.</p>
<p>Suppose you had some algorithm which on input of two grammars, would give you a way to tranform one into the other. Then this process should only succeed if they produce the same language, and fail if they don't. So you could decide this undecidable set.</p>
<p>There are some catches. Maybe your grammars are not context free, or maybe you already know they are equivalent and just want the conversion, things where this would not apply.</p>

CC BY-SA 4.0
2021-07-06T10:09:19.480Z
How about transpilation or source-to-source compilation?
user16237393
CC BY-SA 4.0
2021-07-19T16:35:13.783Z
@user16237393 I guess it depends on how phrased. Equality between two turing machines is also an undecidable problem.
abrahimladha
CC BY-SA 4.0
2021-07-01T06:21:39.007Z
2021-07-01T06:21:39.007Z
abrahimladha
<p>Often I use <code>sed 's/match/replacement/'</code> in places where I would rather have a more formal tool, just because <code>sed</code> is what I know.</p>
<p>As an example, lets say I want to translate markdown to html. In sed I would start doing something like:</p>
<pre><code>s/# (.*)/&lt;h1&gt;\1&lt;/h1&gt;/
s/## (.*)/&lt;h2&gt;\1&lt;/h2&gt;/
s/### (.*)/&lt;h3&gt;\1&lt;/h3&gt;/
s/#### (.*)/&lt;h4&gt;\1&lt;/h4&gt;/
s/`(.*)`/&lt;pre&gt;&lt;code&gt;\1&lt;/pre&gt;&lt;/code&gt;/
# etc...
</code></pre>
<p>Now for arguments sake, lets say that I had the grammars of markdown and html (or whatever two languages are the best for this example) defined in BNF.</p>
<p>Then instead of creating an ad-hoc parser for both markdown and html, I would just have to find a tool to translate from grammar A to grammar B. Is there any such framework?</p>
<ul>
<li>For example, I know pandoc can translate from several markup languages to each-other.</li>
<li>Also a lot of languages now-a-days translate to javascript (eg: typescript, elm, purescript, coffeescript).</li>
<li>I took a look at string-rewriting/semi-Thue systems on wikipedia.</li>
</ul>
<p>I'm guessing that most of these tools do the translation by hand, rather than taking as an input two grammars and some mapping from one to the other.
Is this even possible?</p>

CC BY-SA 4.0
2021-06-20T01:59:17.873Z
In theory, if the two languages have the same compute competence.they can translate from one to another.
Hamilton
<grammars>
Given two languages and their grammars can you translate from one to the other?
user16237393
# Given two languages and their grammars can you translate from one to the other?

(Asked by: username_0 on 2021-06-16)

Often I use sed 's/match/replacement/' in places where I would rather have a more formal tool, just because sed is what I know.
As an example, lets say I want to translate markdown to html. In sed I would start doing something like:
s/# (.*)/\1/
s/## (.*)/\1/
s/### (.*)/\1/
s/#### (.*)/\1/
s/`(.*)`/\1/
# etc...

Now for arguments sake, lets say that I had the grammars of markdown and html (or whatever two languages are the best for this example) defined in BNF.
Then instead of creating an ad-hoc parser for both markdown and html, I would just have to find a tool to translate from grammar A to grammar B. Is there any such framework?

For example, I know pandoc can translate from several markup languages to each-other.
Also a lot of languages now-a-days translate to javascript (eg: typescript, elm, purescript, coffeescript).
I took a look at string-rewriting/semi-Thue systems on wikipedia.

I'm guessing that most of these tools do the translation by hand, rather than taking as an input two grammars and some mapping from one to the other.
Is this even possible?

**Tags:** grammars
> **Comments:**
> **username_1**: In theory, if the two languages have the same compute competence.they can translate from one to another.  

---

## 1 answers

### Answer by username_2 on 2021-07-01. Score: 1

The language $$EQ\_{CFG} = \{\langle G\_1,G\_2 \rangle ~|~ G\_1,G\_2 \text{ are context free and } L(G\_1) = L(G\_2)\}$$ is known to be undecidable.

Suppose you had some algorithm which on input of two grammars, would give you a way to tranform one into the other. Then this process should only succeed if they produce the same language, and fail if they don't. So you could decide this undecidable set.

There are some catches. Maybe your grammars are not context free, or maybe you already know they are equivalent and just want the conversion, things where this would not apply.

> **Comments:**
> **username_0**: How about transpilation or source-to-source compilation?  
> **username_2**: @user16237393 I guess it depends on how phrased. Equality between two turing machines is also an undecidable problem.  

---

