Natural Language Processing (AL-504 (B)) - Unit 3 Short Notes

UNIT 3: MORPHOLOGY AND FINITE-STATE AUTOMATA

This unit focuses on the internal structure of words (morphology) and the use of Finite-State Automata (FSA) as a computational model for analyzing and generating word forms.

3.1 Morphology: Concepts and Processes

Morphology is the study of the internal structure of words and the rules for forming new words.

• Morpheme: The smallest unit of meaning or grammatical function.

  • Example: un- (prefix), break (root), -s (suffix) in "unbreaks".

• Types of Morphological Processes:

  | Process | Definition | Example (English) | Relevance to Indian Languages | | :--- | :--- | :--- | :--- | | Inflection | Modifying a word to express grammatical categories (tense, number, case) without changing core meaning or part of speech. | cat → cats (plural) | Highly prevalent. Sanskrit has extensive case endings; Tamil uses suffixes for tense and person. | | Derivation | Creating a new word (often new part of speech) by adding affixes, altering core meaning. | happy (adj) → happiness (noun) | Common. Hindi: Sikh (learn) → Siksha (education). Often agglutinative. | | Agglutination | Stringing together morphemes, each representing a single, clear grammatical function. | Turkish: ev (house) + -ler (pl) + -im (my) = evlerim (my houses) | Key feature of many Indian languages (e.g., Telugu, Kannada, Malayalam). Morphemes are concatenated linearly. | | Compounding | Combining two or more free morphemes to form a new word. | sun + flower = sunflower | Very productive in Hindi (राजमार्ग - king+road = highway) and other languages. |

[!TIP] Exam Focus: Be prepared to differentiate inflection (same word, different form) from derivation (new word, often new category). For Indian languages, emphasize agglutination and provide a clear example from a language like Hindi, Tamil, or Telugu.

3.2 Finite-State Automata (FSA): Design and Application

Finite-State Automaton (FSA) or Finite-State Machine (FSM) is a computational model with a finite number of states and transitions between them based on input symbols. It is perfectly suited for morphology because word formation is a local, sequential process that can be modeled by a finite set of states and transitions.

Key Components of an FSA:

1. Finite set of states (Q): e.g., q0 (start), q1, q2 (accept).

2. Finite input alphabet (Σ): The set of characters/morphemes (e.g., {a, b, c, -s, -ed}).

3. Transition function (δ): Maps a (state, input symbol) pair to a next state. δ(q, a) = q'.

4. Start state (q₀).

5. Set of accept/final states (F).

Design for Morphological Analysis:

An FSA can recognize valid word forms (analysis) or generate all possible forms from a root (generation).

Example: Simple English Plural FSA (Analysis)

[[DIAGRAM: CANVAS: A simple 3-state FSA.

- Start state: q0 (double circle, final)

- State q1 (single circle)

- Accept state: q2 (double circle)

Transitions:

q0 --'s'--> q1

q0 --'es'--> q1

q1 --'s'--> q2

q1 --'es'--> q2

]]

• Function: Accepts strings like cat+s (cats), box+es (boxes). The FSA encodes the rule: after certain stems (ending in sibilant), use -es; otherwise, use -s.

• States represent stages in the word formation process.

Application to Indian Languages (Agglutinative):

FSAs are extremely effective for languages like Tamil, Telugu, or Kannada.

• A single FSA can be built with states representing the root and sequential transitions for each suffix (tense, aspect, person, case).

• Example for a Tamil verb root வா (vā - come):

  • q0 (root) --'க'--> q1 (past) --'ஆன்'--> q2 (3rd masc sg past) = வாங்க` (vāṅkaṇ - he came).

  • The linear, concatenative nature maps directly to FSA state transitions.

[!TIP] Exam Focus: You must be able to draw a simple FSA for a basic morphological process (like English plural or past tense). More importantly, explain why FSA is suitable for morphology: finite state nature, local dependencies, efficiency for pattern matching/generation. For Indian languages, explicitly state that agglutination makes FSA a natural fit.

3.3 Relationship between Morphology and Finite-State Automata

This is a highly frequent exam question (seen in Nov 2022, Dec 2024).

• Morphology provides the linguistic phenomena: The rules of inflection, derivation, and agglutination that define how words are built from morphemes.

• FSA provides the computational formalism: A precise, executable model to implement those morphological rules.

• The Connection:

  1. Modeling Regularity: Morphological processes in natural languages are largely regular (rule-governed). FSAs excel at modeling regular, local patterns.

  2. Efficiency: An FSA can recognize or generate all valid word forms of a lexicon in linear time relative to the word length. This is crucial for spell-checkers, morphological analyzers, and machine translation systems.

  3. Implementation: A lexicon of roots can be combined with a single, large FSA encoding all affixation rules. This is more efficient than storing every inflected form.

  4. Handling Ambiguity: A single word form (e.g., walks) might correspond to multiple analyses (verb 3rd sg present or noun plural). An FSA can be designed to have multiple paths to final states, representing this ambiguity, which downstream components (like POS taggers) can resolve.

In essence: Morphology defines what needs to be computed (the word formation rules). FSA defines how to compute it efficiently (the state machine that traverses morphemes).

Summary for Revision

Final Formula/Concept to Box:

\boxed{\text{FSA efficiently models the finite-state nature of regular morphological processes, especially agglutination in Indian languages.}}