The NLP Problem and Linguistic Structure

Natural Language Processing (NLP) is the subfield of computer science and artificial intelligence concerned with enabling computers to process, analyze, and generate human language — whether written text or transcribed speech. The word "natural" distinguishes human languages like English, Mandarin, or Swahili from formal languages such as programming languages, which are engineered to be unambiguous. NLP tasks span a spectrum: low-level tasks like splitting text into words, mid-level tasks like identifying the grammatical role of each word, and high-level tasks like answering a question or summarizing a document. What unifies all these tasks is that they require some model of linguistic structure — the systematic organization that language imposes on otherwise unstructured strings of symbols. Linguists traditionally decompose language into a hierarchy of levels, each studied by its own subdiscipline. Phonetics and phonology concern the sounds of speech and how they pattern into a language's sound system. Morphology studies how words are built from smaller meaningful units called morphemes (for example, "unhappiness" decomposes into un-, happy, -ness). Syntax governs how words combine into phrases and sentences according to grammatical rules. Semantics is the study of literal meaning — what words and sentences denote. Pragmatics studies meaning in context: what a speaker intends to convey given the situation, beyond the literal words. A related notion, discourse, concerns how sentences connect to each other across a text or conversation, including reference and coherence. These levels are usually presented in increasing order of context-dependence, from the physical signal (sound) to the social act (intention). The central engineering insight is that ambiguity compounds across levels. A speech signal may be consistent with multiple phoneme sequences; a word form may have multiple morphological analyses; a sentence may have multiple syntactic parses; a parse may support multiple semantic readings; and a sentence's pragmatic force may depend on who is speaking to whom. Classical NLP responded to this by building pipelines: a sequence of processing stages, each resolving ambiguity at one level before passing a cleaner representation to the next stage. This pipeline view is the historical backbone of the field and remains the clearest way to teach why NLP is hard, even as modern systems increasingly learn end-to-end representations that implicitly span several levels at once.

There is no single "algorithm" for NLP as a whole; rather, the field is organized as a layered pipeline of interpretation, where each stage takes a representation from the previous stage and refines it using level-specific tools. Below is the classical pipeline architecture, presented as pseudocode that any concrete NLP system — from a 1990s tagger to a modern chatbot's preprocessing stage — can be seen as instantiating. ``` function CLASSICAL_NLP_PIPELINE(input_signal):

# Stage 0: Acoustic / orthographic input if input_signal is speech: phonemes = PHONETIC_ANALYSIS(input_signal) # sound -> phoneme sequence text = PHONOLOGICAL_DECODE(phonemes) # phoneme sequence -> word hypotheses else: text = input_signal # already written text

# Stage 1: Tokenization (segment text into words/punctuation) tokens = TOKENIZE(text)

# Stage 2: Morphological analysis (decompose words into morphemes, tags) morph_analyses = [] for token in tokens: morph_analyses.append(ANALYZE_MORPHOLOGY(token)) # e.g. "running" -> run + -ing (VERB, GER)

# Stage 3: Syntactic analysis (assign part-of-speech, build parse tree) pos_tags = TAG_PARTS_OF_SPEECH(tokens, morph_analyses) parse_tree = PARSE(tokens, pos_tags) # resolve structural ambiguity

# Stage 4: Semantic analysis (map structure to meaning representation) logical_form = SEMANTIC_INTERPRET(parse_tree) # resolve word-sense, compose meaning

# Stage 5: Discourse and coreference (link across sentences) discourse_repr = RESOLVE_COREFERENCE(logical_form, prior_context)

# Stage 6: Pragmatic interpretation (infer speaker intent, given context) intent = INFER_PRAGMATICS(discourse_repr, situational_context) return intent ``` Each stage in this pipeline exists precisely because a level of linguistic structure introduces a specific ambiguity that must be resolved before the next stage can operate reliably.

Step 1 — Tokenization. Raw text is split into words, punctuation, and other units. Even this first step is nontrivial: "don't" may become one token or two ("do" + "n't"); "New York" may be one unit or two words; a period may end a sentence or mark an abbreviation ("Dr."). This step is elaborated in the article on Text Preprocessing and Tokenization.

Step 2 — Morphological analysis. Each token is decomposed into a stem (or lemma) and affixes, and tagged with grammatical features such as tense, number, or case. "Ran" is analyzed as the past tense of "run"; "geese" as the plural of "goose." Languages differ enormously in how much information morphology carries — Turkish and Finnish pack many grammatical features into a single word, while English relies more on separate function words. This step feeds into Morphology and Stemming.

Step 3 — Syntactic analysis. Part-of-speech tags are assigned (noun, verb, adjective, ...), and a parser builds a tree representing how words group into phrases and how phrases relate (subject, object, modifier). Syntax resolves structural ambiguity: "I saw the man with the telescope" can attach "with the telescope" to "saw" (I used a telescope) or to "the man" (the man had a telescope). A parser must choose — or represent both — analyses.

Step 4 — Semantic analysis. The syntactic tree is mapped onto a meaning representation: who did what to whom, what entities are referenced, what logical relations hold. This step resolves lexical ambiguity (word senses: "bank" as a financial institution versus a riverbank) and composes word meanings according to sentence structure.

Step 5 — Discourse and coreference. Sentences are linked across a passage. Pronouns and definite descriptions are resolved to their antecedents: in "Maria took her badge to the office. She showed it to the guard," a discourse module infers that "she" is Maria and "it" is the badge.

Step 6 — Pragmatics. Finally, the system infers what the speaker actually means given context, tone, or convention. "Can you pass the salt?" is syntactically a yes/no question, but pragmatically a request for action. This is the level at which sarcasm, indirect speech acts, and implicature live. The following figure lays out this pipeline as a layered architecture, showing how ambiguity is introduced and progressively narrowed at each stage.

Because "NLP" names a problem area rather than a single algorithm, complexity must be discussed per stage, and correctness must be discussed as a modeling claim rather than a proof in the traditional algorithmic sense.

Tokenization. A simple whitespace/punctuation tokenizer is a single linear scan: $O(n)$ time and $O(n)$ space for a string of length $n$, since each character is visited a constant number of times and each token is stored once. Rule-based tokenizers using regular expressions preserve this linear bound as long as the regular expressions are compiled into finite automata (matching is linear in input length for a fixed-size automaton).

Morphological analysis. Dictionary-lookup morphological analyzers run in $O(1)$ expected time per word given a hash-table lexicon, so $O(n)$ overall for $n$ words. Rule-based analyzers using finite-state transducers (composing phonological and morphological rules) also run in time linear in word length, because finite-state transducers process input symbol by symbol with bounded states — a consequence of the Kleene/Myhill–Nerode theory underlying finite automata: any regular relation can be recognized in time proportional to input length.

Syntactic parsing. This is where complexity becomes serious. Context-free parsing with the CYK algorithm runs in $O(n^3 |G|)$ time and $O(n^2)$ space for a sentence of $n$ words and grammar size $|G|$, because CYK fills a triangular chart of $O(n^2)$ spans, each requiring $O(n)$ work to consider all split points, combined with grammar rule lookups. This cubic bound is a worst-case guarantee: it holds regardless of how ambiguous the sentence is, because the chart-based dynamic program shares subcomputations across all parses (the same insight that makes edit-distance and other DP algorithms sub-exponential despite exponentially many possible solutions). Without dynamic programming, naively enumerating all parse trees of an ambiguous sentence takes time exponential in $n$, since the number of binary bracketings of $n$ items grows as the Catalan numbers, $C_{n-1} = \binom{2n-2}{n-1}/n$.

Semantic and pragmatic interpretation. These stages are not generally decidable to "solve" in a formal sense, because pragmatic inference depends on open-ended world knowledge and speaker intention, which cannot be fully enumerated. Classical systems bound this by restricting to narrow domains (e.g., a fixed set of intents in a dialogue system), reducing an otherwise unbounded inference problem to a finite classification problem solvable in time linear in the size of a fixed intent inventory.

Correctness — what "correct" even means here. Unlike sorting or shortest paths, there is rarely a unique correct output for an NLP task, because human language licenses genuine ambiguity that even people resolve differently. The appropriate correctness criterion is therefore agreement with human judgment, operationalized via:

• Coverage: does the pipeline produce some analysis for every valid input? (An analyzer with a closed lexicon fails to reach 100% coverage on new words — the classical out-of-vocabulary problem.)
• Precision/Recall against a gold standard: does the system's chosen analysis match a linguist-annotated corpus?
• Inter-annotator agreement as an upper bound: since even expert human annotators disagree on parses or word senses some fraction of the time (agreement rates well below 100% are typical for hard semantic tasks), no algorithm can be "more correct" than the ambiguity intrinsic to the data — this is the theoretical ceiling on achievable accuracy, often called the Bayes error of the task.

This reframes the "proof of correctness" question: a pipeline stage is correct not in the sense of matching a mathematical specification, but in the sense that its error rate approaches the irreducible disagreement rate among competent human speakers. This is a genuinely different notion of correctness from classical algorithms, and it is the reason NLP historically moved from hand-written rules (which are brittle against real language variation) toward statistical and later learned models (which fit the empirical distribution of human-produced language).

Tradeoffs. Pipelines have the advantage that each stage is inspectable and errors are localizable — you can look at the parse tree and see the parser was wrong. Their disadvantage is error propagation: a mistake at the morphology stage compounds through syntax, semantics, and pragmatics, and there is no mechanism for a later stage's evidence to correct an earlier stage's mistake. This is one of the central motivations for later end-to-end and joint models that let signal flow both ways across levels, at the cost of interpretability.

Consider the sentence: > "The old man the boats." This is a classic linguistic garden-path sentence — a sentence that is grammatically valid but leads most readers to an incorrect first parse. Tracing it through the pipeline exposes exactly where and why each linguistic level matters.

The trace shows precisely why NLP is hard even for a single, short, fully grammatical sentence: the most frequent part-of-speech tag for "man" is noun, so any tagger relying on unigram frequency alone will mis-tag it, causing the syntactic parser to fail or mis-parse, which in turn produces an incoherent semantic representation. Only a model that considers the whole-sentence context — that "the boats" needs a verb before it, and no other verb candidate exists — recovers the correct analysis. This is exactly the kind of cross-level interaction (morphology feeding syntax, syntax constraining word-sense choice) that motivated statistical part-of-speech tagging and parsing using sequence models, which weigh tag sequences rather than single-word frequencies. A second short example makes the semantic/pragmatic distinction concrete. Consider a customer support chatbot receiving: > "This is the third time my package hasn't arrived." Syntactically and semantically, this sentence is a simple factual statement. Pragmatically, in the context of a support chat, it functions as a complaint carrying an implicit request ("please fix this" or "please refund me") — an instance of an indirect speech act. A pipeline that stops at the semantic level will output a true-but-useless representation ("the package has not arrived, and this has happened three times"); only pragmatic inference, conditioned on the discourse context (a support chat), recovers the actionable intent. This is why production dialogue systems add an explicit intent-classification or dialogue-act stage on top of syntactic and semantic parsing.

The recognition that language has distinct, analyzable levels predates computing by millennia, but the formalization relevant to NLP emerged through 20th-century linguistics and information theory converging with early computer science.

Every production NLP system, however modern, is still organized around the linguistic levels described here, even when a single neural network appears to "do it all." Search engines must tokenize and normalize morphological variants ("running" and "run") so that a query matches relevant documents. Machine translation systems must resolve syntactic ambiguity (which phrase attaches to which) before they can correctly reorder words across languages with different syntax. Speech assistants must resolve phonetic ambiguity ("recognize speech" versus "wreck a nice beach") using downstream syntactic and semantic context. Grammar-checking tools rely explicitly on morphological and syntactic analysis to flag subject-verb agreement errors. Customer-service chatbots depend on pragmatic/intent-level modeling to distinguish a literal statement from an implied request. Even large language models, which are trained without explicit linguistic-level supervision, are evaluated and debugged using this same vocabulary: researchers diagnose failures as "the model mis-resolved coreference" (a discourse-level failure) or "the model missed the sarcasm" (a pragmatic-level failure), because the levels remain the clearest diagnostic frame humans have for language understanding. Anyone building or evaluating an NLP system — from a spell-checker to a chat assistant — reasons in these terms, which is why this layered view remains foundational before studying Tokenization, Morphology, or statistical language modeling in depth.

Ask the tutor: How would this pipeline need to change for a language with no whitespace between words, like Chinese?