Grammars

Some texts

 

Grammars as Representations of Music, C. Roads (1979) Computer Music Journal 3(1), pp48-55

Generative theories in language  and music descriptions. J. Sundberg, and B, Lindblom, (1993) In Machine Models of Music Eds. S.M. Schwanauer & D.A. Levitt, MIT Press, pp263-288. (originally in Cognition, 1976, Vol. 4, pp 98—122)

A Generative Grammar for Jazz Chord Sequences, M.J. Steedman, (1984), Music Perception Vol. 2, No. 1, pp 52-77

Introduction to Formal Languages. Révész, G. (1985) McGraw-Hill Computer Science series, New York.

Understanding Music with AI. Balaban, M., Ebciogle, K. And Laske, O. (1992) Menlo Par k. The AAAI/The MIT Press.

 

 

Grammars

Grammars have been widely used in producing music since the 1970’s.

There is a wide acceptance of the usefulness of a “linguistic” metaphor for music.

Both involve structured sequences of information

Both seem susceptible to being organised and understood in an hierarchical manner

 

Our interest is in how grammars can be used to define or describe ``actions'' - and their order and relationships.

 

A grammar allows a single “concept” or piece to be unfolded via a sequence of actions that specify what is going to happen next - or conversely, what is allowed to happen next if we are using a grammar to validate a sequence…

Grammars can be used to specify the form of a production...i.e. how a mechanism should produce a piece of Music.

Is Music a Language?

Buhler (1934) and Popper (1972) defined a number of levels or characteristics that can be used to describe aspects of language.

This kind of classification can be used as a reference point in understanding the development, continuities and particularities of human language in the context of communication in general. These functional levels are…

Expressive

A being reveals or hides its internal states

Signalling

A being more and less efficiently signals to others to elicit some general response

Descriptive

A being describes states of the world with more and less truth

Argument

A being rationally constructs arguments about the nature of the world

Human language is recognised to encompass all four - chimpanzees can only manage 1 and 2.

Question: can we ascribe levels 3 & 4 to Music?

If the answer is yes then we are saying that music is a language just like spoken or written language.

If the answer is no then we saying that when we say that music is a language that we are just speaking metaphorically. This means that we would not necessarily expect to be able to describe musical sequences successfully using grammars

Note: We need to distinguish form and function. We may be able to describe music with grammars but that is not the same as saying that music is syntactically constructed.

Grammars - Introduction

There are several kinds of grammar...

Informal - as in school - parts of speech

Formally, a grammar is a Quadruple/Quartet of elements

A gentle introduction to grammars

A grammar is a way of describing the structure of a sequence of things.

This sequence can be of anything….

One sequence that we know very well is sentences……..

For example, take the sentence

The cat sat on the mat

This is a string of unique symbols

Now this sentence can be described in a slightly abstracted way as parts of speech, i.e.

This Sentence = Article Noun Verb Preposition Article Noun

Now when we look at this sequence we no longer have a string of unique symbols

There are two occurrences of Article and two of Noun, moreover these are in order so that we can observe a repetition of  the string.

Article Noun

So we can perhaps make our description of the sentence a bit more economical, by substituting a symbol that we know means the sequence Article Noun, lets call the NP (short for Noun Phrase) thus……

This Sentence = NP Verb Preposition NP

Grammars - Informal

We can continue our process of abstraction - although we need to look at more sentences. If we do then we can observe that sentences also include Verb Phrases (VP) and that these comprise verbs and noun phrases, and also possible adjectives and prepositions.

By the time we have finished we have the following

S = NP VP

In fact we can draw the string as a structure that shows all the components as follows..

 

 

 

 

 

 

 

 

 

 


Why do we want to describe sequences in this way?

Answer: It allows us to describe all the possible strings within a language very economically

Grammars - Formal

A Grammar is specified by a Quadruple    < VT, VN, P, S >

VT                        Terminal Vocabulary.  

e.g.     c  d  #….. this is a finite set….

VN                Non-Terminal Vocabulary.

These are a set of categories useful for expressing generalisations about relationships either between other non-terminals, non-terminals and terminals or between terminals and terminals, e.g. Chords or Arpeggios. These are usually referred to using short (confusing?) Mnemonics such as Ch, Ar, etc

P                  A Finite set of productions (rules)

e.g. a ® b

The ® symbol here means that the right-hand-side (rhs) of the rule is derived from the left-hand-side (lhs).

This is also known as rewriting - the lhs rewrites to the rhs

S                  A Root symbol, such that there is always one rule where a is S. S may rewrite itself in a more than one way

 

Types of Grammar

Formal grammars are often called Generative Grammars. Generative means defining rather than producing. However, they are used to both ``produce'' and ``recognise'' languages e.g. we might have a grammar for producing blues progressions.

 

A Language is the set of valid productions when a grammar is applied to the set of musical terms defined in the set of terminals. The productions are drawn from the Union of VT, VN,.    i.e. VT È VN

 

Chomksy defined four types of grammar by the structure of their productions

Finite State                     (Type 3).

Context Free                  (Type 2).

Context Sensitive           (Type 1).

General Rewrite             (Type 0).     (Natural Language)

 

Each grammar type n is able to produce languages of types ³ n

Grammars and Automata

Grammars define structure …...

 

Syntactic rules determine what productions are well formed within a given language.

Grammars are used by mechanisms that act according to their specification

There are strong similarities between Automata, Recognisers, and Parsers

They are all specified using grammars.

 

Automata act.

 

A Recogniser establishes (non-) conformance to a grammar.

A Parser Recognises and describes the recognised form.

A compiler/interpreter recognises, can report structure and act (or produce code).

Finite State Grammars

In a FSG the form of rules in P, i.e. a ® b is as follows

a  is a non-terminal

b  is a terminal or a non-terminal & a terminal

the order of the terminal or non-terminal doesn't matter

 

VT  

=

{c d e f g a b #, @}

VN  

=

{N P}

P

=

{

N ® P#, N ® @P,

P ® c, P ® d, P ® e, P ® f, P ® g, P ® a, P ® b

}

L

=

{

c# d# e# f# g# a# b#

@c @d @e @f @g @a @b

}

S

=

N

 

An FSG is a subset of a CFG.

Context Free Grammars

In a CFG the form of rules in P , i.e. a ® b is as follows

a  is a single non-terminal

b  is a string of terminals and/or non-terminals

 

VT

=

{c e g # @}

VN

=

{S, N, R, A}

P 

=

{

S ® N         S ® N N

N ® R         N ® R A

R ® c, R ® e, R ®g

A ® #, A ® @

}

L

=

{c e g       c# e# g#       c@ e@ g@

c e g c e g    c e g c# e# g#     c e g c@ e@ g@

c# e# g# c e g   c# e# g# c# e# g#

c@ e@ g@ c e g   c@ e@ g@ c# e# g#    c@ e@ g@ c@ e@ g@

}

S

=

S

A CFG is a subset of a CSG.

Context Sensitive Grammars

 

In a CSG the form of rules in P , i.e. a ® b is as follows

a  & b are strings of terminals and/or non-terminals

b must be equal to or longer than a

 

VT  

=

{c d e f g a b #}

 

VN

=

{Chord, Maj, Min, CS, DS, FS, GS, AS, N}

 

P 

=

{

S ® Chord

Chord®Maj,      Chord®Min

Maj ® c e g,      Maj ® CS f GS

Min ® c DS g,   Min ® CS e GS

CS ® c#,  DS ® d#,  GS ® g#

}

 

L 

=

{c e g  c# f g# c d# g,c# e g#}

 

S

=

S

 

A CSG is a subset of a General rewrite.

General Rewrite Grammars

 

In a GRG the form of rules in P , i.e. a ® b is as follows

a  & b are both strings of terminals and/or non-terminals

There are no restrictions on a and b

 

VT

=

{c d e f g a b #}

VN

=

{S, Scale, Maj, Min}

P

=

{S ® Scale

S ® Scale Scale

Scale® Maj,

Scale ®Min, Maj ® c d e f g a b 

c d e f g a b ® c d e f#

c d e f# ® c d# e

c d e f g a b Maj® Min}

S

=

Scale

L

=

{ c d e f g a b, d e g c b a f …………etc…….}

An example Grammar for a Tune

 

Grammars and Trees

 

So perhaps we have a grammar like this

S  ® P        P ® R Q

R ®c,         R ®d,         etc..

Q ® #

 

This grammar can be expressed in the form of  trees.......


 

 


In this tree each of the rewrite rules can be expressed as a branch or root of the tree