Formal Grammar

From GM-RKB
(Redirected from Rewriting System)
Jump to navigation Jump to search

A formal grammar is a production system with a formal specification.



References

2013

  • (Wikipedia, 2013) ⇒ en.wikipedia.org/wiki/Formal_grammar
    • In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) is a set of production rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context — only their form.

      Formal language theory, the discipline which studies formal grammars and languages, is a branch of applied mathematics. Its applications are found in theoretical computer science, theoretical linguistics, formal semantics, mathematical logic, and other areas.

      A formal grammar is a set of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, a grammar is usually thought of as a language generator. However, it can also sometimes be used as the basis for a “recognizer"—a function in computing that determines whether a given string belongs to the language or is grammatically incorrect. To describe such recognizers, formal language theory uses separate formalisms, known as automata theory. One of the interesting results of automata theory is that it is not possible to design a recognizer for certain formal languages.

      Parsing is the process of recognizing an utterance (a string in natural languages) by breaking it down to a set of symbols and analyzing each one against the grammar of the language. Most languages have the meanings of their utterances structured according to their syntax—a practice known as compositional semantics. As a result, the first step to describing the meaning of an utterance in language is to break it down part by part and look at its analyzed form (known as its parse tree in computer science, and as its deep structure in generative grammar).

2009

  • http://www.britannica.com/EBchecked/topic/228762/generative-grammar
    • a precisely formulated set of rules whose output is all (and only) the sentences of a language — i.e., of the language that it generates. There are many different kinds of generative grammar, including transformational grammar as developed by Noam Chomsky from the mid-1950s. Linguists disagree as to which, if any, of these different kinds of generative grammar will serve as the best model for the description of natural languages.
    • Generative grammars do not merely distinguish the grammatical sentence of a language from ungrammatical sequences of words of the same language; they also provide a structural description, or syntactic analysis, for each of the grammatical sentences. The structural descriptions provided by a generative grammar are comparable with, but more precisely formulated than, the analyses that result from the traditional practice of parsing sentences in terms of the parts of speech.
  • (WordNet, 2009) ⇒ http://wordnetweb.princeton.edu/perl/webwn?s=generative%20grammar
    • S: (n) generative grammar ((linguistics) a type of grammar that describes syntax in terms of a set of logical rules that can generate all and only the infinite number of grammatical sentences in a language and assigns them all the correct structural description)
  • (Wikipedia, 2009) ⇒ en.wikipedia.org/wiki/Grammar_(formal_language_theory)
    • In formal semantics, computer science and linguistics, a formal grammar (also called formation rules) is a precise description of a formal language - that is, of a set of strings over some alphabet. ...
  • (Wikipedia, 2009) ⇒ en.wikipedia.org/wiki/Syntax_(logic)
    • In logic, syntax comprises the rules governing the composition of texts in a formal language that constitute the properly formed formulas (WFFs ...
  • WordNet Syntax
    • the grammatical arrangement of words in sentences
    • a systematic orderly arrangement
    • studies of the rules for forming admissible sentences
  • (Wikipedia, 2009) ⇒ en.wikipedia.org/wiki/SYNTAX
    • In computer science, SYNTAX is a system used to generate lexical and syntactic analyzers (parsers) (both deterministic and non-deterministic) for ...
  • WordNet Grammar
    • the branch of linguistics that deals with syntax and morphology (and sometimes also deals with semantics)
  • (Wikipedia, 2009) ⇒ en.wikipedia.org/wiki/Grammar
    • Grammar is the field of linguistics that covers the rules governing the use of any given natural language. It includes morphology and syntax, often complemented by phonetics, phonology, semantics, and pragmatics.
  • Wiktionary en.wiktionary.org/wiki/Grammar
    • A system of rules and principles for speaking and writing a language; The study of the internal structure of words (morphology) and the use of ...
  • www.edgateway.net/pub/docs/pel/glossary.htm
    • The system of rules by which words are formed and put together to make sentences.

2008

  • (Crystal, 2008) ⇒ David Crystal. (2008). “A Dictionary of Linguistics and Phonetics, 6th edition." Blackwell Publishing.
    • grammar A central term in LINGUISTICS, but one which covers a wide range of phenomena, being use both in mass noun and count noun senses (as in 'grammar in general' and 'a grammar in particular'). Several types of grammar can be distinguished. … (2) A theoretical grammar goes beyond the study of individual languages, using linguistic DATA as a means of developing theoretical insights in the the nature of language as such .... formal grammar (as opposed to 'NOTIONAL grammar') …

2007

  • (Kakkonen, 2007) ⇒ Tuomo Kakkonen. (2007). “Framework and Resources for Natural Language Evaluation." Academic Dissertation. University of Joensuu.
    • A language follows the rules of a given grammar and is represented by using a particular grammar formalism.
    • Definition 3-4. Grammar, rules.
      • A grammar [math]\displaystyle{ G }[/math] is a description of a language L.
      • A grammar [math]\displaystyle{ G }[/math] consists of a lexicon and rules.
      • A lexicon is a structure that defines the terminals in a language.
      • Rules describe how the terminals combine into larger entities.
    • Definition 3-5. Language generated by a grammar, derivation, grammatical and ungrammatical strings.
      • Let L(G) denote that grammar G generates language L.
      • The process of grammar rule applications is referred to as derivation.
      • L(G) is the set of sentences that can be derived by the grammar G.
      • The sentences that grammar G generates are referred to as grammatical.
      • The sentences that are not generated by G are referred to as ungrammatical.
    • Definition 3-6. Grammar formalism and grammatical theory.
      • A grammar formalism is a language used for expressing grammars.
      • A grammatical theory is the set of statements expressed in a grammar formalism.

2003

2001

1979

  • (Hopcroft & Ullman, 1979) ⇒ John E. Hopcroft, and Jeffrey D. Ullman. (1979). “Introduction to Automata Theory, Languages and Computation.” Addison-Wesley. ISBN:020102988X