0
$\begingroup$

I have a converter between two context-free grammars which are both describing the same language but one uses infixes other than prefixes, has different symbols and sometimes switches order of nonterminals. It's a converter in a sense that it takes an expression in one grammar and outputs its equivalent counterpart in the other grammar and vice versa. All the rules for the translation are symmetrical.

I'd like to prove (at least beyond reasonable doubt) that my two-way converter works. Would it be sufficient to generate a lot of random expressions and show that when we put them through in both ways, the result is the same? I can't really decide what that would actually 'prove', if anything.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Random examples will not prove much, you are rught. It might give you a general idea how parts of the grammar are translated into the other one. In general one might prove that some variable $A$ in one grammar generates the same strings as variable $A'$ in the other one, using case analysis. Without knowing any details I cannot add much. You might look into a textbook, where for instance some normal forms for CFG's are proven correct, like Chomsky normal form. $\endgroup$
    – Hendrik Jan
    Commented Jan 29, 2022 at 23:05

1 Answer 1

Reset to default
1
$\begingroup$

No, looking at a lot of examples doesn't prove anything.

There is no general procedure that will work for all CFGs: testing equivalence of two context-free grammars is undecidable.

So, your proof will have to use special properties of the conversion process.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well, I know it won't really 'prove' it but I'm thinking if that actually says something like 'there's a very high probability that you did this right'. $\endgroup$
    – tomashauser
    Commented Jan 30, 2022 at 11:50
  • $\begingroup$ @tomashauser, random testing is often very useful but I doubt there will be any basis for assigning a probability as a result of it. It is easy to construct conversion algorithms that are incorrect, but that are likely to pass random tests. $\endgroup$
    – D.W. ♦
    Commented Jan 30, 2022 at 21:55

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.