Natural Language Processing - Context-Free Grammars and Predicate

 

Constituency in English

Constituency refers to the way words group together in a sentence to form units or "constituents" that act as a single unit in a sentence. One of the most common constituents in English is the Noun Phrase (NP), which is a group of words centered around at least one noun. Examples of noun phrases include:

• three parties from Brooklyn
• a high-class spot such as Mindy’s
• the Broadway coppers
• they
• Harry the Horse
• the reason he comes into the Hot Box

Evidence for Constituency

How can we tell that words form groups like these? There are several types of evidence:

1. Syntactic Environment: Noun phrases can all appear in similar positions in a sentence, such as before a verb. For example:

   • three parties from Brooklyn arrive...
   • a high-class spot such as Mindy’s attracts...
   • the Broadway coppers love...
   • they sit...

   However, not all individual words in a noun phrase can appear in these positions. For example:

   • from arrive... (incorrect)
   • as attracts... (incorrect)
   • the is... (incorrect)
   • spot is... (incorrect)

   This shows that it's the entire noun phrase, not individual words, that can occur in these syntactic environments.

2. Preposed and Postposed Constructions: Constituents can be moved as a whole to different positions in a sentence. For example, the prepositional phrase "on September seventeenth" can appear in various positions in the sentence:

   • On September seventeenth, I’d like to fly from Atlanta to Denver.
   • I’d like to fly on September seventeenth from Atlanta to Denver.
   • I’d like to fly from Atlanta to Denver on September seventeenth.

   However, the individual words within the phrase cannot be moved independently:

   • On September, I’d like to fly seventeenth from Atlanta to Denver (incorrect)
   • On I’d like to fly September seventeenth from Atlanta to Denver (incorrect)
   • I’d like to fly on September from Atlanta to Denver seventeenth (incorrect)

These examples demonstrate that groups of words, like prepositional phrases and noun phrases, behave as units in sentences. This is key evidence for the concept of constituency in syntax, where certain word groupings act as a single component in sentence structure.

Recursive Structures

Further evidence for constituency comes from the ability of certain constituents to embed within themselves, a concept known as recursion. This is why models like context-free grammars are effective at capturing the structure of language, as they can represent these recursive relationships between constituents.

Context-Free Rules and Trees

A Context-Free Grammar (CFG) is a formalism used to describe the constituent structure of natural languages, widely used in natural language processing (NLP). It is also known as Phrase-Structure Grammar, Backus-Naur Form (BNF), or Generative Grammar.

Key Components of a CFG:

1. Non-Terminal Symbols (N): Represent abstract categories such as noun phrases (NP) or verb phrases (VP). These symbols appear on the left side of grammar rules and are further expanded.

2. Terminal Symbols (Σ): The actual words or tokens in the language, such as 'the', 'flight', etc. They appear at the bottom level of the grammar, derived from the lexicon.

3. Production Rules (P): Define how non-terminal symbols are expanded into a sequence of non-terminals and terminals. For example:

   • NP → Det Nominal
   • VP → Verb NP
   • Det → a
   • Noun → flight

4. Start Symbol (S): The initial non-terminal from which a CFG begins its derivation, typically representing a sentence.

Derivations and Parse Trees:

• Derivation: A step-by-step process of replacing non-terminal symbols with their expansions according to the grammar's production rules. For instance, starting with NP, we might apply rules to expand it into Det Nominal, then further to a flight.

• Parse Tree: A hierarchical structure representing the derivation of a sentence. Each branch in the tree corresponds to a production rule. For example, the phrase "a flight" can be visualized in a tree structure: 

  
  
  

• Grammatical vs. Ungrammatical Sentences:

  A CFG defines a formal language comprising strings that can be derived from the start symbol. Sentences that can be derived are termed grammatical, while those that cannot are ungrammatical. 

  Examples of CFG Rules:

  1. Sentence Structure:

     • S → NP VP
     • A sentence (S) consists of a noun phrase (NP) followed by a verb phrase (VP).

  2. Verb Phrases:

     • VP → Verb NP
     • VP → Verb NP PP
     • A verb phrase can consist of a verb followed by a noun phrase, or a noun phrase and a prepositional phrase (PP).

  3. Prepositional Phrases:

     • PP → Preposition NP
     • A prepositional phrase contains a preposition followed by a noun phrase.

  Bracketed Notation:

  Parse trees can also be represented in a compact, bracketed notation. For example, the sentence "I prefer a morning flight" is represented as:

• [S [NP [Pro I]] [VP [V prefer] [NP [Det a] [Nom [N morning] [N flight]]]]]

Formal Definition of CFG:

A CFG can be formally defined as a 4-tuple (N, Σ, P, S), where:

1. N: Non-terminal symbols.
2. Σ: Terminal symbols.
3. P: Production rules of the form A → α (where A is a non-terminal and α is a string of terminals and non-terminals).
4. S: Start symbol.

The language generated by the CFG is the set of terminal strings that can be derived from the start symbol S.

Sentence-Level Constructions 

In this section, we explore different sentence-level constructions used in English, particularly focusing on those relevant to the Air Travel Information System (ATIS) domain. These constructions are key to understanding different sentence forms in natural language processing (NLP), and they provide insights into how complex English sentences are modeled using context-free grammars (CFGs).

Key Sentence Structures:

1. Declarative Sentences:

   • Structure: Subject NP + Verb Phrase (VP)
   • These are the most common sentences, used for making statements. For example:
     • "I prefer a morning flight."
     • "The flight should be at eleven a.m. tomorrow."
   • Declarative sentences can have various purposes, including providing information, expressing preferences, or stating plans.

2. Imperative Sentences:

   • Structure: Verb Phrase (VP) (without a subject)

   • Used for commands or suggestions, typically in interactions with systems. For example:

     • "Show the lowest fare."
     • "List all flights from Burbank to Denver."

   • Imperative sentences often omit the subject but imply a command directed at the listener or system.

   • CFG Rule for Imperative Sentences:

     • S → VP

3. Yes-No Questions:

   • Structure: Auxiliary Verb + Subject NP + VP

   • Used to ask questions that can be answered with "yes" or "no." For example:

     • "Do any of these flights have stops?"
     • "Can you give me the same information for United?"

   • These questions often start with an auxiliary verb like "do," "does," or "can."

   • CFG Rule for Yes-No Questions:

     • S → Aux NP VP

4. Wh-Questions (Wh-Phrase Constructions):

   • These sentences begin with a wh-phrase (who, what, where, when, which, why, how), and there are two primary types:

   • Wh-Subject Question:

     • Structure: Wh-NP + VP
     • The wh-phrase acts as the subject of the sentence, similar to a declarative sentence structure. For example:
       • "What airlines fly from Burbank to Denver?"
       • "Which flights serve breakfast?"
     • CFG Rule for Wh-Subject Questions:
       • S → Wh-NP VP

   • Wh-Non-Subject Question:

     • Structure: Wh-NP + Auxiliary Verb + Subject NP + VP
     • The wh-phrase is not the subject, and the sentence includes an auxiliary verb before the subject. For example:
       • "What flights do you have from Burbank to Tacoma?"
     • CFG Rule for Wh-Non-Subject Questions:
       • S → Wh-NP Aux NP VP

Other Sentence-Level Constructions:

• Fronting:
• Involves placing a phrase at the beginning of the sentence for emphasis, topicalization, or focus. For example:
  • "On Tuesday, I’d like to fly from Detroit to Saint Petersburg."
• These structures are often used for discourse purposes and are not covered by simple CFG rules.

Coordination 

In this section, we explore the concept of coordination in natural language, which involves the conjoining of noun phrases, verb phrases, and sentences using conjunctions like and, or, and but. This mechanism allows for the combination of similar grammatical elements, providing more complex structures in sentences.

Key Concepts:

1. Conjunctions:

   • Words that join other words, phrases, or clauses. Common conjunctions include:
     • And: Indicates addition or inclusion.
     • Or: Indicates alternatives or choices.
     • But: Indicates contrast.

2. Coordinate Noun Phrases:

   • Two or more noun phrases (NPs) can be conjoined to form a coordinate noun phrase. The coordination can be represented using brackets to highlight the constituents.
   • Examples:
     • "Please repeat [NP [NP the flights] and [NP the costs]]."
     • "I need to know [NP [NP the aircraft] and [NP flight number]]."
     • "I would like to fly from Denver stopping in [NP [NP Pittsburgh] and [NP Atlanta]]."
   • CFG Rule for Coordinating Noun Phrases:
     • $NP \rightarrow NP \text{ and } NP$ (Rule 9.14)

3. Conjoining Other Phrase Types:

• Beyond noun phrases, other phrase types can also be coordinated, including verb phrases (VPs) and prepositional phrases (PPs).
• Examples:
  • "What flights do you have [VP [VP leaving Denver] and [VP arriving in San Francisco]]?"
  • "[S [S I’m interested in a flight from Dallas to Washington] and [S I’m also interested in going to Baltimore]]."
• CFG Rules for Coordination of Other Phrases:
• For verb phrases: $VP \rightarrow VP \text{ and } VP$ (Rule 9.15)
• For sentences: $S \rightarrow S \text{ and } S$ (Rule 9.16)

Agreement 

1. Inflectional Morphology:

   • English verbs can appear in different forms depending on the subject. Notably, the third-person singular (3sg) form typically adds an -s ending, while other forms do not.
   • Examples:
     • The flight does (3sg)
     • All the flights do (non-3sg)
     • I do (non-3sg)

2. Subject-Verb Agreement:

   • A verb must agree with its subject in number (singular/plural) and person (first, second, third). Sentences where the subject and verb do not agree are ungrammatical.
   • Examples of Grammatical Sentences:
     • "Does this flight stop in Dallas?"
     • "Do all of these flights offer first class service?"
   • Examples of Ungrammatical Sentences:
     • What flight leave in the morning?
     • Does you have a flight from Boston to Fort Worth?
     • Do this flight stop in Dallas?

3. Grammar Expansion for Agreement:

   • To handle agreement phenomena in grammar, we can create multiple sets of rules:
     • A rule for 3sg subjects: $S \rightarrow 3sgAux \ 3sgNP \ VP$
     • A rule for non-3sg subjects: $S \rightarrow Non3sgAux \ Non3sgNP \ VP$

4. Auxiliary Verbs:

   • Define auxiliary verbs based on the subject type:
     • 3sg Auxiliary: $3sgAux \rightarrow \text{does | has | can | ...}$
     • Non-3sg Auxiliary: $Non3sgAux \rightarrow \text{do | have | can | ...}$

5. Noun Phrase Rules:

   • Create rules for noun phrases distinguishing between singular and plural:
     • 3sg Noun Phrase:
       • $3sgNP \rightarrow (Det) (Card) (Ord) (Quant) (AP) SgNominal$
     • Non-3sg Noun Phrase:
       • $Non3sgNP \rightarrow (Det) (Card) (Ord) (Quant) (AP) PlNominal$

6. Noun Rules:

   • Singular Nouns:
     • $SgNominal \rightarrow SgNoun | SgNoun \ SgNoun$
   • Plural Nouns:
     • $PlNominal \rightarrow PlNoun | SgNoun \ PlNoun$

7. Examples of Nouns:

   • Singular Nouns:
     • flight, fare, dollar, reservation
   • Plural Nouns:
     • flights, fares, dollars, reservations

8. Challenges with Agreement:

   • This method of handling agreement can lead to a substantial increase in grammar size, as every rule referencing nouns or verbs requires both singular and plural versions.
   • Case Agreement:
     • In addition to number, English pronouns exhibit case distinction (e.g., nominative vs. accusative).
   • Gender Agreement in Other Languages:
     • Languages like German and French require gender agreement between nouns and their modifiers, complicating the grammar further.

9. Parameterization of Grammar:

• Chapter 11 will discuss a more efficient approach to manage agreement without exponentially increasing grammar complexity by using feature structures to parameterize nonterminal symbols.

The Verb Phrase and Subcategorization 

This section discusses the structure of the verb phrase (VP) in English and the concept of subcategorization, which refers to the compatibility of verbs with different types of complements.

Key Concepts:

1. Definition of Verb Phrase (VP):

   • A verb phrase consists of a verb and its constituents, which can include noun phrases (NPs), prepositional phrases (PPs), and more complex structures such as sentential complements.
   • Simple Rules:
     • $VP \rightarrow \text{Verb}$
     • $VP \rightarrow \text{Verb NP}$
     • $VP \rightarrow \text{Verb NP PP}$
     • $VP \rightarrow \text{Verb PP}$

2. Sentential Complements:

   • Sentences can contain entire embedded sentences as complements of the verb, known as sentential complements.
   • Examples:
     • "You said there were two flights that were the cheapest."
     • "I think I would like to take the nine-thirty flight."
   • Rule for Sentential Complements:
     • $VP \rightarrow \text{Verb S}$

3. Infinitive Verb Phrases:

   • Certain verbs can take another VP as a complement, particularly those expressing desire or intention.
   • Examples:
     • "I want to fly from Milwaukee to Orlando."
     • "I’m trying to find a flight."
   • Rule:
     • $VP \rightarrow \text{Verb VP}$

4. Phrasal Verbs:

   • Verbs can also be followed by particles, forming phrasal verbs (e.g., "take off"). These particles are integrated into the verb's meaning.
   • Examples:
     • "The plane took off."

5. Subcategorization of Verbs:

   • Not all verbs can take the same types of complements. This leads to the concept of subcategorization, where verbs are classified based on the types of complements they can take.
   • Traditional Grammar:
     • Verbs are often divided into transitive verbs (which require a direct object) and intransitive verbs (which do not).
     • Examples:
       • Transitive: "I found a flight."
       • Intransitive: "I disappeared a flight."

6. Modern Subcategorization:

   • Modern grammars may have up to 100 subcategories based on different complement types.
   • Example Subcategorization Frames:
     • Frame | Verb | Example
       • $0/$ | eat, sleep | "I want to eat."
       • NP | prefer, find | "Find the flight from Pittsburgh to Boston."
       • NP NP | show, give | "Show me airlines with flights from Pittsburgh."
       • PP from | fly, travel | "I would like to fly from Boston to Philadelphia."
       • NP PP with | help, load | "Can you help me with a flight?"
       • VP to | prefer, want | "I would prefer to go by United Airlines."
       • VP brst | can, would | "I can go from Boston."
       • S | mean | "Does this mean AA has a hub in Boston?"

7. Predicate-Argument Structure:

   • The relationship between verbs and their complements can be conceptualized as predicates with arguments.
   • Examples:
     • FIND (I, A FLIGHT)
     • WANT (I, TO FLY)

8. Grammar Representation:

   • To represent the relation between verbs and their complements in a context-free grammar, we could create distinct subtypes of verbs for each complement type.
   • Example Representation:
     • $\text{Verb-with-NP-complement} \rightarrow \text{find | leave | repeat}$
     • $\text{Verb-with-S-complement} \rightarrow \text{think | believe | say}$
     • $\text{Verb-with-Inf-VP-complement} \rightarrow \text{want | try | need}$

9. Challenges:

• This approach can lead to an explosion in the number of rules, similar to the challenges faced in managing agreement features.
• A more efficient solution using feature structures will be discussed in Chapter 11, allowing for better management of subcategorization without overwhelming the grammar with rules.

Auxiliaries 

Auxiliaries (or helping verbs) assist the main verb and have specific syntactic constraints, representing a kind of subcategorization.

1. Types of Auxiliaries:

   • Modal Auxiliaries: can, could, may, might, must, will, would, shall, should.
     • Subcategorize for a VP with a bare stem verb (e.g., can go).
   • Perfect Auxiliary: have, followed by a past participle (e.g., have booked).
   • Progressive Auxiliary: be, followed by a gerund (e.g., am going).
   • Passive Auxiliary: be, followed by a past participle (e.g., was delayed).

2. Auxiliary Order: When multiple auxiliaries are present, they follow a specific order:

   • Modal < Perfect < Progressive < Passive
   • Example: could have been a contender.

3. Semantic Role: In passive constructions, the subject often represents the patient (the undergoer) rather than the agent.

   • Example: A catastrophe was prevented (compared to active: I prevented a catastrophe).

4. Grammar Rules for Auxiliaries: Create rules for each type of auxiliary based on their complement requirements.

Spoken Language Syntax: 

Spoken language grammar shares similarities with written English grammar but also has distinct features. In spoken contexts, we typically use the term utterance instead of sentence to refer to spoken units.

1. Transcription of Spoken Language:

   • Transcriptions often use symbols to represent speech elements:
     • Commas (,) indicate short pauses.
     • Periods (.) denote long pauses.
     • Square brackets ([uh]) represent non-verbal events (e.g., breaths, pauses).

2. Characteristics of Spoken Language:

   • Lexical Differences: Spoken English often contains a higher frequency of pronouns. For example, subjects in spoken sentences are frequently pronouns.
   • Short Fragments: Spoken sentences may consist of brief phrases or fragments (e.g., “one way” or “around four PM”), unlike the more complete sentences in written English.
   • Disfluencies: These include hesitations, false starts, repairs, and repetitions. For instance, a speaker might begin to say "one-way flights" and then correct themselves to say "one-way fares".

3. Prosody:

   • Definition: Prosody refers to the rhythm, stress patterns, and pitch contour of spoken utterances.
   • Components:
     • Pitch Contour: The rise and fall of the voice during speech.
     • Stress Pattern: The arrangement of stressed and unstressed syllables.
     • Rate of Speech: The speed at which the utterance is spoken.

4. Disfluencies Explained:

   • Types of Disfluencies:
     • Filled Pauses: Words like "uh" and "um", which can be treated as lexical items in speech recognition systems.
     • Repetitions: Repeating words or phrases during speech.
     • False Starts: Beginning to say something and then stopping to correct oneself.
   • Example of a Disfluency:
     • Does American airlines offer any one-way flights [uh] one-way fares for 160 dollars?
   • Terminology:
     • Reparandum: The original sequence of words before correction (e.g., "one-way flights").
     • Repair: The corrected sequence (e.g., "one-way fares").
     • Interruption Point: The location where the speaker switches from the original to the corrected form.

5. Interaction of Disfluencies and Structure:

• Disfluencies can often reflect the underlying constituent structure. For instance, repairs may have the same grammatical structure as the reparandum preceding the interruption point.
• This relationship helps in processing and understanding spoken language by allowing the identification of interruptions and possible corrections.

Grammar Equivalence and Normal Form

1. Formal Language and Grammar:

• A formal language is defined as a set of strings of words, potentially infinite.
• The concept of grammar equivalence is used to determine if two grammars generate the same set of strings, even if the rules differ.

2. Types of Grammar Equivalence:

• Weak Equivalence:
  • Two grammars are weakly equivalent if they generate the same set of strings but do not assign the same phrase structure to each sentence.
  • Example: Two grammars might both generate the string "I want a flight," but one may structure it as a Verb Phrase (VP) while another as a Sentence (S).
• Strong Equivalence:
  • Two grammars are strongly equivalent if they generate the same set of strings and assign the same phrase structure to each sentence.
  • Example: If two grammars both generate "I want a flight" and both assign it as a VP with identical structure, they are strongly equivalent.
  • The only difference allowed is the renaming of non-terminal symbols (e.g., renaming VP to Action).

3. Normal Form for Grammars:

• It is often useful to have grammars in a specific normal form, where the productions take on a standardized structure.

4. Chomsky Normal Form (CNF):

• Definition: A context-free grammar is in Chomsky normal form (CNF) if it satisfies the following conditions:
  • It is ε-free (no rules produce the empty string ε).
  • Each production is of one of the following two forms:
    • A → BC: Two non-terminal symbols.
    • A → a: One terminal symbol.
• Example of a CNF rule:
  • If the rule is A → B C D, it can be converted to CNF in two steps:
    • A → B X
    • X → C D
• Use of CNF:
  • CNF is particularly useful in certain algorithms, such as parsing and binary tree structures, where rules have two non-terminals or one terminal.

5. Conversion to Chomsky Normal Form:

• Any context-free grammar can be converted into a weakly equivalent grammar in Chomsky normal form.
• This means that while the structure might change (weak equivalence), the grammar will still generate the same set of strings.

Finite State and Context-Free Grammars

1. Overview:

• A robust model of grammar must handle both constituency (grouping of words) and recursion (repeated use of the same structure within itself).
• Finite-state models of grammar (like finite-state automata, FSA) are often inadequate to represent all the complexities of natural language grammar due to their inability to fully support recursion.

2. Finite-State Grammar and Regular Expressions:

• A finite-state grammar can be modeled using regular expressions, which describe patterns in sequences of words.
• For example, a simple noun phrase (NP) can be represented as:
  • (Det) (Card) (Ord) (Quant) (AP) Nominal
    • This expression allows optional Determiners (Det), Cardinals (Card), Ordinals (Ord), Quantifiers (Quant), Adjective Phrases (AP), and ends with the Nominal (the main noun or noun phrase).

3. Adding Postmodifiers to Finite-State Grammar:

• To model more complex structures like postmodifiers (e.g., prepositional phrases), the regular expression can be expanded:
  • (Det) (Card) (Ord) (Quant) (AP) Nominal (PP)*
  • Here, PP* means zero or more Prepositional Phrases (PP) can be added.
• The issue arises when recursive structures like noun phrases inside prepositional phrases are introduced.

4. Recursion in Grammar:

• Recursion occurs when a non-terminal symbol expands to include itself, leading to potentially infinite structures.
• An example of a recursive rule is:
  • Nominal → Nominal PP
  • This rule says a Nominal can be followed by a Prepositional Phrase (PP), but a PP can also contain another NP, making it a recursive structure.

5. Problem of Recursion in Finite-State Grammars:

• Finite-state automata (FSA) struggle with recursion because they lack the memory needed to handle recursive structures effectively.
• Expanding a recursive NP rule results in a structure that keeps repeating itself:
  • (Det) (Card) (Ord) (Quant) (AP) Nominal (P (Det) (Card) (Ord) (Quant) (AP) Nominal (P NP))*
• This loop makes it difficult for finite-state grammars to represent all recursive structures found in English, especially for more complex cases like Relative Clauses, Gerund Phrases, etc.

6. Chomsky’s Proof on Context-Free Grammars:

• Chomsky (1959) proved that a finite-state automaton can generate a context-free language only if there is no center-embedded recursion (recursion of the form A → α A β).
• Center-embedded recursion is common in natural language (e.g., "The book that the man who I met bought"), and finite-state grammars cannot handle such structures well.

7. Finite-State Approximations of Context-Free Grammars:

• While finite-state grammars cannot fully represent all recursive structures, they can approximate context-free grammars by limiting recursion.
• Algorithms like those proposed by Pereira and Wright (1997) can automatically generate finite-state grammars that approximate more complex context-free grammars by limiting certain recursive elements.

8. Recursive Transition Networks (RTN):

• Recursive Transition Networks (RTNs) extend the power of finite-state automata by allowing recursion.
• RTNs are isomorphic to context-free grammars and can represent recursive structures, making them a useful tool for studying context-free grammars.

Grammars and Human Processing

1. Introduction:

• One of the key questions in linguistics is whether humans use context-free grammars (CFGs) in processing language.
• Various experiments have tried to prove that people mentally process language using syntactic constituents (structures like noun phrases and verb phrases), but clear evidence has been difficult to obtain.

2. Early Experiments on Constituency:

• Levelt (1970) conducted experiments where subjects were asked to judge which words in a sentence were closely connected. The results suggested that people intuitively grouped words into syntactic constituents.
• Fodor and Bever (1965) conducted experiments with auditory comprehension. Subjects heard sentences while also hearing clicks at different points in the sentence. The results suggested that people often misperceived clicks to occur at constituent boundaries, implying that constituents act as perceptual units.

3. Methodological Challenges:

• A major challenge with early experiments was that constituents are often both syntactic and semantic units.
  • For instance, a noun phrase (NP) like "a single odd block" is a syntactic unit but also a semantic unit (it refers to a specific object).
• Therefore, experiments showing people detect constituent boundaries might be measuring semantic facts, not just syntactic ones.
• This raises the need for experiments that prove the existence of constituents as syntactic units independent of semantics.

4. Evidence for Constituency (Bock and Loebell’s Experiments):

• Bock and Loebell (1990) used experiments to provide evidence for constituency in human language processing by avoiding the pitfalls of earlier studies.
• Their experiment relied on syntactic priming, a method where the use of a particular syntactic structure makes its later use more likely.
  • Example: If a subject hears or uses a verb phrase (VP) like "V NP PP" (e.g., "The boy gave the apple to the teacher"), they are more likely to use that same structure in subsequent sentences.
• The experiment focused on the ditransitive alternation in English:
  • Ditransitive sentence (V NP NP): "The wealthy widow gave [NP the church] [NP her Mercedes]."
  • Prepositional dative sentence (V NP PP): "The wealthy widow gave [NP her Mercedes] [PP to the church]."
• The key innovation in their experiment was that the priming sentences had similar syntactic structures but different meanings. For example:
  • Priming sentence: "IBM moved [NP a bigger computer] [PP to the Sears store]." (This is a prepositional locative but has the same structure as a prepositional dative).
• Results: Subjects primed with V NP PP structures were more likely to describe pictures using the V NP PP structure, even though the priming sentence had different semantics. This demonstrated that subjects were primed by the syntactic structure, not the meaning.

5. Constituency as a Mental Representation:

• Bock and Loebell’s findings suggest that constituents (like verb phrases or noun phrases) are mentally represented in the brain. These constituents can be primed or activated, influencing the production of future sentences.
• The use of a specific syntactic structure (like V NP PP) in one sentence makes it easier to use the same structure in a subsequent sentence, indicating that these structures are mentally stored.

6. The Debate on Human Use of Context-Free Grammars:

• There is disagreement among researchers about whether natural language can be fully described by context-free grammars (CFGs).
• Modularist View:
  • Supporters argue that human syntactic knowledge is a distinct module of the mind, separate from other cognitive functions.
  • According to this view, natural language can be modeled using formal rules like context-free grammar productions, and syntactic structure is independent of meaning or other factors.
• Anti-Modularist View:
  • This position argues that human language processing involves not only syntax but also other factors like semantics, pragmatics, intonation, and social context.
  • The anti-modularists believe that syntactic processing cannot be separated from these other influences, making it impossible to fully describe natural language using context-free grammars alone.
• This debate continues, with each side bringing forward different kinds of experimental evidence to support their view.

The Earley Algorithm

The Earley algorithm is a chart parsing algorithm used for parsing sentences in natural language processing. It is particularly effective for parsing sentences that conform to context-free grammars (CFGs). Unlike some other parsing methods, the Earley algorithm can handle both left-recursive and ambiguous grammars, making it versatile for various syntactic structures.

Key Components of the Earley Algorithm:

The Earley algorithm operates through a dynamic programming approach that consists of three key operations:

1. Prediction: Expand non-terminal symbols based on the grammar rules.
2. Scanning: Match terminals from the input string to the grammar rules.
3. Completion: Combine completed sub-structures (partial parses) to form larger structures.

Steps of the Earley Algorithm:

The algorithm uses a chart, which is a data structure that records parsing progress at each position in the input sentence. The process involves iterating over the input sentence, one word at a time. At each word, a set of Earley states (records) is maintained, which represent partial parses.

Each state is represented as a tuple:

$$(A \rightarrow \alpha \cdot \beta, i)$$

Where:

• A is a non-terminal.
• \alpha is the part of the production rule that has already been processed.
• \beta is the part that still needs to be processed.
• The dot (·) represents the position in the rule being processed.
• i represents the starting position in the input where the rule was first predicted.

Initialization:

• The algorithm begins with the start symbol of the grammar, typically S.
• It predicts the possible expansions of S and records these in the chart for position 0.

1. Prediction:

If a state has a non-terminal to the right of the dot (like A → α · B β), the algorithm predicts all possible expansions of B. These are added to the current chart.

Example: Let’s assume we are parsing the sentence ab with a simple grammar:

S → A B

A → a

B → b

At position 0, the algorithm predicts the possible expansions of S:

(S → · A B, 0)

(A → · a, 0)

(B → · b, 0)

2. Scanning:

If the next symbol after the dot is a terminal (like A → α · a β), and the current word in the input matches that terminal, the algorithm moves the dot over the terminal and moves to the next word.

For our example, at position 1, if the word a is encountered, we scan it and move the dot:

(A → a · , 0)

This indicates that the non-terminal A has been completely parsed.

3. Completion:

If a state has the dot at the end of a rule (like A → α · , i), it means that the non-terminal on the left-hand side (in this case A) has been successfully parsed. The algorithm then goes back to the state where this non-terminal was predicted and moves the dot over the completed non-terminal.

For example: At position 1, after completing A → a ·:

(S → A · B, 0)

At position 2, we can scan the terminal b to complete B:

(B → b · , 1)

Finally, the algorithm completes the parse:

(S → A B · , 0)

This shows that the sentence has been successfully parsed as a valid instance of the grammar.

Example of Parsing:

Consider the grammar:

S → NP VP

NP → Det N

VP → V NP

Det → the

N → dog

V → sees

And the sentence: "the dog sees the dog"

Chart Initialization (position 0):

(S → · NP VP, 0)

(NP → · Det N, 0)

(Det → · the, 0)

1. Prediction: Start by predicting all rules that begin with S, NP, and Det at position 0.
2. Scanning: Match the word "the" from the input to Det, resulting in:

(Det → the · , 0)

(NP → Det · N, 0)

3. Completion: Once Det is complete, predict possible N expansions

4. Continue this process for all words in the sentence, scanning and completing until the final parse is achieved. 

Earley Algorithm Characteristics:

• Efficiency: The algorithm runs in O(n³) time in the worst case for general CFGs but is more efficient for certain classes of grammars, running in O(n²) or even O(n) for unambiguous or regular grammars.
• Handling Left Recursion: The Earley algorithm can handle grammars with left recursion, unlike simpler top-down parsers that struggle with these cases.
• Ambiguity: The Earley algorithm can process ambiguous grammars, meaning grammars that allow multiple parse trees for the same input string.

Advantages:

• It is capable of parsing any context-free grammar.
• It supports real-time parsing, making it suitable for interactive systems like speech recognition or dialogue systems.
• The algorithm works well for parsing incomplete or ambiguous input.

Finite-State Parsing Methods

Finite-state parsing methods are based on finite-state automata (FSA), which are computational models used to recognize patterns in strings. In natural language processing (NLP), finite-state methods are used to parse simpler sentence structures that do not require recursive patterns or deep syntactic relations. While finite-state models are less expressive than context-free grammars (CFGs), they are computationally efficient and can be useful for certain linguistic tasks.

Overview of Finite-State Parsing:

Finite-state parsing methods use finite-state automata to recognize grammatical patterns in a string by moving through a set of states based on input symbols. These states represent grammatical categories, and transitions between states represent possible ways that categories combine in a sentence. Unlike CFGs, finite-state parsers are not powerful enough to handle deep recursion or nested structures, but they can be used effectively for simpler tasks like part-of-speech tagging, chunking, and certain types of phrase recognition.

Finite-State Automata (FSA):

An FSA is a machine with a finite number of states, transitions between states, and a start state and accept states. The machine reads input symbols (words or tokens) and transitions between states according to a defined set of rules (transitions).

• Start state: The initial state where the automaton begins.
• Transitions: Rules that define how the automaton moves from one state to another based on input.
• Accept states: If the automaton ends in an accept state after processing the entire input, the input is considered valid according to the grammar.

Components of Finite-State Parsing:

1. States: Represent grammatical categories or partial parses (e.g., noun phrases, verb phrases).
2. Transitions: Define how words or symbols move the parser from one state to another.
3. Final/Accepting States: Indicate the successful parsing of the input.

Key Characteristics:

• Non-recursive: Finite-state methods do not handle recursion, meaning they struggle with deeply nested structures (e.g., sentences within sentences).
• Efficiency: Finite-state methods are computationally efficient, making them suitable for real-time parsing tasks.
• Ambiguity Handling: Finite-state parsers are generally not equipped to handle syntactic ambiguity (multiple valid parses for the same input), which is a limitation compared to more powerful parsers like CFG-based parsers.

Finite-State Parsing for Specific Tasks:

1. Part-of-Speech Tagging:

   • In part-of-speech (POS) tagging, each word in a sentence is assigned a grammatical category (e.g., noun, verb, adjective).
   • A finite-state machine can be designed to transition through different grammatical categories based on the input words and their context.
   • For example, after reading a determiner (the), the automaton may transition to expect a noun (dog).

   Example: Given the sentence: "The dog runs."

   • States: START → DET → NOUN → VERB
   • Transitions:
     • START → DET (the)
     • DET → NOUN (dog)
     • NOUN → VERB (runs)
   • The automaton successfully accepts the sentence as grammatically valid.

2. Chunking:

   • Chunking (also known as shallow parsing) is the process of identifying and segmenting syntactic constituents such as noun phrases (NPs) or verb phrases (VPs) without performing full syntactic parsing.
   • Finite-state machines can be used to recognize chunks in sentences. For example, the automaton can transition through noun and verb phrase structures based on word sequences.

   Example: In the sentence: "The quick brown fox jumps."

   • The finite-state parser can identify chunks like [NP The quick brown fox] [VP jumps].

3. Named Entity Recognition (NER):

   • Finite-state methods are often employed in Named Entity Recognition (NER) to identify named entities such as persons, locations, or organizations in a text.
   • The FSA is trained to recognize patterns that correspond to named entities and transition through states as it processes each word in a sentence.

   Example: Given the sentence: "John Smith visited Paris."

   • States: START → PERSON → O → LOCATION
   • Transitions:
     • START → PERSON (John)
     • PERSON → PERSON (Smith)
     • PERSON → O (visited)
     • O → LOCATION (Paris)
   • The FSA successfully identifies "John Smith" as a person and "Paris" as a location.

Challenges and Limitations of Finite-State Parsing:

1. Lack of Recursion:

   • Finite-state parsers cannot handle recursive structures such as center-embedded sentences or nested noun phrases, which are common in human languages. For example, sentences like "The cat that the dog chased ran away" cannot be fully parsed using finite-state methods because they involve nested phrases.

2. Limited Expressiveness:

   • Finite-state methods lack the expressive power of context-free grammars or context-sensitive grammars and are not able to represent all possible sentence structures in natural language.

3. Ambiguity:

   • Handling syntactic ambiguity (where a sentence can be parsed in multiple ways) is difficult with finite-state methods. For example, in the sentence "I saw the man with the telescope," there are multiple possible interpretations that finite-state parsing cannot handle well.

Finite-State Approximation:

Despite their limitations, finite-state parsing methods are sometimes used to approximate more complex grammars. For example, by expanding only a certain number of noun phrases (NPs) or by ignoring deeply nested structures, finite-state parsers can handle common sentence structures efficiently.

Algorithms for Finite-State Parsing:

Finite-state methods can be incorporated into larger parsing systems using regular expressions or finite-state transducers (FSTs). These can be used for simple parsing tasks or preprocessing in combination with more powerful parsers.

Example of Finite-State Parsing:

Let’s consider a simple sentence: "The big cat chased the mouse." A finite-state parser for this sentence might define states for:

• DET (determiner): the
• ADJ (adjective): big
• NOUN: cat, mouse
• VERB: chased

The finite-state transitions might look like this:

START → DET → ADJ → NOUN → VERB → DET → NOUN → END

1. Input: The parser starts in the START state.
2. Transition: On reading the, it transitions to the DET state.
3. Transition: On reading big, it moves to the ADJ state.
4. Transition: On reading cat, it transitions to the NOUN state, and so on.
5. Final State: If the parser successfully transitions to the END state after consuming all input, the sentence is considered grammatically valid.