Usually formal grammars have production rules in the format N=tNt where simple concatenation function is used for the expansion of the nonterminal. https://www.grammaticalframework.org/ has concrete grammars (e.g. FoodEng https://www.grammaticalframework.org/doc/tutorial/gf-tutorial.html#toc19 grammar) with more general production rules which involve special functions for handling inflextion, gender agreement and so on. Are there grammars (and corresponding deterministic finite automata) that can handle grammars whose production rules involve functions beyond simple concatenation?

  • 1
    $\begingroup$ Well, tree grammars aren't just "simple concatenations", but they define trees rather than strings, so they're probably not what you're looking for. $\endgroup$ – David Richerby Nov 12 '18 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.