Commentary by Chris Pressey

This work is distributed under a CC-BY-ND-4.0 license, with the following explicit exception: the ratings may be freely used for any purpose with no limitations.

Formal Language

Introduction to Formal Languages

• rating: 1

A decent older textbook on formal languages.

Natural Language Processing Techniques in Prolog

• rating: 1

Some introduction to DCGs and chart parsing and feature structures.

Programs, Grammars, Arguments

• rating: TODO

.

The Hardest Context-Free Language

• rating: classic

It's CFL-complete, for any reasonable conception of "CFL-complete".

Lecture 7: Definite Clause Grammars

• rating: 1

.

On the Structure of Context-Sensitive Grammars

• rating: 2

Interesting technical report on (and this is the author's phrasing, not mine) "what context gets you".

It's like a Turing machine, but in some ways worse. It doesn't just have to launch the tape head flying down the tape until it reaches some area of interest (a global variable, say); it actually has to launch symbols across the input string, sliding them along like "messages", until they interact with whatever we wanted them to interact with.

In this way, it's also a lot like a 1D cellular automaton.

Functional Unification Grammar

• rating: 0

.

Definite Clause Grammars for Language Analysis

• rating: 1

.

Formal Languages and Infinite Groups

• rating: 1

An exposition of formal language theory from the perspective of group theory, giving an algebraic formulation of the usual classes of formal languages.

Formal languages and groups as memory

• rating: 1

Explores an interesting twist on "counter automata" where the "counter" is not an integer, but only an algebraic structure with (some of) the properties of an integer: a group or a monoid.

finite automata - Is there a reasonable and studied concept of reduction between regular languages? - Computer Science Stack Exchange

• rating: 1

.

parsers - Representing \"but not\" in formal grammar - Computer Science Stack Exchange

• rating: 1

.

formal languages - Proving that a word is *not* generated by a context-free grammar - Computer Science Stack Exchange

• rating: 1

.

closure properties - Does there exist an context free language L such that L∩L\^R is not context free? - Computer Science Stack Exchange

• rating: 1

.

computability - Context-free complete language - Computer Science Stack Exchange

• rating: 3

.

Natural examples of context-sensitive languages from practice - Theoretical Computer Science Stack Exchange

• rating: 1

.

idioms - Is \"regex\" in modern programming languages really \"context sensitive grammar\"? - Stack Overflow

• rating: 1

.