Syntax

How to put words together to form complex phrases

Obviously not every sequence of words should be grammatical, e.g.

• Colourless green ideas sleep furiously
• *Sleep green furiously ideas colourless

A language can be finite or infinite, but your language should be infinite

An infinite language has a finite set of grammatical rules that decide which strings of words are grammatical and which ones are not

Languages and sets

A language can be understood to be a set of strings of words

• Let's call the entire set of words in
• We assume to be finite

We denote the set of all possible strings of words in by (Kleene Closure of )

• is an empty string

If a string of words is a member of () we say is grammatical in ; otherwise () is ungrammatical in

Syntax as a function

The syntax of should tell us for any whether or

The syntax of can be seen as a single function : for any string :

NB: This assumes that grammaticality is binary

• We stick to this assumption, as per most syntactic theories
• Alternatively one could understand grammaticality as a more gradient notion, in which case will return values in , for example
• Cf. grammaticality vs. acceptability

Decision problems and computability

The problem of determining whether or , for an arbitrary is a decision problem

Chomsky hierarchy

Some computable functions are 'simpler' than others

Correspondingly there are different levels of syntaxes/languages

By J. Finkelstein - CC BY-SA 3.0, Link

Example 1: A finite regular language

The syntactic rules of :

• A grammatical sentence must contain at least one and at most two 's.
• must be preceded by and followed by .
• can be preceded by but not by or .

Production rules

The syntax of regular languages is described by a finite set of production rules

• : set of terminal symbols =
• : set of non-terminal symbols

A production rule of a regular language has to look like:

• ; or
• ; or

where and

One member (usually ) of is a start symbol

Production rules for

Example 2: An infinite regular language

Production rules

Remarks

• Every finite language is a regular language (proof omitted)

• What we defined above is right regular languages

• For any right regular language, there is an equivalent left regular language, and vice versa (proof omitted)

Remarks (cont.)

• Every regular language is recognised by a finite state automaton, and every language recognised by a finite state automaton is a regular language (proof omitted)

• A finite state automaton is a kind of machine that does not have (long-term) memory

• Regular languages can encode certain types of dependencies

  • In both and , must be immediately followed by
  • Such dependencies can be long-distance, e.g., if there is a , there must be a following it at some point

Non-regular languages

• However, regular languages are not capable of unlimited counting, so there is no way to formulate dependencies like the following (proof omitted)

  • There can be any number of 's, but there must be the same number of 's following all the 's
  • Similarly for non-terminal levels, e.g., if there are -many 's, there must be -many 's

• Natural languages show such dependencies, e.g., centre embedding

• It's been claimed that birdsongs are regular languages

Context Free Languages

Context free languages are generated by productions rules of the form:

where is any sequence of terminal and/or non-terminal symbols

• Every regular language is a context free language
• There are context free languages that are not regular, e.g.

Example derivations in CFL

Remarks

• Context free languages can have unlimited center embedding dependencies, so more powerful than regular languages

• Every context free language is recognised by a push-down automaton, and every language recognised by a push-down automaton is a context free language (proof omitted)

• A push-down automaton is a machine with a stack memory

Non-context free languages

• There are languages that are not context free, e.g., (proof omitted)

• Syntacticians argue that some natural languages have unbounded numbers of cross-serial dependencies, so are not context free

• Chomsky's Transformational Grammar:

  • Prase-Structural Rules are context free and generate D-structures
  • D-structures are mapped to S-structures by Transformations
  • Transformations need to be constrained so that natural languages are not entirely context-sensitive or recursively enumerable

More powerful languages

• The next class of languages in the Chomsky hierarchy is context sensitive languages, whose production rules are either of the following:

  • 
    where are any strings of terminal or non-terminal symbols and

• Natural language syntax does not have the full power of context-sensitive languages

  • E.g., no rules like "the same number of determiners, nouns, and verbs in the same sentence but in any order"

More powerful languages

• Natural language is mostly context free, but it goes a bit outside of it with certain types of cross-serial dependencies

• Mildly context free languages

  • Tree Adjoining Grammar
  • Multiple Context Free Grammar
  • Minimalist Grammar

For your language

• No need to make syntactic rules for the entire language

• Focus on some constructions, e.g.

  • Simple intransitive and transitive sentences name + predicate (+ name)
  • Structures of DPs

• If you like, you can write some context-free rules for some (or all) of the constructions

• Make sure to have recursion so that your language will be infinite

Example: Context free rules for DPs in English

Example: Mirror English