1
$\begingroup$

If we change the right arrow in the rewriting rules of grammar into equators , changes all terminals into x and keep the non-terminals unchanged,we get system of equations.In some cases,those equations can be solved to get the generating function of the language,like non-inherently ambiguous languages(please see analytical combinatorics by Flajolet etc. for details).

And we know we can reduce a diophantine equation to some form with four variables and some degrees or with 13 variables and less degrees.

Now,the question: does there exist reduced grammars in forms with similar feathers as to the reduced Diophantine equations?

If there exists grammars in such forms,what is the link between the reduced grammar and reduced Diophantine equations?

Possibly,there are some approach to solving the question by automata theory,but I have not tried it.

$\endgroup$

0

Your Answer

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