Processing languages and grammars

There are three basic kinds ways in which a grammar for a language can be processed:

1. recognition: determination of whether a sentence belongs to the language described by the grammar or not.
2. generation: production of a sentence belonging to the language described by the grammar.
3. learning: creation of a grammar which describes a given language by generalising over the sentences of the language.

An extension of the recognition problem is parsing. In addition to determining whether a sentence belongs to a language or not, a parser assigns a structure to each sentence, based on the rules of the grammar which describes the language.

Recognisers:

For a context-free language, a deterministic recogniser algorithm is easy to describe in informal terms:

1. Input: Regular grammar, start symbol, string in
2. Output: True or False (i.e. "accepted" or "not accepted"
3. Method:
   1. Initialisation: Store the start symbol and the string.
   2. Termination condition:
      if no symbol is stored and the string is empty, emit "True" and terminate.
   3. Iteration condition:
      if the first symbol in the store is nonterminal,
      retrieve the rule from the grammar whose left-hand side matches the stored symbol and substitute the the right-hand side of the grammar for the stored symbol.
      if the first symbol in the store is nonterminal and matches the first symbol on the string,
      remove the first symbol from the store and the first symbol from the string and repeat from (2).
   4. Exclusion condition:
      If either the Termination condition or any of the cases of the Iteration condition does not hold, emit "False" and terminate.

This algorithm describes a top-down depth-first left-right deterministic recogniser. These terms will be explained below.

Parsers:

A parser differs from a recogniser in that its output is a structure which summarises the rules which have applied to the substrings of the input string, not a Boolean value. The strategies available for traversing the string and the grammar are the same for parsers and for recognisers.

Task:

Search the web:

1. Definitions of context-free recognisers (maybe also others),
2. Definitions of context-free parsers (maybe also others),
3. How many different kinds of parser can you identify?
4. Look for information on Chomsky's contribution to linguistics and computer science (and the philosophy of mind and international politics...).
5. Find characterisations of search strategies in the context of Artifial Intelligence terms, or in the context of Computational Linguistics.
6. Search for descriptions of applications of search to
   • Concordancing
   • Lexical retrieval
   • Information retrieval
   • Database querying
   • Text mining
   • Data mining
7. Find a definition of the term agenda or schedule in connection with parsing strategies (or search strategies in general).