26_Formal_Grammars_and_NLP

Loading views...

Formal Grammars and Natural Language Processing (NLP)

Natural Language Processing (NLP) is a subfield of Artificial Intelligence that focuses on the interaction between computers and human languages. A fundamental aspect of NLP is the use of Formal Grammars to model the underlying structure of sentences.

1. Fundamental Definitions

To understand how grammars work, we must first define the building blocks of any formal language:

Symbol: The smallest, indivisible unit of a language (e.g., a letter like 'a' or a word like "apple").
Alphabet ( $\Sigma$ or $V_T$ ): A finite, non-empty set of symbols. In NLP, this is often called the Vocabulary.
String: A finite sequence of symbols formed by concatenating elements from the alphabet.
Formal Language ( $L$ ): A set of strings governed by specific structural rules.

2. The Formal Definition of a Grammar ( $G$ )

A grammar $G$ provides the mathematical framework for generating all valid sentences in a language while excluding invalid ones. It is defined as a 4-tuple:

G = (V_N, V_T, S, P)

Components:

$V_N$ (Non-terminal Symbols): Variables used as placeholders for grammatical categories (e.g., $NP$ for Noun Phrase). They are replaced during the derivation process.
$V_T$ (Terminal Symbols): The actual words of the language that appear in final sentences (the alphabet).
$S$ (Start Symbol): The initial non-terminal ( $S \in V_N$ ) from which all derivations begin.
$P$ (Production Rules): Rules that dictate how symbols can be transformed. Written as $\alpha \to \beta$ .

[!NOTE] The language generated by a grammar $G$ is denoted as $L(G)$ , representing the set of all terminal strings derivationable from $S$ .

3. The Chomsky Hierarchy

Developed by Noam Chomsky in 1956, this hierarchy classifies grammars into four nested levels based on their generative power and the complexity of the machines required to recognize them.

3.1 Type 0: Unrestricted Grammar

Definition: These are the most general grammars with no restrictions on production rules. They can model any language that is computable by a Turing Machine.
Rule Form: $\alpha \to \beta$ (where $\alpha$ is a non-empty string of terminals and non-terminals).
Example: $aAb \to ba$

3.2 Type 1: Context-Sensitive Grammar (CSG)

Definition: A symbol can only be replaced by a string if it appears within a specific context. The length of the left-hand side is always less than or equal to the length of the right-hand side.
Rule Form: $\alpha A \gamma \to \alpha \beta \gamma$ (where $|\alpha A \gamma| \le |\alpha \beta \gamma|$ ).
Example Language: $\{a^n b^n c^n \mid n \ge 1\}$

3.3 Type 2: Context-Free Grammar (CFG)

Definition: Production rules depend only on a single non-terminal symbol, regardless of the surrounding context. These are essential for specifying the syntax of most programming languages and natural languages.
Rule Form: $A \to \gamma$ (where $A$ is a single non-terminal).
Example Language: $\{a^n b^n \mid n \ge 1\}$ (e.g., matching parentheses).

3.4 Type 3: Regular Grammar

Definition: The most restrictive grammar. It is used to describe finite state languages and is typically used for lexical analysis and pattern matching.
Rule Form: $A \to aB$ or $A \to a$ (Right-linear).
Example Language: $(a+b)^*$ (All strings composed of 'a' and 'b').

4. NLP Syntax Analysis

Syntax analysis (parsing) is the process of mapping a linear string of words into a structured representation that reflects its grammatical relationships.

4.1 Solving Techniques

1. Linear Technique (Sequential Generation)

This is a step-by-step process where the sentence is generated by systematically applying production rules. It is a one-dimensional, linear representation of the derivation process.

Example Derivation:

Start: $S$
Rule ( $S \to NP \ VP$ ): $NP \ VP$
Rule ( $NP \to Det \ N$ ): $Det \ N \ VP$
Rule ( $VP \to V$ ): $Det \ N \ V$
Lexicon Match: "The" $N \ V \to$ "The cat" $V \to$ "The cat sat."

2. Tree Technique (Parse Tree)

The tree technique provides a graphical, hierarchical representation of the sentence. It clearly shows the relationship between different parts of the sentence (e.g., how $Det$ and $N$ combine to form $NP$ ).

Parse Tree Example:

            [S]
          /     \
       [NP]     [VP]
      /    \      |
   [Det]   [N]   [V]
     |      |     |
   "The"  "cat" "sat"

Root Node: The Start symbol ( $S$ ).
Intermediate Nodes: Non-terminals (e.g., $NP, VP$ ).
Leaf Nodes: Terminal symbols (actual words).

4.2 Parsing Strategies

Parsing strategies determine the order in which we build these structures.

1. Top-Down Parsing (Goal-Driven)

Top-down parsing starts with the root symbol ( $S$ ) and attempts to expand it downwards to match the input words. It is a derivation-based linear process.

Example

Goal: $S$
Apply Rule ( $S \to NP \ VP$ ): $\Rightarrow NP \ VP$
Apply Rule ( $NP \to Det \ N$ ): $\Rightarrow (Det \ N) \ VP$
Match Token ("The"): $\Rightarrow \text{"The"} \ N \ VP$
Match Token ("cat"): $\Rightarrow \text{"The cat"} \ VP$
Apply Rule ( $VP \to V$ ): $\Rightarrow \text{"The cat"} \ (V)$
Match Token ("sat"): $\Rightarrow \text{"The cat sat."}$ (Success)

2. Bottom-Up Parsing (Data-Driven)

Bottom-up parsing starts with the actual words of the sentence and attempts to "reduce" them into higher-level non-terminals. It is a reduction-based linear process.

Example

Input: "The cat sat."
Assign Categories (Lexicon): $Det \ N \ V$
Apply Rule ( $NP \to Det \ N$ ): $(Det \ N) \ V \Rightarrow NP \ V$
Apply Rule ( $VP \to V$ ): $NP \ (V) \Rightarrow NP \ VP$
Apply Rule ( $S \to NP \ VP$ ): $(NP \ VP) \Rightarrow S$ (Success)

4.3 Summary Comparison

Strategy	Logic	Pros	Cons
Top-Down	$S \Rightarrow \text{Words}$	Efficient if the set of rules is small.	Can get stuck in infinite recursion with left-recursive rules.
Bottom-Up	$\text{Words} \Rightarrow S$	Handles all types of grammars; data-oriented.	Can be less efficient if many words have multiple grammatical roles.

5. Transition Networks

In computational linguistics, we use networks to represent these grammatical transitions visually and procedurally.

5.1 Recursive Transition Networks (RTN)

An RTN is a collection of finite-state transition networks that can "call" each other.

Example: The network for a Sentence ( $S$ ) might have a transition labeled $NP$ . When the parser reaches this, it pauses the $S$ network, executes the $NP$ network, and returns once finished.

Visual Transition Network:

      (Start) --- [NP] ---> (State 1) --- [VP] ---> ((Success))
                   |                       |
                   v                       v
            [Recursive Call]        [Recursive Call]
                 (NP)                    (VP)
                 /  \                    /  \
              [Det] [Noun]            [Verb] [NP?]

(Circles are states, square brackets are recursive transitions or categories)

5.2 Augmented Transition Networks (ATN)

ATNs are more powerful versions of RTNs. They include:

Registers: To store information (e.g., the "number" of the subject: singular vs. plural).
Conditions: To ensure agreement (e.g., "The cat sats" would be rejected because the singular subject doesn't match the plural verb form).

4. Levels of Knowledge in NLP

Understanding natural language requires knowledge at several levels:

Phonological: Knowledge of linguistic sounds and how they are formed.
Morphological: Knowledge of word formation and structure (e.g., prefixes, suffixes, roots).
Syntactic: Knowledge of how words are combined to form legal sentences (Grammar).
Semantic: Knowledge of the literal meanings of words and sentences.
Pragmatic: Knowledge of how language is used in different contexts and how context affects meaning.
World Knowledge: General knowledge about the world that helps resolve ambiguities.

5. General Approaches to NLP

There are three main categories of systems used for natural language processing:

1. Keyword and Pattern Matching

Strategy: Look for specific words or patterns and generate pre-defined responses (e.g., ELIZA).

2. Syntactic and Semantic Directed

Strategy: Use formal grammars and word meanings to parse and understand sentences.

3. Scenario-based (Scripts)

Strategy: Use Scripts to provide context and expectations (e.g., SAM).

6. Advanced Grammars in NLP

Standard context-free grammars often fail to capture the deeper meaning or functional aspects of language. Several advanced grammar models address this:

6.1 Transformational Generative Grammar

Proposed by Noam Chomsky, this model uses a series of rules to transform sentences from one form to another while maintaining the same meaning.

Surface Structure: The actual syntactic form of the sentence (e.g., active vs. passive voice).
Deep Structure: The underlying semantic meaning.
Goal: To map different surface structures (e.g., "Joe kissed Sue" and "Sue was kissed by Joe") to the same deep structure.

6.2 Case Grammars

Introduced by Charles Fillmore, case grammars focus on the semantic roles that noun phrases play with respect to the verb.

Cases: Agentive (instigator), Instrumental (object used), Objective (receiver), Dative (person affected), Locative (location).
Case Frame: A verb defines which cases are required or optional (e.g., "STRIKE" requires an Objective case and an optional Agentive).

6.3 Systemic Grammars

Developed by Michael Halliday, these grammars emphasize the function and purpose of language in social contexts.

Ideational Function: Relates to the content and activities described.
Interpersonal Function: Relates to the purpose (request, statement, query).
Textual Function: Relates to the coherence and continuity of the conversation.

6.4 Semantic Grammars

These grammars encode semantic information directly into the syntactic rules.

Instead of NP/VP, they use categories like <SHIP>, <ATTRIBUTE>, or <DESTINATION>.
Pros: Highly efficient for restricted domains (e.g., database queries like the LIFER system).
Cons: Very difficult to scale to general language.

← Previous Next →