Probabilistic context free grammars.md

Context Free Grammars

Some grammar defined by the tuple:

G = (V, Sigma, R, S)

1. V- finite set. v ∈ V called nonterminal variable, or variable. Each variable defines a sub-language of language defined by G.
2. Sigma - finite set of terminals, disjoint from V. Set of terminals is the alphabet of the language defined by grammar G.
3. R - finite realisation (productions) from V to (V U Sigma)* (++ Kleene star operation). Members are the (rewrite) rules or productions of the grammar.
4. S - start variable/symbol used to represent the whole sentence (or program).

Production rule notation: (⍺, β) ∈ R, where ⍺ ∈ V is a nonterminal, β ∈ (V U Sigma)* is a string of variables and/or terminals. Usually formulated as ⍺ -> β.

Rule application: For any strings u,v ∈ (V U Sigma)* , say u yields v (u ⇒ v) if there exists (⍺, β) ∈ R, with ⍺ ∈ V and u1, u2 s.t. u = u1⍺u2, v = u1βu2. Thus v is the result of applying the rule (⍺, β) to u.

++ Kleene star operation

1. If V is a set of strings, then V* is defined as the smallest superset of V that contains the empty string ε and is closed under the string concatenation operation.
2. If V is a set of symbols or characters, then V* is the set of all strings over symbols in V, including the empty string ε.

Example

1. Nonterminal (auxillary) alphabet, V = {S, T}
2. Terminal alphabet, Sig = {'(', ')'}
3. Start Symbol, S - S
4. Productions, R : S -> () S -> (T) T -> S S -> TT

Example generated sequences

S -> ()

S -> (T) -> (S) -> (())

S -> TT -> SS -> ()()

S -> TT -> SS -> ()(T) -> ()(S) -> ()(())

Application to Rhythmic Sequences

Grammar used to generate coherent skeletal rhythmic patterns. Define our grammar as such:

1. Auxillary Alphabet: V = {S,M,H}
2. Terminal Alphabet: Sigma = {h, q}
3. Start Symbol: S = S
4. Production Rules R: S -> M S -> MS M -> HH H -> h H -> qq

where S - Sequence of one or more measures M - Whole measure (crot) H - Half measure h - half note q - quarter note

Example Generated Rhythms

S -> M -> HH -> hH -> hh

S -> M -> HH -> hH -> hqq

S -> M -> HH -> Hh -> qqh

S -> MS -> HHS -> qqHS -> qqhS -> qqhHH -> qqhqqH -> qqhqqh

and so on.

Application to Tidal Cycles

1. Applying the above to the mini-notation of Tidal Cycles, for some pattern

d1 $ gain (slow 2 $ gainPat) # s "bd"

let gainPat = some sequence of 1s and 0s..

Measure -> [1]

Half Measure -> [[1] [1]]

Half Note -> [[1 1] [1 1]]

Quarter Notes -> [[[1 1] [1 1]] [[1 1] [1 1]]]