Samenvatting

Samenvatting Formele en Natuurlijke talen Eindtentamen

5 keer verkocht

Instelling
Universiteit Utrecht (UU)

Dit document bevat al mijn aantekeningen van de opgegeven readings (controleer of deze overeenkomen met het academische jaar van jouw studie), deze zijn in het Engels. Het bevat ook enkele pagina's met algemene aantekeningen die een overzicht bieden van de notatieafspraken en samenvattingen van all...

[Meer zien]

Voorbeeld 6 van de 39 pagina's

Bekijk voorbeeld

Geupload op 24 februari 2024
Aantal pagina's 39
Geschreven in 2022/2023
Type Samenvatting

talen
fsa
cfg
nlp
taalkunde
bloch
pda
chomsky

Volgen

Alysa3 Lid sinds 1 jaar 15 documenten verkocht

€9,43

In winkelwagen

Opslaan

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

R6 : 'max I NT per regel
zich hebben
overgankelijk ww moet
bij (kijken naar)
.

een Ir NT voor aant
>
af
At
voeg jef
3 voor a

toe(/A a) f)
, ,

4 been s rechts

Algemene aantekeningen tentamen slide
(voornamelijk aantekeningen)
① KI omvat vack taal ;
begrijpen genereren samenvatten
, , , vertalen
↳
verkrijgt kennis van
falige data text data mining
:

Natuurlijke taal: complex communicatiesysteem dat zonder opzettelijk ingrijpen van mensen ontstaat uit menselijke interactie & taalvermogen
• (spontaan ontstaan) (vanuit het menselijke taalvermogen) natuurlijk gebarental =

Spellingsregels zijn gebaseerd op je talige Kennis ,
geen
onderdeel uit
maar maken
je talige Kennis
Ons natuurlijke taalvermogen is creatief; verz. (basis)woorden in een taal is eindig, brein is eindig -> Toch kunnen we met deze middelen
v .

oneindig aantal zinnen produceren/interpreteren

Jonologie : Klanken ,
morfologie woorden syntaxis
:
,
: Zinnen
Verzameling reeksen is een formele taal; formele talen beschrijven kennis v/e natuurlijke taal via een verz. klankreeksen, een verz.
morfeemreeksen en een verz. woordreeksen

② Cartetisch product X [Ix y)/XEX
1yey) Een
x) = > relatie is een deeluerz. Vle cartetisch product
-
:
,

P(Xxy) is .
verz U alle relaties tussen X
.

enly R∈ ℘(X×Y) is een functie desda voor elke x∈X er precies 1 y∈Y bestaat zodat (x,y)∈R
Een relatie over X is een deelverzameling van X × X —> R ∈ ℘(X × X)
Symmetrie: ∀x∈X, ∀y∈X: (x,y)∈R (y,x)∈R
Transitiviteit: ∀x∈X, ∀ ∈X, ∀z∈X : (x,y)∈R en (y,z)∈R
Reflexiviteit: ∀x ∈ X : (x, x) ∈ R
(x,z)∈R
Sequivalentie-relatie ((d-funstie

elkaar kennen =

symmetrisch en
transitief (wwtelkaar kan
symmt trans ,
alleen
symm of geen
, van beide zyin)

38] all sets O ,
all sets , [OS all PIX) OE all sets ,
boomheeft
geen cykels

Gelabelde directionele graaf: <V,E,L,f> (<knopen,bogen,labels,label-toekenning>) Vb label-toekenning: ((2,slaat), (1,Jan)), subject)
Cykel: begint en eindigt in zelfde knooppunt, Simpele cykel: bevat 3 of meer verschillende knooppunten, (in een ongerichte graaf geen pijlen)
Pad: knooppunten zijn verbonden (2,3,2), Simpel pad: knooppunten verbonden, maar worden niet herhaald (3,2,1)

Computationele complexiteit gaat over geheugen(ruimte) en tijd, structurele complexiteit gaat over het soort machine wat nodig is
③ Neem een verz. symbolen Σ, elke geordende sequentie van elementen in Σ = een rijtje over Σ (kan e zijn; lege rijtje)
Concatenatie: aan elkaar plakken van 2 geordende rijtjes, Exponentie: (ba)^2=baba, maar 2^3=222 (Σ ^1={e concat a, e concat b})
Kleene-ster: verz. van alle mogelijke eindige rijtjes over Σ
Klasse v. talen over L(Σ) = P(Σ*) wil zeggen: de set van talen over Σ = powerset v. alle strings die gevormd kunnen worden door concatenatie v.
symbolen uit Σ (dus powerset van de Kleene-star van Σ; een aftelbaar oneindige set, met overaftelbaar veel talen)
*
Σ*=altijd aftelbaar oneindig, Kleene star v/d lege set is enige Kleene-closure die eindig is (een eindige taal produceert) -
Sterkte regels: haakjes> * + ? >rijtjes >disjunctie
Recursieve Kleene star leidt tot dezelfde verzameling ( {a, b}* = ({a, b}*)* )
(𝐿̅ )∗ ≠ 𝐿̅ ∗ ,dus e zit wel in (𝐿̅ )∗ maar niet in 𝐿̅ ∗ (in dit geval gaat het om het complement van L*, en e zit wel in L* dus niet in het complement)
Als s en t reguliere expressies zijn corresponderend met talen Ls en Lt:
- dan is /s|t/ een regexp corresponderend met Ls ∪ Lt (disjunctie)
- dan is /st/ een regexp corresponderend met Ls · Lt (is concatenatie)
- dan is /s∗/ ook regexp corresponderend met Ls (alles)
alle strings st of th

/1*/ = {1}*

⑭ FSA Eindige toestandsautomaat: <E,S,s,A,R> (alfabet, verz toestanden, start, verz acceptatietoestanden, transitie-relaties)
Transitie-relatie is functie R: (({x,y}x{a,b}) -> {x,y}) ((toestand, alfabet), toestand) of ((SxE) -> S)
M > w1,…,wn desda er een berekening s0,…sn zodanig dat s0 de begintoestand is, sn een accepterende toestand is en A1<1<n: R((si-a, wi)) = si
P-deterministisch: als er voor sommige elementen in het domein geen afbeelding is (partieel gedefinieerd), of in een gegeven toestand zijn er
meerdere overgangen voor zelfde symbool mogelijk
T-determinsitisch: overgangsfunctie is gespecificeerd voor elke combinatie van toestand en symbool
-> Om t-deterministisch te maken voegen we een ’afvalbak’ toe (voeg een toestand x toe, en laat alle ongedefinieerde gevallen een transitie
vormen naar x)
Voor niet-deterministische automaten geld dezelfde definitie die door pijl wordt aangegeven alleen is de laatste ‘=‘ een ‘element’ symbool
FST Eindige toestandtransducer: <E1, E2, S, s, A, R1, R2> (inputalfabet, outputalfabet, toestanden, start, acceptatietoestanden, transitie-instructies,
schrijfinstructies), waar R1:(SxE1*)->S en R2:(SxE1*)->E2, dus R1: (toestand, input), toestand) R2: (toestand, input), output)
Voorbeeld: een+man:Det-Noun correspondeert met {((q0, een),q1), ((q1, +),q2)} {((q0, een), Det), ((q1, +), -)}
Een FST wordt gebruikt om input strings te vertalen/manipuleren produceert output op basis van de input string)

, () X y) 2) E toestandovergangen
, ,

(X y2)
, = Productieregels
(1 , b) 2)
,
>
-
(1 , b2)

A -B =
(AUB)
FSAs corresponderen met formele talen en FSTs corresponderen met relaties
In een NFSA produceert elk toestand-symbool paar een set van toestanden
Bij NFSA zijn er inputs waarvoor we bij het lezen van een string een keuze moeten maken
Voor alle talen die door een FSA herkend worden bestaat er een NFSA (mapt alle toestand-string combinaties naar de singletons set die de staat
bevat waar de deterministische versie v/d FSA de combinatie naartoe mapt)

⑤ Concatenatie: L1 L2 = {aba, abc, aaa, aac,…}, waar L1={ab, aa} en L2={a, c}
Reguliere talen over Σ: 0, {e}, {o} (zolang o een element is van Σ) , L1 L2 (zolang L1 & L2 regulier zijn), L1 U L2 (zolang L1 & L2 regulier
zijn), L* (zolang L dat is)
FSA L1 U L2 is gevormd door een nieuwe start-toestand te maken waarbij je vanuit deze toestand met twee overgangen van lege rijtjes naar
de (oude) start-toestanden van de 2 FSA gaat
FSA L1 L2 is gevormd door vanuit de acceptatie toestand van L1 een overgang met lege rijtje te maken naar de start-toestand van L2
Reguliere talen: precies de klasse v talen waarvoor we een (non-)deterministische FSA-, een regex- of een RG kunnen geven die precies de
taal beschrijft
Sluiting: X is gesloten onder operatie O desda voor alle x1,…,xn in X geldt dat O(x1,…,xn) in X (bijv. N is gesloten onder +)
Verz reguliere talen is gesloten onder , U, *, complementatie en omkering (bv. concatenatie v 2 reguliere talen -> reguliere taal)
Omkering: F′ = ⟨Σ,S,a,{s0},R′⟩ zodat R′ = {((t,x),u) | ((u,x),t) ∈ R}
Als er een berekening s0s1…a is voor x1,…,xn voor F -> Dan is er een berekening a...s1s0 voor xn,…,x1 voor F′
En dus: als F α accepteert, accepteert F′, α^R (omkering van α)
Als L(M) oneindig is dan bestaan er rijtjes zodat |r| > |S| (lengte rijtjes > aantal toestanden in automaat)
Pomp-lemma: Voor elke reguliere taal L bestaat er een p zodat voor elk rijtje in L met |r| > p er rijtjes x,y,z zijn zodanig dat:
1) r=xyz, 2) |xy|<p, 3) voor elke i>0: xy i z zit in L (als y wordt herhaald, zit dat rijtje nog steeds in L)
Algoritme voor contradictie: 1) kies een rijtje r in L zodat |r|>p (al weten we niet wat p is), 2) beschouw alle mogelijke opsplitsingen voor r in
-

x,y,x zodanig dat |x,y|<p en y niet leeg, 3) voor alle mogelijke opsplitsingen: kies een waarde voor i zodanig dat xy^i niet in L zit
-

Complement van een FSA vindt je door hem t-deterministisch te maken en de accepterende-toestanden en de toestanden om te wisselen
! Als de unie van een niet-reguliere en een reguliere taal disjoint zijn dan is de unie altijd regulier (niet-reguliere wordt onderdeel van reguliere)
~R R >
-

NR onderdeel van R
&

⑥ Basiselementen taal: morfemen (gebonden morfemen zijn niet zelfstandig bruikbaar, vrije morfemen wel)
Wortels + affixen (prefix(ongeluk), suffix(geinig), infix(mawani), circumfix(gefietst))
*
* vormen nieuwe Morfemen combineren: Derivatie (toepassing gebonden morfeem, woordsoort verandert meestal, verkleining valt hieronder),
lexemen Inflectie (toepassing gebonden grammaticaal morfeem, behoud woordsoort, grammaticaal relevant, ww-vervoeging en mv vallen hieronder),
*
Compounding (stam+stam) -> Reduplicatie: wortel vormt affix aan de wortel zelf
Citicisatie: (combiantie stam+clitic(speelt rol van een woord, maar is afgeleid en toegevoegd aan een ander woord) vb. -ve in I’ve is een clitic)
Woordsoorten: functionele-(D, P, C, pronomina), en inhoudswoorden(N, Adj, V, Adv) zijn een open klasse met veel morfologie
Inflectie is categorie-gebonden en vindt na derivatie plaats (tafel-tje-s / *tafel-s-tje)
Isolerende talen: Geen gebonden morfemen, grote rol voor woordvolgorde en hulpwoorden, werkwoorden zijn niet inflecterend
Agglutinerende talen: Gebonden morfemen zijn affixen, 1 betekenis per morfeem, morfemen met verschillend betekenissen worden aan stam
toegevoegd
Inflecterende talen: Gebonden morfemen zijn affixen, morfemen/woorden hebben vaak meerdere betekenissen (verandering naamval)
Meestal vallen woorden gebouwd met morfologische processen wel onder reguliere talen
Onzijdige zelfstandige naamwoorden zijn het-woorden (boek is onzijdig) of i wordt it o

FSTs en reguliere relaties zijn gesloten onder unie, FSTs zijn gesloten onder inversie(parser->generator) & compositie(2 serie-FSTs -> worden 1)
Derivatie Slides Gay >*
-

Spy van
af start bestaat er een derivate zodat o in de taal zit
Formele grammatica: <E,N,S,P> hieruit volgt G = <E,N,S,P>, L(G) = {o | S=>*G o en o zit in E*}
⑰ Left-most end right-most derivation: vervang steeds de meeste linkse/rechtse non-terminal, waarbij afleiden laat zien dat een rijtje in de taal zit
Grammatica is ambigu als er een rijtje o in E* zit zodanig dat er meerdere (left-/right-most derivation) derivaties zijn van o (>1 parseerboom)
Rechts-lineaire grammatica producties: X->yZ, X->y, X->e (dus non-terminal rechts) & Links-lineaire grammatica producties: X->Zy, X->y, X->e
RG bestaan uit rechts- OF links lineaire grammatica’s (Een grammatica met Productieregels r:(X,xX) én l:(X,Xx) is niet regulier)
Gegeven een FSA (<E,S,s,A,R>) kunnen we een formele grammatica (<E,S,s,P>) construeren waarbij F->e altijd onderdeel is van de A
Zwak equivalent: L(G1)=L(G2), bomen verschillen bij dezelfde string & Sterk equivalent: zwak equivalent EN bouwen dezelfde parseerboom
Derivatie-similariteit is een equivalentie-relatie (trans, reflex, symm) talen
hetzelfde

Constituent is een groep woorden die samen een eenheid vormen
⑧ Vb bewijs voor constituenten: aanwijzende voornaamwoorden (Sue kuste Jan, ze deed ‘dat’ vorige week)
Elke zin is opgebouwd uit S(ubject), V(erb), O(bject) (meeste talen: SVO of SOV)
! Nederlands is SOV maar kent ook V2: in een oningebedde zin (hoofdzin) staat er altijd precies 1 constituent voor het (hulp)werkwoord
Sue keek naar de man met de verrekijker (SVO) V2: Naar de man met de verrekijker keek Sue (hulpww-O-V-S)
n-war

Constituent testen in SV7

, Recursiere toepassing
Regels kan
x

Productieregel
v. een
X-
geeft transitie (51 X) (5) o
.

> o e, -
taal
, ,
reguliere oneindig maken

CFG kan
reguliere talen beschrijven Center-embedding kan niet in
reguliere talen

*
d=
derives as c
Hoofd: belangrijkste woord v/h constituent [VP->[V brak][NP …]]
Onder-generatie: Grammatica herkent niet alle grammaticale zinnen, Over-generatie: grammatica herkent ook ongrammaticale zinnen
Functionele woorden geven grammaticale info en zouden weggelaten kunnen worden, Inhoudelijke woorden geven info over inhoud v/d zin
Complementizers voegen 2 zinnen samen mbv voegwoorden (maar, want, omdat, doordat, en, dus, of)
Hiërarchische structuur wordt gevormd door het integreren van constituenten in andere constituenten
Hoofd voorbeeld: In de PP regel (PP-> P NP) is P het hoofd
Conjoin regel: XP-> XP conj XP
Polysyntetische taal: taal bestaande uit zwaar geinflectioneerde woorden
Hoofdinitieel en hoofdfinaal wordt onderscheiden door mogelijkheid v/h hoofd vooraf of achteraf (NED is hoofdinitieel; ‘over mij’, ‘van Piet’)

⑨ De klasse reguliere talen {0^n1^m|n,m>0} ⊂ context-vrije talen {0^n1^n|n>0} ⊂ berekenbare talen{oo|o in{0,1}*} (copy-taal, niet CF)
Typische derivatie regels tot nu toe niet regulier (niet links- of rechts linear), wel CF
CF-grammatica is een formele grammatica <E,N,S,P> waar P ⊆ N x (N U E)* dwz links alleen n-terminals, rechts zowel terminals als n-terminals
CNF: 1) Geen start-symbool rechts, 2) A->BC (2 non-terminals rechts), 3) A->a (1 terminal rechts), 4) bevat nooit het lege rijtje
Elke CFG heeft een CNF -> dus als we dingen willen bewijzen over CFG en CFL kunnen we CNF aannemen (CNF vereenvoudigt parseren)
Bewijs CFL: met een CFG of een PDA (T is context-vrij desda er een CFG G is zodanig dat T = {o|S=>*G o}
PDA: <E,T,S,s,A,R> (taal-alfabet, stack-alfabet, toestanden, start, acceptatie-toestanden, transitie-relaties)
R bevat altijd de transitie (s0, e, e)->(s1, S), de transitie naar de acceptatie toestand dmv niks te lezen en de $ op de stack te pushen)
PDA accepteert een o in E* desda er een R in A zit zodat (s,o,e) |- (f,e,e) (begonnen in s en eindigt in accpetatie-toestand nadat string is gelezen)
PDA tabel: toestand, input(begint met e ), stapel(begint met $)
Overgangen: 1,0|e staat voor: input,pop(gelezen)|push(stapel)
CFL is gesloten onder , U, * en niet gesloten onder intersectie en complementatie
Als je n vertakkingen hebt in een CNF boom: max 2^n bladeren (rijtje lengte 8 is CNF boom minimaal 3 vertakkingen hoog, 2log(8)=3)
Hoogte tel je bij de uiteinden van de vertakking (dus niet bij de terminalen!!!)
Als er in een CFL met n niet-terminalen een rijtje o mogelijk is wat langer is dan 2^n dan weten we dat het aantal vertakkingen in de
parseerboom >n is, dus moeten er niet-terminale zijn herhaald (pompbaar!)
Pomplemma CFL: voor een CFL T bestaat er een getal m zodat voor elk rijtje o in T met o>m er rijtjes u,v,w,x,y bestaan zodat: 1) o=uvwxy,
2) vwx<m, 3) vx>1 (niet leeg) en voor elke i>0 geldt: uv i i
wx y zit in T
! Zie productieregel-veranderingen in 5.3 van samenvatting lecture 9 non-CNF -> CNF
Als hoogte v/d boom n is, heeft hij een string die in de wortel begint en in een blad eindigt: n+1 non-terminals
Alle reguliere talen zijn CF omdat alle lineaire grammatica CF zijn, en een taal is per definitie regulier als het een lineaire grammatica heeft
Copy accepteert alle strings die gemaakt zijn uit 2 opvolgende exacte kopieën van een string over het alfabet (niet regulier, niet CF)
Mirror geeft de reverse van de string die als input gegeven is (als s=01, dan ss^r=0110) (niet regulier, WEL CF)
Als een string niet gebouwd kan worden dmv het hebben van nested dependencies, dan is het niet CF

⑧
I
Center embedding laat zien dat natuurlijke talen niet regulier (WEL CF) zijn dmv patroon: (D N)^i V^i
Center embedding is niet mogelijk in reguliere talen maar wel in natuurlijke talen
Natuurlijke talen zijn productief en in principe oneindig; menselijk vermogen zoals geheugen zijn het limiet, de talige kennis niet
↓ Bij aanwezigheid van kruisende afhankelijkheden is een taal niet CF (bv. Copy-taal)
Als A CF is en B regulier dan is A intersect B context-vrij (B is sws een subset van A omdat alle reguliere talen CF zijn)
Ef
Dus de intersect van een niet-CF met een reguliere taal is niet CF g

Info over het wel of niet regulier/CF zijn van talen is belangrijk voor taal-analyse & helpt bij begrijpen en onderscheiden van cognitief- en
communicatie-vermogen van mensen en dieren
Uniek aan mensentaal: displacement(niet-actuele zaken), compositionaliteit, woordenschat, productiviteit(oneindige combinatorische
mogelijkheden met discrete delen), structuur(hoge structurele complexiteit, inherent aan productiviteit-systeem)
Regulier: (ab)+ (deze konden apen wel leren), Niet-regulier: (a^n b^n) (wel CF), is ook recursief (successieve insertie van AXB)

Turing machine isl equivalent aan een PDA met 2 stapels: leest/schrijft/richting
⑭ Configuratie: (q, (T\{ })*, T, ((T\{ })*) wil zeggen (toestand, rijtje links vd kop(incl kop), positie kop, rijtje rechts vd kop)
1-stap derivatie noteer je als (q1, e, , aabb) =>m (q2, e, a, abb) & derivatie als (q1, e, , aabb) =>*m (q5, $a, b, #) ->transitieve reflexieve sluiting
v. 1-stap derivatie
Taal is beslisbaar als er een Turing machine is die alle w in E* (L) accepteert en alle w die niet in L zitten afwijst
Taal is semi-beslisbaar (RE) als er een Turing machine is die alle w in E* (L) accepteert en alle w die niet in L zitten niet accepteert (stopt/looped)
Er zijn semi-beslisbare talen die niet beslisbaar zijn (dit is te bewijzen dmv het stop-probleem, slide 18)
Elke taal geaccepteerd door een LBA is beslisbaar
Een CSG is een soort reguliere CFG met minder restricties
Enige restrictie CSG: rechts v/e productieregel moet altijd langer zijn dan links, rechts mag het start-symbool niet voorkomen en S->e mag niet
Bach-taal B={o in {0,1,2}* | o bevat evenveel 0,1,2} is niet CF (center embedding) maar wel CS (crossing dependencies)

3 El
leven ABAB znieuwe
bigrammen (AA , BB) leven AABB nieuwe
bigram (BA)
testen AABB testen ABAB

,als buffer leeg voordat stack backtrack
leegis
:
4
non-projectief
3 5 =

↳ dus
L =
problem voor
top down ligt fussen
hoofd-dependent ,
er
zon een pad moeten
zijn van 3 4

Een boom is een drietal <V,E,r> waarbij <verz knopen, verz verbindingen, wortel> met een labeling l
Voor r zijn er geen inkomende verbindingen, elke ander knoop heeft precies 1 inkomende verbinding en voor elke knoop is er een (in)direct pad
dat van r naar die knoop leidt
Adjunctie (plaatsvervanging met toevoeging) wordt toegestaan als T1, l1 een knoop v heeft en T2, l2 een blad f heeft zodanig dat l1(v)=l2(f)=l2(r)
Substitutie (vervanging) (van T2 in T1) wordt toegestaan als T1,l1 een blad v heeft en T2,l2 zo is dat l1(v)=l2(r)
Een TAG (tree-adjoining-grammar) manipuleert bomen ipv rijtjes en is mild-CS (CF ⊂ mild-CS ⊂ CS)
Natuurlijke talen zijn ten minste CF en maximaal CS (mild-CS, met als formele grammatica: TAG)

Parseren: nodig voor interpretatie v natuurlijke talen, maakt interpretatie v Python mogelijk voor een computer en het bestuderen ervan helpt ons
begrijpen wat talige kennis bevat
⑫ Left-recursion: productie-type waarbij productie links en rechts dezelfde categorie bevat (A->A a) Voor top-down kan dit leiden tot non-terminatie
Top-down parsing: welk rijtje zou de grammatica kunnen genereren?
LL-parsing (links->rechts, left-most derivative): Begin met een stack met $ erop, plaats start-knoop op de stack
Herhaal: Expand; neem bovenste element a v/d stack en vervang het met B als a->B een productie-regel is, Scan; neem bovenste element a v/d
stack en vervang het niet indien a het volgende element in de input is. Lees a dan, Backtrack; terug naar laatste keuze-punt
Totdat: stack alleen bestaat uit $ en er niks meer te lezen valt
Bottom-up parsing: welk rijtje is herkenbaar door de grammatica?
LR-parsing (links->rechts, right-most derivatie): Begin met lege stack
Herhaal: Shift; neem symbool v/d input en plaats boven op de stack, Reduce; vind een rijtje a boven op de stack en vervang X als X->a een
productieregel is, Backtrack; terug naar laatste keuze-punt
Totdat: stack alleen uit S bestaat en er niks meer te lezen valt

Vrije woordvolgorde leidt tot veel grammaticale regels; een CFG moet voor iedere volgorde van argumenten nieuwe grammaticaregels bepalen
⑬ Binnen elk constituent is 1 woord het belangrijkste: het hoofd (alle andere elementen in het constituent zijn dependenten v/h hoofd)
Dependentiegrammatica geeft aan welk hoofd-dependent relaties er zijn (dependenten volgen het hoofd, dus komen in een boom eronder &
pijlen gaan van hoofd -> dependent)
Voor een dependentieboom gelden precies dezelfde verzamelingen, label definite en regels als voor een boom (zie eerste 2 regels v deze blz)
Een dependentieboom (met pijltjes) correspondeert met de equivalentie-klasse van constituentiebomen (zoals een parseerboom)
Een boog tussen H en D is projectief als er (in)direct een pad is van H naar alle woorden tussen H en D
Een structuur is projectief desda alle bogen projectief zijn
Non-projectieve structuren hebben geen corresponderende structuur in constituentiebomen & geen corresponderende structuren gegenereerd
door CFG
De dependentierelatie tussen woorden binnen een boog bepalen of een non-projectieve boog acceptabel (grammaticaal) is
Arc-Standard: Parseren in een dependentiegrammatica (kan niet met non-projectieve structuren): Begin met een stack met ROOT
Herhaal: Left-Arc(1e woord stack); als a boven op de stack is, gevolgd door b en a het hoofd is en b het dependent, noteer relatie en verwijder b
Right-Arc(2e woord stack); als b boven op de stack is, gevolg door a en a is het hoofd en b het dependent en b heeft geen andere dependentie,
noteer relatie en verwijder b, Shift; Neem het woord v/d input en plaats het boven op de stack
Totdat: stack bestaat alleen uit ROOT en er valt niks meer te lezen (Accept)
Left- en Right-Arc zijn reduce operaties: combineren van elementen op de stack
n
Aantal stappen bij parseren met dependentiegrammatica: 2 waar n het aantal woorden is (groei is lineair, sneller dan CYK ((n /2)+(n/2))
2

CYK is dus handig bij korte zinnen
In arc-standard worden dependenten verwijderd van de stack wanneer hun hoofd aanwezig is
In arc-eager mogen woorden al zo vroeg mogelijk worden gekoppeld aan hun hoofden (al voordat alle andere dependenten aanwezig zijn)
Een dependentieboom heeft n-1 dependentierelaties
Left-Arc voegt bij arc-eager een relatie toe en popt de stack terwijl Left-Arc bij arc-standard niet popt
Blad in een dependentieboom is een woord zonder uitgaande pijl
Naieve definitie van kans: A/S (gebeurtenis/uitkomstenruimte)-> Werkt alleen als uitkomsten dezelfde kans hebben en uitkomstenruimte eindig is
⑭ Kans/probabiliteit = som van kans afzonderlijke gebeurtenissen = 1
Frequentische interpretatie: P=hoe vaak we gebeurtenis zouden zien als we een kansexperiment oneindig zouden herhalen
Bayesiaanse interpretatie: P=hoe sterk we geloven dat gebeurtenis zou plaatsvinden
Voorwaardelijke kans: P(A|B)=kans dat A plaatsvindt gegeven dat B plaatsvindt= rijtjes BA/B (als B>0)
P(w(t+1)=B | w(t)=A) noemen we een bigram (ab/a) gegeven een a, kans dat een b volgt
P(w(t-1)=B | w(t)=A) (ba/a) gegeven een a, kans dat een b vooraf gaat
In ambigue zinnen kunnen we de dominante representatie vinden als we grammatica’s verbinden met kans
PCFG: <E,N,S,R,P> (terminalen, non-terminalen, start, producties, probabiliteit P:R->[0,1]) Waarbij som van een P altijd 1 is
Beste parse van een zin = boom met de hoogste probabiliteit
Waarschijnlijkheid v/e zin = som alle mogelijke parseerbomen (bij een niet-ambigue zin is de kans v/d zin gewoon de kans van de enige boom)
Kans productieregel is afhankelijk v woorden in zinnen
Ouder-annotatie: zet ouder v/d knoop bij de non-terminal & Hoofd-annotatie: zet hoofd v/d knoop bij de non-terminal
P(A U B) = P(A) + P(B) - P(A intersect B)
Onafhankelijke gebeurtenis: Voor P(X) > 0, als P(Y|X) = P(Y), dan zijn voorkomen van X en voorkomen van Y volgend op X onafh. gebeurtenissen

pomplemma voor (ftalent pCFG's kennen soms
dezelfde wssheid toe
verschillende boment meest te
parseven nog (LR/L) Relaties (tr sym refl
, , ,
aan
moeilijk was

Kiezen

, * =
Of

? = 0/l

+ = It

< ...
] ...
=

symbolen die niet
gebruikt mogen worden
[a-2] Vd
een
symbolentussen a enz
=

~

begin regel / The/ vindt alleen The's
= : can
begin
S / $/ vindt
=
einde
regel dogl .
: alleen
dogs aan eind

&
woordgrens (Lbcatlb matched alleen'sat' losse underdelen)
geen
=
en

& : lees het
volgende symbool als symbool

b"a
+
& <
/ a, b)a > b] niet
regulier want b aP niet pompbaar P
y 2

3 +'aP+, bP
P +2
qP+ zitten niet in X

Irk p

|
xy1 =>
P

xy2
r =

VieA
xyz e/v
I .

3
Symmetrie als(x *
,
y) (y x)
,

Transiviteit Cls(x y)n
,
Cls(y , z) * (x , z) If premis false >
-
conclusie
altijd waar

Reflexiviteit (x X) moet
, voor XXEX
exp bovenste el stack als B
Top down $""S$
a-
a en
vervang
:

,
scan : veruang als el Stack overeenkomt met input
.

~ neem symbol van input en plaats op stack
LR
Bottom up rijfje-input , Shift-Reduce vervang symbool in stack met
:

LHS
regel

, Voorbereiding lecture 1
Linguistics: scientific study of human language
Linguist: scientist who investigates human language (structure, use, history, place in society
Theory of grammar: mental representation of linguistic knowledge
Theoretical/Generative linguistics has its basis views put forth by Chomsky -> Major aim was to characterise
the nature of human linguistic knowledge (competence)
Competence: explain or account for what speakers know which permits them to speak and comprehend
speech or sign
Performance: production and comprehension of speech
Descriptive linguistics provides analyses of the grammars of languages
Historical linguistics is concerned with a theory of language change, why and how they develop
Comparative method: is used to compare languages in the attempt to determine which languages are related
& establish families of languages and their roots
Anthropological/Ethno-linguistics and sociolinguistics focus on language as part of culture and society
Dialectology investigates how factors fragment one language into many
Sociolinguistics and applied linguistics are interested in language planning, literacy, bilingualism and second
language acquisiton
Computational linguistics is concerned with natural language computer applications & has the goal of
modelling language as a cognitive system
Mathematical linguistics studies formal and mathematical properties of language
Pragmatics studies language in context and the influence of situation on meaning
Neurolinguistics is concerned with the biological basis of language acquisition & development in the brain-
mind-language interface
Psycholinguistics is concerned with linguistic performance, production and comprehension of speech —>
Child language acquisition; how children acquire complex grammar which underlies language use

↑ Sapir, concerned with developing a general theory of language, was a mentalist and believed that any valid
linguistic theory must account for the mental representation of linguistic knowledge
Bloomfield was a behaviorist, a view that precludes any concern for mental representation of language/mind
Theory of grammar; synctatic structures: concerned with biological basis for acquisition, representation and
use of human language & the universal principles which constrain the class of all languages

Competence: What constitutes knowledge of language ?
2
1 Acquisition: How is knowledge of language acquired ?
.

Performance/ Language processing: How is knowledge of language put to use ?

3
1
.

Discussion of the nature/characteristics of language should be interpreted as referring to both spoken and
signed languages
A grammar: the linguistic knowledge as represented in the speakers mind
Linguistic theory is concerned with revealing the nature of the mental grammar which represents speakers’
knowledge of their language
Each kind of linguistic knowledge constitutes a component of mental grammar -> Here we don’t speak of
conscious knowledge!

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper Alysa3. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €9,43. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 66184 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis

Samenvatting

Samenvatting Formele en Natuurlijke talen Eindtentamen

Document informatie

Onderwerpen

Geschreven voor

Verkoper

Ontvangen beoordelingen

Voorbeeld van de inhoud