Journal of Computer Technology & Applications
Grammars with Exclusion
Abstract
AbstractFormal grammars represent a practical tool for description and processing programming languages, as well as for modeling and study of natural languages. In this paper, we introduce and study a new type of formal grammars—grammars with exclusion. Procedures of language generation by grammars with exclusion are elaborated. In contrast to conventional formal grammars, one grammar with exclusion can generate several types of languages. It isdemonstrated that they have essentially higher computational power and expressive possibilities in comparison with the conventional formal grammars, as well as with grammars with prohibition or Boolean grammars. Results presented in this paper are aimed at the development of modeling natural languages, empowerment of programming languages, human–machine interaction, computer simulation, better software systems, and theory of recursion.Keywords: Formal grammar, formal language, hierarchy, natural language, programming languageCite this ArticleBurgin M. Grammars with exclusion. Journal of Computer Technology & Applications. 2015; 6(2): 56–66p.References (26)
- Backus JW. The Syntax and Semantics of the Proposed International Algebraic Language. Proceedings of the International Conference on Information Processing; 1959 Jun 15 –20; UNESCO House, Paris. 125–32p.
- Martin JC. Introduction to Languages and the Theory of Computation . New York/San Francisco/London: McGrow Hill; 1991.
- Schwitter R. Working for Two: a Bidirectional Grammar for a Controlled Natural Language, AI 2008: Advances in Artificial Intelligence. Lecture Notes in Computer Science. 2008; 5360: 168–79p.
- Jacobs PS. Knowledge structures for natural language generation. Proceedings of the 11th Conference on Computational Linguistics; 1986 Aug 25 –29; Bonn, Germany. 554–9p.
- Burgin M. Grammars with Prohibition and Human-Computer Interaction. Proceedings of the Business and Industry Simulation Symposium, Society for Modeling and Simulation International ; 2005; San Diego, California. 143–7p.
- Burgin M. Complexity of grammars with prohibition. Abstracts of papers presented to the American Mathematical Society . 2005b; 26(3): 459–60p. Journal of Computer Technology & Applications Volume 6, Issue 2 ISSN: 2229-6964(online), ISSN: 2347-7229(print) JoCTA (2015) 56-66 © STM Journals 2015. All Rights Reserved Page 66
- Burgin M. Basic Classes of Grammars with Prohibition . Formal Langua ges and Automata Theory. 2013; 1302.5181: 15 p. Available from: http://arXiv.org (electronic edition)
- Carlucci L, Case J, Jain S. Learning Correction Grammars. Lecture Notes in Computer Science. 2007; 4539: 203–17p.
- Case J, Jain S. Rice and Rice -Shapiro Theorems for Transfinite Correction Grammars. Mathematical Logic Quarterly. 2011; 57(5): 1–13p.
- Chomsky N. Three models for the description of language . IRE Transactions on Information Theory. 1956; 2: 113–24p.
- Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory , Languages, and Computation . Boston/San Francisco/New York: Addison Wesley; 2001.
- Newman P. Towards convenient bi - directional grammar formalisms. Proceedings of the 13 th Conference on Computational Linguistics COLING '90 ; 1990 Aug 20 –25; Helsinki, Finland. 294 – 8p.
- Burgin M. Super-recursive Algorithms . New York/Heidelberg/Berlin : Springer; 2005.
- Shoenfield JR. Mathematical Logic . K Peters, Ltd.: Association for Symbolic Logic; 2001.
- Linz P. An Introduction to Formal Languages and Autom ata. Sudbury, MA: Jones & Bartlett Learning; 2011.
- Markman EM. Categorization and naming in children : Problems of induction . Cambridge, MA: MIT Press; 1989.
- Jaswal V, Markman EM. Learning proper and common names in inferential versus obstensive contexts. Child Development. 2001; 72(3): 768–86p.
- Freivalds R, Karpinski M, Smith CH. Co - Learning of Total Recursive Functions. Proceedings of the 7 th Annual Conference on Computational Learning Theory COLT 1994; 1994 Jul 12 –15; New Brunswick, NJ, USA. 190–7p.
- Jespersen O. Growth and structure of the English language . Garden City, New York: Doubleday&Co.; 1955.
- Nowak MA, Krakauer DC. The evolution of language. Proc Natl Acad Sci USA. 1999; 96: 8028–33p.
- Christiansen MH, Kirby S. Language evolution: consensus and cont roversies. Trends in Cognitive Science . 2003; 7(7): 300–7p.
- Murata M, Lee D, Mani M. Taxonomy of XML Schema Languages using Formal Language Theory. ACM Transactions on Internet Technology (TOIT); 2005; 5(4): 660–704p.
- Kolmogorov AN. On the Concept of Algorithm. Russian Mathematical Surveys. 1953; 8(4): 175–6p.
- Aho A. Indexed Grammars Journal of the ACM. 1968; 15(4): 647–71p.
- Knuth DE. The genesis of attribute grammars. Proceedings of the International Conference on Attribute Grammars and their Applications, Lecture Notes in Computer Science. 1990; 461: 1– 12p.
- Parchmann R, Duske J, Specht. Closure Properties of Deterministic Indexed Languages. Information and Control . 1980; 46: 200–18p. Cite this Article Burgin M. Grammars with exclusion. Journal of Computer Technology & Applications. 2015; 6(2): 56–66p.