@article{ALMEIDA201948,
    Abstract = {In this paper we consider the problem of cycle-free context-free grammars equivalence. To every context-free grammar there corresponds a system of formal equations. Formally applying the iteration method to this system we obtain the grammar axiom in the form of a formal power series composed of the words generated by the grammar ''multiplied'' by the respective ambiguities. We define a transform that attributes a matrix meaning to the system of formal equations and to formal power series: terminal symbols are substituted by matrices and formal sum and product are substituted by the matrix ones. In order to effectively compute the sum of a matrix series we numerically solve the system of matrix equations. We prove distinguishability theorems showing that if two formal power series generated by cycle-free context-free grammars are different, then there exists a matrix substitution such that the sums of the respective matrix series are different. Based on this result, we suggest a procedure that can resolve the problem of equivalence of cycle-free context-free grammars in many practical cases. The results obtained in this paper form a theoretical basis for algorithms oriented to automatic assessment of students' answers in computer science. We present the respective algorithms. Then we compare our approach with a simple heuristic method based on CYK algorithm and discuss the limitations of our method.},
    Author = {Almeida, Jos{\'e} Jo{\\textasciitilde a}o and Grande, Eliana and Smirnov, Georgi},
    File = {On solving cycle-free context-free grammar equivalence problem using numerical analysis - 1-s2.0-S1045926X18301848-main.pdf},
    ISSN = {2590-1184},
    Journal = {Journal of Computer Languages},
    Keywords = {Formal languages, Context-free grammars, Automatic assessment},
    Pages = {48-56},
    Title = {On solving cycle-free context-free grammar equivalence problem using numerical analysis},
    URL = {https://www.sciencedirect.com/science/article/pii/S1045926X18301848},
    Volume = {51},
    Year = {2019},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S1045926X18301848},
    bdsk-url-2 = {https://doi.org/10.1016/j.cola.2019.02.005},
    date-added = {2023-06-09 17:50:10 +0200},
    date-modified = {2023-06-09 17:50:10 +0200},
    doi = {10.1016/j.cola.2019.02.005}
}

@article{ALMEIDA201948, Abstract = {In this paper we consider the problem of cycle-free context-free grammars equivalence. To every context-free grammar there corresponds a system of formal equations. Formally applying the iteration method to this system we obtain the grammar axiom in the form of a formal power series composed of the words generated by the grammar ''multiplied'' by the respective ambiguities. We define a transform that attributes a matrix meaning to the system of formal equations and to formal power series: terminal symbols are substituted by matrices and formal sum and product are substituted by the matrix ones. In order to effectively compute the sum of a matrix series we numerically solve the system of matrix equations. We prove distinguishability theorems showing that if two formal power series generated by cycle-free context-free grammars are different, then there exists a matrix substitution such that the sums of the respective matrix series are different. Based on this result, we suggest a procedure that can resolve the problem of equivalence of cycle-free context-free grammars in many practical cases. The results obtained in this paper form a theoretical basis for algorithms oriented to automatic assessment of students' answers in computer science. We present the respective algorithms. Then we compare our approach with a simple heuristic method based on CYK algorithm and discuss the limitations of our method.}, Author = {Almeida, Jos{\'e} Jo{\textasciitilde a}o and Grande, Eliana and Smirnov, Georgi}, File = {On solving cycle-free context-free grammar equivalence problem using numerical analysis - 1-s2.0-S1045926X18301848-main.pdf}, ISSN = {2590-1184}, Journal = {Journal of Computer Languages}, Keywords = {Formal languages, Context-free grammars, Automatic assessment}, Pages = {48-56}, Title = {On solving cycle-free context-free grammar equivalence problem using numerical analysis}, URL = {https://www.sciencedirect.com/science/article/pii/S1045926X18301848}, Volume = {51}, Year = {2019}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S1045926X18301848}, bdsk-url-2 = {https://doi.org/10.1016/j.cola.2019.02.005}, date-added = {2023-06-09 17:50:10 +0200}, date-modified = {2023-06-09 17:50:10 +0200}, doi = {10.1016/j.cola.2019.02.005} }