# Category: Unit – Language Complexity

## Unit Overview – Language Complexity

David A. Tanzer, January 2021, in unit Language Complexity

How complex is the English language? That’s a tough nut to crack! Here we’ll reframe the question in a more formal setting which is shared by computer science and linguistics: the theory of formal languages and their complexity. By the end, we’ll reach a technical understanding of what is meant by the famous conjecture P != NP.

## Language Complexity, Part 1

David A. Tanzer, January 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

A simple view of languages

How complex is the English language? The question has many dimensions and nuances. What does complexity mean, and how could it be measured? This a tough nut to crack, so in this post we’ll make a retrenchment and reconsider the question in a more formal setting — computer science.… Read more

## Language Complexity, Part 2

David A. Tanzer, January 30, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Decision problems, decision procedures and complexity

In Part 1, we introduced the formal idea of a language, as being just a set of sentences. Now let’s approach the topic of language complexity.

For any given language, there is an associated decision problem:   given a candidate string of characters, determine whether or … Read more

## Language Complexity, Part 3

David A. Tanzer, February 7, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

A detailed measure of computational complexity

In Part 2, we identified language complexity by how “difficult” it is for a program to decide if some given text is a sentence of the language — in other words, by the complexity of the decision problem for the language.

Note there may be many … Read more

## Language Complexity, Part 4

David A. Tanzer, February 8, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Summarizing computational complexity

In Part 3 we defined, for each program P, a detailed function P'(n) that gives the worst case number of steps that P must perform when given some input of size n. Now we want to summarize P into general classes, such as linear, quadratic, etc.

## Language Complexity, Part 5

David A. Tanzer, February 9, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

Big O analysis

Recall our function $f(n)$ from Part 4, which gives the values 2, 13, 14, 25, 26, 37, …

Using ‘big O’ notation, we write $f(n) = O(n)$ to say that $f$ is linearly bounded.

This means that $f(n)$ will eventually become less than some linear function.

As we said, … Read more

## Language Complexity, Part 6

David A. Tanzer, February 10, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.

In Part 5 we introduced big O notation for describing linear complexity. Now let’s look at a function with greater than linear complexity.

def square_length(text):
# compute the square of the length of text
# FIXME: not the most elegant or efficient approach
n = length(text)
counter = 0
for i 
In Part 6, we saw a program with quadratic complexity. The collection of all languages that can be decided in $O(n^k)$ time for some $k$ is called P, for polynomial time complexity.