Abstract
We consider context-free grammars and Lambek grammars enriched with semantic labeling. Such grammars do not just answer whether a given word belongs to the language described by the grammar, but, if the answer is positive, also assign the word a λ-term that corresponds to the semantic value (“meaning”) of the word. We present a modification of W. Buszkowski’s direct translation of context-free grammars in the Chomsky normal form into Lambek grammars; this modification preserves semantic values of words.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Y. Bar-Hillel, C. Gaifman, and E. Shamir, “On categorial and phrase-structure grammars,” Bull. Res. Council Israel, Sect. F 9F, 1–16 (1960).
J. van Benthem, “The semantics of variety in categorial grammar,” in Categorial Grammar (J. Benjamins, Amsterdam, 1988), pp. 37–55.
W. Buszkowski, “The equivalence of unidirectional Lambek categorial grammars and context-free grammars,” Z. Math. Logik Grundlagen Math. 31, 369–384 (1985).
W. Buszkowski, “On the equivalence of Lambek categorial grammars and basic categorial grammars,” Preprint LP-93-07 (Univ. Amsterdam, Inst. Logic Lang. Comput., Amsterdam, 1993), ILLC Prepubl. Ser.
B. Carpenter, Type-Logical Semantics (MIT Press, Cambridge, MA, 1997).
N. Chomsky, “Three models for the description of language,” IRE Trans. Inf. Theory IT-2 (3), 113–124 (1956).
D. R. Dowty, R. E. Wall, and S. Peters, Introduction to Montague Semantics (D. Reidel, Dordrecht, 1981).
S. A. Greibach, “A new normal-form theorem for context-free phrase structure grammars,” J. Assoc. Comput. Mach. 12 (1), 42–52 (1965).
H. Hendriks, “Studied flexibility: Categories and types in syntax and semantics,” PhD Dissert. (Univ. Amsterdam, Amsterdam, 1993).
W. A. Howard, “The formulae-as-types notion of construction,” in To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Ed. by J. P. Seldin and H. J. Roger (Academic, London, 1980), pp. 479–490.
M. Kanazawa and S. Salvati, “The string-meaning relations definable by Lambek grammars and context-free grammars,” in Formal Grammar: Proc. 17th and 18th Int. Confs., FG 2012/2013, Ed. by G. Morrill and M.-J. Nederhof (Springer, Berlin, 2013), Lect. Notes Comput. Sci. 8036, pp. 191–208.
S. Kuznetsov, “Lambek grammars with one division and one primitive type,” Log. J. IGPL 20 (1), 207–221 (2012).
J. Lambek, “The mathematics of sentence structure,” Am. Math. Mon. 65 (3), 154–170 (1958).
M. R. Pentus, “Lambek calculus and formal grammars,” Fundam. Prikl. Mat. 1 (3), 729–751 (1995).
Yu. Savateev, “Product-free Lambek calculus is NP-complete,” in Logical Foundations of Computer Science: Proc. Int. Symp. LFCS 2009, Ed. by S. Artemov and A. Nerode (Springer, Berlin, 2009)
Yu. Savateev, Lect. Notes Comput. Sci. 5407, pp. 380–394.
Author information
Authors and Affiliations
Corresponding author
Additional information
Published in Russian in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2015, Vol. 290, pp. 72–79.
Rights and permissions
About this article
Cite this article
Kuznetsov, S.L. On translating context-free grammars into Lambek grammars. Proc. Steklov Inst. Math. 290, 63–69 (2015). https://doi.org/10.1134/S0081543815060061
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0081543815060061