The Handbook of Computational Linguistics and Natural Language Processing

Alexander Clark, Chris Fox, Shalom Lappin, Alexander Clark, Chris Fox, Shalom Lappin

• Publisher: Wiley-Blackwell
• Year: 2013
• Print ISBN: 9781118347188, 9781405155816
• eBook ISBN: 9781118448670
• Edition: 1
• Topic: Languages & Linguistics
• Subtopic: Linguistics
• Index: Languages & Linguistics

This comprehensive reference work provides an overview of the concepts, methodologies, and applications in computational linguistics and natural language processing (NLP).

• Features contributions by the top researchers in the field, reflecting the work that is driving the discipline forward
• Includes an introduction to the major theoretical issues in these fields, as well as the central engineering applications that the work has produced
• Presents the major developments in an accessible way, explaining the close connection between scientific understanding of the computational properties of natural language and the creation of effective language technologies
• Serves as an invaluable state-of-the-art reference source for computational linguists and software engineers developing NLP applications in industrial research and development labs of software companies

Part I Formal Foundations

1 Formal Language Theory

SHULY WINTNER

1 Introduction

This chapter provides a gentle introduction to formal language theory, aimed at readers with little background in formal systems. The motivation is natural language processing (NLP), and the presentation is geared towards NLP applications, with linguistically motivated examples, but without compromising mathematical rigor.

The text covers elementary formal language theory, including: regular languages and regular expressions; languages vs. computational machinery; finite state automata; regular relations and finite state transducers; context-free grammars and languages; the Chomsky hierarchy; weak and strong generative capacity; and mildly context-sensitive languages.

2 Basic Notions

Formal languages are defined with respect to a given alphabet, which is a finite set of symbols, each of which is called a letter. This notation does not mean, however, that elements of the alphabet must be “ordinary” letters; they can be any symbol, such as numbers, or digits, or words. It is customary to use ‘Σ’ to denote the alphabet. A finite sequence of letters is called a string, or a word. For simplicity, we usually forsake the traditional sequence notation in favor of a more straightforward representation of strings.

Example 1 (Strings). Let Σ = {0,1} be an alphabet. Then all binary numbers are strings over Σ. Instead of 〈0,1,1,0,1〉 we usually write 01101. If Σ ={a,b,c,d,...,y,z} is an alphabet, then cat, incredulous, and supercalifragilisticexpialidocious are strings, as are tac, qqq, and kjshdflkwjehr.

The length of a string ω is the number of letters in the sequence, and is denoted |ω|. The unique string of length 0 is called the empty string and is usually denoted ∈(but sometimes λ).

Let ω₁ =〈x₁, . . .,x_n〉and ω₂ =〈y₁,. . .,y_m〉be two strings over the same alphabet Σ. The concatenation of ω₁ and ω₂, denoted ω₁ ·ω₂, is the string 〈x₁,. . .,x_n,y₁,. . .,y_m〉. Note that the length of ω₁ ·ω₂is the sum of the lengths of ω₁and ω₂: | ω₁ ·ω₂| = |ω₁| +|ω₂|. When it is clear from the context, we sometimes omit the ‘·’ symbol when depicting concatenation.

Example 2 (Concatenation). Let Σ = {a,b,c,d,. . .,y,z} be an alphabet. Then master · mind = mastermind, mind · master = mindmaster, and master · master = mastermaster. Similarly, learn · s = learns, learn · ed= learned, and learn · ing= learning.

Notice that when the empty string ∈is concatenated with any string ω, the resulting string is ω. Formally, for every string ω, ω ·∈ =∈ ·ω =ω.

We define an exponent operator over strings in the following way: for every string ω, ω⁰ (read: ω raised to the power of zero) is defined as ∈. Then, for n >0, ωⁿ is defined as ω^n-1 ·ω. Informally, ωⁿ is obtained by concatenating ω with itself n times. In particular, ω¹ =ω.

Example 3 (Exponent). If ω = go, then ω⁰ =∈, ω¹ =ω =go, ω² =ω¹ ·ω =ω ·ω =gogo, ω³ =gogogo, and so on.

A few other notions that will be useful in the sequel: the reversal of a string ω is denoted ω^R and is obtained by writing ω in the reverse order. Thus, if ω =〈x ₁,x₂,. . .,x_n〉, ω^R =〈x_n,x_n-1,. . .,x₁〉.

Example 4 (Reversal). Let Σ = {a,b,c,d,...,y,z} be an alphabet. If ω is the string saw, then ω^R is the string was. If ω =madam, then ω^R =madam =ω. In this case we say that ω is a palindrome.

Given a string ω, a substring of ω is a sequence formed by taking contiguous symbols of ω in the order in which they occur in ω: ω_c is a substring of ω if and only if there exist (possibly empty) strings ω_l and ω_r such that ω =ω_{l ·}ω_c ·ω_r. Two special cases of substrings are prefix and suffix: if ω =ω_l ·ω_c ·ω_r then ω_lis a prefix of ω and ω_r is a suffix of ω. Note that every prefix and every suffix is a substring, but not every substring is a prefix or a suffix.

Example 5 (Substrings). Let Σ ={a,b,c,d,...,y,z} be an alphabet and ω =indistinguishable a string over Σ. Then ∈, in, indis, indistinguish, and indistinguishable are prefixes of ω, while ∈, e, able, distinguishable and indistinguishable are suffixes of ω. Substrings that are neither prefixes nor suffixes include distinguish, gui, and is.

Given an alphabet Σ, the set of all strings over Σ is denoted by Σ*(the reason for this notation will become clear presently). Notice that no matter what the Σ is, as long as it includes at least one symbol, Σ* is always infinite. A formal language over an alphabet Σ is any subset of Σ*. Since Σ*is always infinite, the number of formal languages over Σ is also infinite.

As the following example demonstrates, formal languages are quite unlike what one usually means when one uses the term “language” informally. They are essentially sets of strings of characters. Still, all natural languages are, at least superficially, such string sets. Higher-level notions, relating the strings to objects and actions in the world, are completely ignored by this view. While this is a rather radical idealization, it is a useful one.

Example 6 (Languages). Let Σ = {a,b,c,. . .,y,z}. Then Σ*is the set of all strings over the Latin alphabet. Any subset of this set is a language. In particular, the following are formal languages:

• Σ*;
• the set of strings consisting of consonants only;
• the set of strings consisting of vowels only;
• the set of strings each of which contains at least one vowel and at least one consonant;
• the set of palindromes: strings that read the same from right to left and from left to right;
• the set of strings whose length is less than 17 letters;
• the set of single-letter strings;
• the set {i, you, he, she, it, we, they};
• the set of words occurring in Joyce’s Ulysses (ignoring punctuation etc.);
• the empty set.

Note that the first five languages are infinite while the last five are finite.

We can now lift some of the string operations defined above to languages. If L is a language then the reversal of L, denoted L^R, is the language {ω | ω^R ∈ L}, that is, the set of reversed L-strings. Concatenation can also be lifted to languages: if L₁and L₂are languages, then L₁ · L₂is the language defined as {ω₁ · ω₂| ω₁∈ L₁ and ω₂ ∈ L₂}: the concatenation of two languages is the set of strings obtained by concatenating some word of the first language with some word of the second.

Example 7 (Language operations). Let L₁ = {i, you, he, she, it, we, they}...

Table of contents

• Cover
• Praise for The Handbook of Computational Linguistics and Natural Language Processing
• Series page
• Dedication
• Title page
• Copyright page
• List of Figures
• List of Tables
• Notes on Contributors
• Preface
• Introduction
• Part I: Formal Foundations
• Part II: Current Methods
• Part III: Domains of Application
• Part IV: Applications
• References
• Author Index
• Subject Index