Formal Gramar

Formal Grammars and NLP

Formal grammars are precise rule systems for describing which symbol sequences belong to a language. Although this lecture focuses on natural-language processing (NLP), formal grammars can describe sequences in any domain made up of discrete symbols.

Regular expressions and text processing

Regular expressions help locate or test for substrings and patterns in text. They are widely available in text editors and command-line tools, though their exact syntax can vary.

Common notation includes:

• ^ marks the start of a sequence.
• $ marks its end.
• * allows zero or more repetitions of the preceding expression.
• + allows one or more repetitions.
• Parentheses group alternatives or parts of an expression.

Familiarity with at least one regular-expression syntax is useful for searching, cleaning, and refining text data. The speaker presents this work as important to improving NLP and AI systems, even if it can be labor-intensive.

What a formal grammar is

A formal grammar specifies the boundary between valid and invalid sequences. It is commonly defined by four components:

• Start symbol: The symbol from which derivations begin.
• Nonterminal symbols: Categories that can be expanded using rules.
• Terminal symbols: Basic symbols or words that cannot be expanded further.
• Production rules: Rules specifying how symbols—especially nonterminals—can be replaced by other sequences.

A sequence belongs to the language defined by a grammar if it can be derived from the start symbol and reduced to terminals.

Derivations and parse trees

A derivation repeatedly applies production rules, starting with the start symbol, until no nonterminals remain. Each rule has a left-hand side (the symbol being replaced) and a right-hand side (the replacement sequence).

A parse tree, also called a derivation tree, records how the rules were applied. Its leaves form the resulting sentence. Derivations can expand symbols from left to right, right to left, or in another order. The order may matter in some grammars, particularly when rule application depends on context.

A single sentence can have more than one parse tree under the same grammar. This is called ambiguity and can make parsing more computationally difficult.

Sentences, languages, grammars, and parses

• A language is a set of sentences; a grammar describes that set.
• Different grammars may describe the same language.
• A sentence can have multiple parse trees, depending on the grammar and the available derivations.
• Grammars can generate valid sentences and, in principle, determine whether a given sentence is valid.

The Chomsky hierarchy

The lecture presents four major grammar classes, ordered from least to most expressive:

1. Regular grammar (Type 3): The most restricted class discussed. Its production rules have limited forms, so it describes fewer possible languages.
2. Context-free grammar (Type 2): Allows a single nonterminal on the left side of a rule and more flexible sequences on the right. The speaker describes it as useful for many natural-language structures.
3. Context-sensitive grammar (Type 1): Rule application can depend on surrounding symbols, allowing more expressive descriptions.
4. Unrestricted grammar (Type 0): Has the fewest restrictions and the greatest expressive power.

The speaker connects these classes to familiar computational models:

• Finite-state automata for regular languages
• Pushdown automata for context-free languages
• Linear-bounded automata for context-sensitive languages
• Turing machines for unrestricted languages

Expressive power and examples

The speaker illustrates expressive power by imagining different shapes used to mark valid sentences in a space of possible sequences. A simple shape may fail to include all valid examples or exclude all invalid ones; a more flexible representation can draw a more precise boundary.

A key contrast is:

• A regular pattern such as a*b* can describe any number of as followed by any number of bs.
• The language {a^k b^k} requires the number of as and bs to match. The speaker uses it to illustrate a pattern that regular grammars cannot capture, but a more expressive grammar can.

The general lesson is that the grammar type should suit the structure of the language or application being modeled. Different domains—including natural language, animal vocalizations, and music—may require different levels of expressive power.

Recursion

Grammar rules can refer back to symbols that eventually lead to themselves, creating recursion. Recursion can be represented as cycles in a graph of grammar symbols.

Such cycles may be difficult to detect in large rule sets, but recursion is also valuable: it can model repeated or nested structures found in natural phenomena.

Parsing and the CKY approach

To determine whether a sentence fits a grammar, parsing searches for valid derivations. A top-down search may face many possible rule choices. The video presents bottom-up parsing, illustrated with the CKY algorithm, as a way to narrow the search.

The basic procedure is:

1. Identify which grammatical categories can match each individual word.
2. Combine adjacent words or constituents when the grammar permits them to form a larger constituent.
3. Repeat the combination process over progressively larger spans.
4. Check whether the start symbol can cover the entire sentence. If it can, the grammar licenses the sentence; otherwise, no complete derivation was found.

The lecture briefly connects parsing to computational complexity, mentioning polynomial-time problems and the P/NP distinction. This connection is introduced briefly and somewhat imprecisely: P and NP are complexity classes and should not be treated as simply equivalent to deterministic and nondeterministic finite-state automata.

Speakers and sources featured

• Speaker: One unnamed lecturer, presenting the material for IRR Lab.
• Named sources or references mentioned: Noam Chomsky; the University of Pennsylvania; the Linguistic Data Consortium (LDC); and regular-expression support in Microsoft Word and vi/Linux text-editing tools.