Review: \(a^nb^n\) (\(oysters^neat^n\), \(people^nmove^n\))

Review Exercises

Construct a regular grammar and equivalent finite state acceptor for \(people^nmove^n\), where \(0 \leq n<4\). What do you have to do to modify your grammar/acceptor if you want the language produced by the grammar to include \(people^4move^4\)?
Construct a context free grammar (fragment) for \(people^nmove^n\), where the depth of embedding is unbounded. Include the production rule \( S \rightarrow NP \, S \, VP\). Draw a derived tree for \(people^3move^3\) from your grammar. Can you see why this is called center embedding?
Is \(people \, (that \, move \, people)^n \, move \) a center embedding pattern? If not, how would you characterize it?
Can you think of center embedding phonological patterns? Right-branching?

Context Free Grammars and Pushdown Automata

If a grammar \(G\) is regular (finite-state), we can construct an equivalent finite state acceptor (generator) that accepts (generates) the language \(L(G)\).
If a grammar \(G\) is context-free, we can construct an equivalent pushdown acceptor (generator) that accepts (generates) the language \(L(G)\).
- A pushdown acceptor is like an FSA, but with a stack.
- Animation of PDA

Now we'll see how we can describe stress patterns using rewrite grammars.

How would you write a grammar/FSA that yields the following stress pattern (Afrikaans):

In words of all sizes, primary stress falls on the initial syllable.
How would you write a grammar/FSA that yields the following stress pattern? First try writing a grammar for just secondary stress, before doing both primary and secondary stress together. (Asmat)

In words of all sizes, primary stress falls on the initial syllable. In words of all sizes, secondary stress falls iteratively on odd numbered syllables, counting from the right.
How would you write a grammar/FSA that yields the following stress pattern? (Fijian)

In words of all sizes, primary stress falls on the final syllable if it is heavy, else on the penultimate syllable if it is heavy, else on the penultimate syllable. In words of all sizes, secondary stress falls on all heavy syllables. In sequences of light syllables, secondary stress falls on the even numbered syllables, counting from the right edge of the sequence. Light monosyllables do not occur.

Counting: Heinz (2011)

Many regular languages describe unnatural phonological patterns. For example, imagine the logically possible language in which words are well-formed only if they contain an even number of vowels, regardless of their order. Words like bbb,baba, bbaa, aab, bbaabbb are all well-formed according to this pattern, unlike words like a, ababa, bab, bababab. This pattern is a regular language, though most phonologists would agree natural languages do not contain bonafide phonological generalizations of this sort (nor could natural languages do so).
Definitions (see further-reading/formal_language/heinzhiguerazaanen2016.pdf)
1. Deterministic acceptor: a finite state acceptor with a uniqe initial state, and where, given current state and next symbol, (output and) next state is (either undefined or) unique.
  - an FSA can be forward-deterministic and/or reverse/backward-deterministic (Section 2.3.1, page 31). If people just say deterministic, they mean forward-deterministic
2. Canonical acceptor for some language: minimal (fewest states), deterministic acceptor for some language (section 3.3, page 53)
3. Tails, heads, head vs. tail canonical acceptors, left to right and right to left
StressTyp2 database
Strings vs. trees

Why implement (=formalize/compute/program), in addition to pen/paper?
1. Verification: Hulden 2017 (code), Finley 2011, Karttunen 2006, 2006a (further-reading/formal_language/karttunen2006.pdf, karttunen2006a.pdf)
2. Making analysis possible at all: generation of infinite candidate set
3. Computing whole grammars: Albro 2005. (Dan Albro)
4. For understanding: in order to implement, you have to understand and make decisions about every last detail. Assumptions are laid bare. Often before implementing, you don't even realize where you are making assumptions!