Klanken 2
Dit college
• Fonologie met eindige automaten en
transducers
Colleges en hoofdstukken
• 28 april: Klanken 1 (fonetiek, fonologie)
Chapters 2 en 7
• 3 mei: Klanken 2 (eindige automaten en
transducers)
Chapters 2, 3 en 11
• 10 mei: Woorden (morfologie)
Chapter 3
Automaten: Talen
• We kunnen de mogelijke syllaben en
woorden in een taal opvatten als een
verzameling rijtjes over een alfabet van
fonemen (d.w.z. als een formele taal)
• Een simpel voorbeeld: Alfabet = { p, k, a, i
}, Taal = { pa, ka, pi, ki, papa, papi, pipa,
pipi, …, paki, …, kipa, …, kikipa, …,
pakipapa, … }
Formele Talen
Eindige Automaten
• Een taal kan worden gekaraktiseerd door een
eindige automaat (finite automaton/state
machine)
• Een automaat herkent een taal door stap voor
stap de tekens van een inputrijtje op een tape te
lezen en een aantal toestanden te doorlopen.
• Geslaagde herkenning: einde tape en tevens in
een accepterende eindtoestand.
Example of a finite automaton
f
on
off
f
• There are states off and on, the automaton
starts in off and tries to reach the “accept
state” on
• What sequences of f ’s lead to the accept
state?
• Answer: {f, fff, fffff, …} = {f n: n is odd}
• This is a finite automaton over alphabet
{f}
Deterministic finite automata
deterministische eindige automaten
• A deterministic finite state automaton
(DFA) is a 5-tuple (Q, S, d, q0, F) where
–
–
–
–
–
Q is a finite set of states
S is an alphabet
d: Q × S → Q is a transition function
q0  Q is the initial state
F  Q is a set of accepting states (or final
states).
• In diagrams, the accepting states will be
denoted by double loops
Example
q0
1
1
alphabet S = {0, 1}
states Q = {q0, q1, q2}
initial state q0
accepting states F = {q0, q1}
q1
0,1
0
q2
table of
transition function d:
inputs
states
0
q0
q1
q2
0
q0
q2
q2
1
q1
q1
q2
Language of a DFA
The language of a DFA (Q, S, d, q0, F) is the set of
all strings over S that, starting from q0 and
following the transitions as the string is read left
to right, will reach some accepting state.
f
M:
on
off
f
• Language of M is {f, fff, fffff, …} = {f n: n is
odd}
Meer Voorbeelden
S = {0, 1}
0
q0
b
b
0
q0
q1
a
q1
0
b
a
1
1
q3
a
q1
a
q2
0, 1
0
q2
Wat zijn de talen van deze automaten?
b
b
q4
1
1
S = {a, b}
q0
a
Reguliere expressies
• We hebben hier te maken met een
reguliere taal – een taal beschreven door
een FSA.
• Een reguliere taal kan ook beschreven
worden door een reguliere expressie:
([pk][ai])+
Operaties over talen
• Let L, L1, L2 be subsets of Σ*
• Concatenation:
L1L2 = {xy | x is in L1 and y is in L2}
• Concatenating a language with itself: L0 = {ε}
 Li = LLi-1, for all i >= 1

i0
• Kleene Closure:
• Positive Closure: L+ =


i 1
L* =
Li = L0 U L1 U L2 U…
Li = L1 U L2 U…
Kleene-sluiting
Say, L1 ={a, abc, ba}, on Σ ={a,b,c}
Then, L2 = {aa, aabc, aba, abca, abcabc, abcba, baa, baabc, baba}
L3= {a, abc, ba}. L2
L* = {ε} U L1 U L2 U L3 U . .
Definitie van een Reguliere Expressie
• Let Σ be an alphabet. The regular expressions over Σ are:
– Ø
– ε
– a
Represents the empty set { }
Represents the set {ε}
Represents the set {a}, for any symbol a in Σ
Let r and s be regular expressions that represent the sets R and S,
respectively.
–
–
–
–
r|s
rs
r*
(r)
Represents the set R U S (precedence 3)
Represents the set RS
(precedence 2)
Represents the set R* (highest precedence)
Represents the set R (not an op, provides precedence)
• If r is a regular expression, then L(r) is used to denote the corresponding
language.
Examples: Let Σ = {0, 1}
(0|1)*
All strings of 0’s and 1’s
0(0|1)*
All strings of 0’s and 1’s, beginning with a 0
(0|1)*1
All strings of 0’s and 1’s, ending with a 1
(0|1)*0(0|1)*
All strings of 0’s and 1’s containing at least one 0
(0|1)*0(0|1)*0(0|1)*
All strings of 0’s and 1’s containing at least two 0’s
(0|1)*01*01*
All strings of 0’s and 1’s containing at least two 0’s
(1|01*0)*
All strings of 0’s and 1’s containing an even number of 0’s
1*(01*01*)* All strings of 0’s and 1’s containing an even number of 0’s
(1*01*0)*1* All strings of 0’s and 1’s containing an even number of 0’s
‘Flapping’ in Amerikaans Engels
foneem /t/
flapping regel
na een beklemtoonde klinker ( ) en voor een onbeklemtoonde klinker
(V), is [dx] de allofoon voor de foneem /t/
Transducers (informeel)
Transducers (formeel)
deterministische eindige automaten
(DFA)
 (1)
niet-deterministische eindige automaten
(NFA)
 (2)
eindige toestands transducer
(finite state transducers FST)
Van DFA naar NFA
• Construct a DFA over alphabet {0, 1} that
accepts those strings that end in 101
0
• Sketch of answer:
0
q0
1
qe
1
0
q1
1
q00
1
q01
…
q10
q11
1
…
1
1
q001
…
0
q000
q101
…
0
q111
1
Would be easier if…
• Suppose we could guess when the string
we are reading has only 3 symbols left
• Then we could simply look for the
sequence 101
and accept if we see it
3 symbols left
1
0
qdie
1
This is not a DFA!
Nondeterminism
• Nondeterminism is the ability to make
guesses, which we can later verify
• Informal nondeterministic algorithm for
strings that end in 101:
1. Guess if you are approaching end of input
2. If guess is yes, look for 101 and accept if you see it
3. If guess is no, read one more symbol and go to step 1
Nondeterministic finite
automaton
• This is a kind of automaton that allows you
to make guesses
0, 1
q0
1
q1
0
q2
1
q3
• Each state can have zero, one, or more
transitions out labeled by the same symbol
(1) Van DFA naar NFA
• A deterministic finite state automaton
(DFA) is a 5-tuple (Q, S, d, q0, F) where
–
–
–
–
–
Q is a finite set of states
S is an alphabet
d: Q × S → Q is a transition function
q0  Q is the initial state
F  Q is a set of accepting states (or final
states).
(1) Van DFA naar NFA
• A nondeterministic finite state automaton
(NFA) is a 5-tuple (Q, S, d, q0, F) where
–
–
–
–
–
Q is a finite set of states
S is an alphabet
d: Q × S × Q is a transition relation
q0  Q is the initial state
F  Q is a set of accepting states (or final
states).
0, 1
q0
1
q1
0
q2
1
q3
0, 1
q0
(q0 , 0, q0)
(q0 , 1, q0)
(q0 , 1, q1)
(q1 , 0, q2)
(q2 , 1, q3)
1
q1
0
q2
1
q3
(2) Van NFA naar FST
0, 1
q0
1
q1
0
q2
1
q3
(2) Van NFA naar FST
0:a, 1:b
q0
1:y
q1
0:x
q2
1:y
q3
(2) Van NFA naar FST
0:a, 1:b
q0
1:y
q1
0:x
011110101 => abbbbayxy
000101000 niet geaccepteerd
q2
1:y
q3
(2) Van NFA naar FST
• A finite state transducer (FST) is a 6-tuple
(Q, S, Δ, d, q0, F) where
–
–
–
–
Q is a finite set of states
S is an input alphabet
Δ is an output alphabet
d: Q × S × Δ × Q is a non-deterministic
transition relation
– q0  Q is the initial state
– F  Q is a set of accepting states (or final
states).
Voorbeeld – Meervoud in het Engels
[ix z] na de “sibilant” fonen [s], [sh], [z], [zh], [ch] of [jh] -
peaches
[z] na “voiced” klanken
-
pigs
[s] na “voiceless” klanken
-
cats
faxes
in lexicon: f aa k ^ z
Automaten: Voorbeeld
p|k|a|i
2
Begintoestand en
eindtoestand
a|i
Eindig aantal
toestanden
p|k
p|k
1
0
a|i
Toestandsovergangen
bij het lezen van
bepaalde symbolen
Automaten: Voorbeeld
p|k|a|i
3
a|i
p|k
0
1
p|k
0
Met een ‘jump’
a|i
2
basi (bus)
bwana (mijnheer)
duka (winkel)
jenga (bouwen)
kwanza (eerst)
mama (moeder)
mbuzi (geit)
mvua (regen)
ndizi (banaan)
ngoma (trommel)
ngwena (krokodil)
njia (weg)
ona (zien)
pangwa (gepland)
pwani (strand)
saa (horloge)
simba (leeuw)
wingu (wolk)
unga (meel)
mbalimbali (allerlei)
asante (bedankt)
desemba (december) kawaida (gewoonte)
kitunguu (ui)
kamera (fototoestel)
maharagwe (bonen)
matata (problemen)
endelea (doorgaan)
safari (reis)
kampuni (onderneming) tofauti (verschil)
Ufaransa (Frankrijk)
mandazi (doughnut)
madaraka
kidogo (klein)
(verantwoordelijkheid)
ofisi (kantoor)
barabara (weg)
kilimanjaro
milionea (millionaire)
arobaini (veertig)
Swahili lettergrepen
• Taalkundige analyse
syllabestructuur: NCwV
opeenvolging van 1 of meer syllaben
• Reguliere expressie in Wingrep
^([mn]?[zsjhrlfvptkbdg]?w?[aeiou])+$
• http://www.wingrep.com/
Descargar

Document