Názor ke článku Turingovsky úplná bezkontextová gramatika od storm trooper - A. co je to preterminal? B. existuje na to...

A. co je to preterminal?

B. existuje na to nejaky efektivni algoritmus? Jestli to spravne chapu tak naivni algoritmus by musel:

1. vygenerovat vsechny mozne derivacni stromy te zakladni gramatiky, kterych muze byt obecne exponencialni mnozstvi...
2. pro kazdy derivacni strom sestavit formuli a pomoci SAT/SMT solveru testovat splnitelnost, coz muze mit obecne exponencialni slozitost...

jestli je tohle jediny algoritmus tak to nezni moc uzitecne ;-)