Language & Computation Flashcards
TW3V19002 UU (196 cards)
1
Q
Formal automata
A
Models with step by step computation.
2
Q
Formal grammars
A
Recipes to create patterns and sentences.
3
Q
List the four language types from Chomsky’s hierarchy from simplest to most complicated:
A
- Regular
- Context-free
- Context-sensitive
- Recursively enumerable
4
Q
List the four automata from Chomsky’s hierachy from simplest to most complicated:
A
- Finite state
- Pushdown
- Linearly bounded
- Turing machine
5
Q
Describe the language and automaton of the type 3 grammar in Chomsky’s hiearchy:
A
Type 3 grammar has a regular language and a finite state automaton.
6
Q
Describe the language and automaton of the type 2 grammar in Chomsky’s hiearchy:
A
Type 2 grammar has a context-free language and a pushdown automaton.
7
Q
Describe the language and automaton of the type 1 grammar in Chomsky’s hiearchy:
A
Type 1 grammar has a context-sensitive language and a linearly bounded automaton.
8
Q
Describe the language and automaton of the type 0 grammar in Chomsky’s hiearchy:
A
Type 0 grammar has a recursively enumerable language and a turing machine.
9
Q
What is the trade-off found in Chomsky’s hierarchy concerned with?
A
Expressivity and complexity.
10
Q
Greater expressivity requires…
A
greater complexity.
11
Q
What does a(n English) syllable consist of?
A
The onset, the nucleus and the coda.
12
Q
Concatenation
A
One symbol after another that form a sequence.
13
Q
In what three ways can you make combinations in the formal grammar RegEx?
A
- Concatenation
- Choice
- Repetition
14
Q
FSA
A
finite state automaton
15
Q
What is the problem for finite automata on palindroms?
A
The computational power is not enough, it does not have any memory.
16
Q
How is the stack of a pushdown automaton organized?
A
First In, Last Out
17
Q
FILO
A
first in, last out
18
Q
PDA
A
Pushdown automaton
19
Q
Which grammar types have polynomial complexity?
A
Type 3 and type 2.
20
Q
FA
A
finite automaton
21
Q
The program (in FA/FSA)
A
The finite set of instructions for changing from state to state while reading.
22
Q
Deterministic FA
A
FAs where there is only one instruction for each combination of state and read symbol.
23
Q
State diagram
A
A representation for an FA in which each state is a circle and the instructions are arrows.
24
Q
Give the formal definition of a deterministic FA:
A
A deterministic FA M is a quintuple [K, Sigma, delta, q0, F] with
K = finite set of states,
Sigma = finite set (the alphabet),
Q0 E K = the initial state,
F [subset] K = set of final states,
delta = f: K x Sigma -> K (the transition function).
25
Give the formal definition of a situation in a deterministic FA:
Given a dFA M = [K, Sigma, d, q0, F], a situation of M is a triple (x,q,y) where q E k and x,y E Sigma^x.
26
Lemmatization
The task of determining that two words have the same root
27
Stemming
A simple form of lemmatization where suffixes are stripped from the end of the word.
28
Sentence segmentation
Breaking up a text into individual sentences using cues like periods or exclamation points.
29
Concatenation
Putting characters in sequence.
30
What is the hierachy in regex?
1. Parentheses ()
2. Counters *, +, ? and {}
3. Sequences and anchors ^, $
4. Disjunction |
31
What is precision?
Minimise false positivies.
32
Recall
Minimize false negatives
33
Regex: find a pattern that contains either t or T.
/[tT]/
34
Regex: find a pattern that matches 'tea' or 'Tea'.
/[tT]ea/
35
Regex: find any number in range 2, 3, 4, or 5.
/[2-5]/
36
Regex: find any letter in range c, d, e, f, g, h.
/[c-h]/
37
Regex: find any upper case letter.
/[A-Z]/
38
Regex: find any lowercase letter.
/[a-z]/
39
Regex: find any single digit.
/[0-9]/
40
Regex: find any single character, except f.
/[^f]/
41
Regex: find any single character, but neither a nor A.
/[^aA]/
42
Regex: find either f or ^.
/[f^]/
43
Regex: find the pattern c^f.
/c^f/
44
Regex: find 'horse' or 'horses'.
/horses?/
45
Regex: what does ? mean?
The preceding character or nothing.
46
Regex; what does * mean?
Zero or unbounded amount of the previous character
47
/aa*/ (regex)
Any string of one a followed by zero or more a's
48
What does . mean in regex?
It's a wildcard, any single character.
49
How do you search for the start of a line with regex?
/^/
50
How do you search for the end of a line with regex?
$
51
How do you search for a word boundary in regex?
\b
52
How do you search for a non-word boundary in regex?
\B
53
How do you use the . as an actual dot in regex?
\.
54
How do you show disjunction in regex?
|
55
How do you search for either 'cat' or 'dog' in regex?
/cat|dog/
56
When do you use parentheses in regex?
When you want the sequence to act as a single character to the operators around it.
57
How do you look for as little text as possible when using a Kleene star?
*?
58
How do you look for as little text as possible when using a Kleene plus in regex?
+?
59
How do you look for exactly x occurrences of the previous character?
/character{x}/
60
What is a shortcut in regex for any alphanumeric/underscore character?
\w
61
What is a shortcut in regex for any digit?
\d
62
Give the shortcut in regex for any non-digit:
\D
63
Give the shortcut in regex for any non-alphanumeric:
\W
64
Give the shortcut to look for a whitespace in regex:
\s
65
Give the shortcut in regex for a non-whitespace:
\S
66
How do you search for a - b occurrences of the previous char in regex?
/char{a-b}/
67
How do you look for at least n occurrences of the previous in regex?
/char{n,}/
68
How do you look for up to m occurrences of the previous in regex?
/char{,m}/
69
How do you search for the asterisk in regex?
\*
70
How do you search for the question mark in regex?
\?
71
How do you find a newline in regex?
\n
72
How do you find a tab in regex?
\t
73
When do you use \1 in regex?
To refer to whatever string matched the first item in parentheses.
74
What do you use when you don't want to capture the group between parentheses in regex?
(?:pattern)
75
Fragment
broken-off word
76
Lemma
Set of lexical forms having the same stem, pos and word sense.
77
Word form
The full inflected or derived form of the word.
78
Types (in corpora)
The number of distinct words in a corpus.
79
Tokens (in corpora)
Total number N of running words
80
Heardan's law =
Heap's law
81
Heap's law
The relationship between the number of types |V| and number of tokens N.
|V| = k * N^beta
82
What 3 things are commonly applied when normalizing text?
1. Tokenizing words
2. Normalizing word formats
3. Segmenting sentences
83
Named entity recognition
The task of detecting names, dates and organization.
84
Clitic
Part of a word that can't stand on its own, but has be attached to another word.
85
What two parts do most tokenization schemes consist of?
1. Token learner
2. Token segmenter
86
What does a token learner do in tokenization?
It takes the raw training corpus and induces vocabulary.
87
What does a token segmenter do in tokenization?
It takes a raw test sentence and segments it into tokens in vocabulary (set of all individual characters). Chooses the 2 most frequent adjacent and adds the merged symbol to vocabulary, changes all occurrences in corpus to merged symbol. Continues until k new tokens have been created.
88
Coreference task
Task of deciding whether two strings refer to the same entity.
89
Alignment
Given two sequences, an alignment is a correspondence between substrings of the two sequences.
90
Levenshtein distance
The simplest weighting factor in which each of the 3 operations has a cost of 1.
91
By what 3 atomic shapes are regular expressions defined?
1. a for any alphabet symbol a in Sigma (recognizes a)
2. Epsilon (recognizes empty string)
3. Empty set (recognizes no string)
92
By what 3 operations are regular expressions defined?
1. Choice (U symbol)
2. Concatenation
3. Repetition
93
What does + mean in regex?
the previous character one or more times/
94
How do you search for words with an even number of symbols in regex?
(..)*
95
In what automaton is it allowed to move states without reading a symbol?
In non-deterministic FSAs
96
When is a string accepted by a non-deterministic FSA?
Iff there is some path through the state diagram which begins in the initial state, reads the entire input and ends in the final state.
97
NFA
non-deterministic finite automaton
98
What allows for non-transitivity in NFAs?
The fact that delta is a relation and not a function.
99
What is the relation between DFAs and NFAs?
1. DFAs are a proper subclass of NFAs.
2. NFAs accept exactly the same class of languages as DFAs.
100
Is the empty set a regular language?
Yes.
101
If A and B are regular languages, so are
The union of A and B
AB
102
What is the use of the pumping lemma?
Showing that certain languages are not fal's. May not prove useful in other cases even though the language in question is not a fal.
103
Pumping lemma (theorem in their book) for FALs:
If L is an infinite fal over alphabet sigma, then there are strings x, y and z in sigma* such that y is not e and x*(y^n)z is in L for all n>=0.
104
What are the two types of pronominal subject doubling?
1. Clitic doubling
2. Topic doubling
105
Where does clitic doubling occur?
In subclauses and inverted main clauses.
106
Where does topic doubling occur?
In subject-initial main clauses.
107
Clitic doubled subject
A subject consisting of a clitic and a strong pronoun, taken as one merged DP.
108
Topic doubled subject
A subject that involves a non-clitic pronoun doubled by a strong pronoun.
109
Tripling
When a strong pronoun is both part of clitic doubling and topic doubling in one sentence.
110
How do you make a DFA out of a NFA?
1. The DFA set of states is the power set of the NFA states.
2. Initital states = readable from q0 without any input.
3. Final state = any set of states that contains a final state of the NFA.
4. Transition function; what set can be reached from this state?
111
What is the complexity of DFAs?
linear, does not depend on the size of the automaton.
112
What is the distinguishing factor between regular languages and context-free languages?
self-embedding
113
What are the two operations on a stack?
1. Push
2. Pop
114
Push operation on stack
Add something to the top of the stack
115
Pop operation on stack
Remove something from the top of the stack
116
The PDA transition function delta is a function such that...
The input is a 3-tuple (current state, input symbol, stack symbol to access/pop).
The output is a set of 2-tuples (next state, stack symbol/string to write/push).
117
Name the two main strategies of procesing context-free languages:
1. Top-down
2. Bottom-up
118
How does top-down processing of CFLs work?
CFG: build a tree from root to leaves
PDA: read in epsilon and push symbols unto the stack, then read input symbols and pop symbols from the stack.
119
How does bottom-up processing work for CFLs?
CFG: build a tree from leaves to root.
PDA: Read input symbols and push symbols onto the stack, then read in epsilon and pop symbols from stack.
120
What two examples were mentioned in lecture that are impossible to capture with CFGs/PDAs?
1. a^n b^n c^n
2. w^2
121
Can all regular languages be modelled with a PDA?
Yes
122
Are all context-free languages regular?
No
123
Can all context-free languages be modelled with an FSA?
No
124
When does a PDA accept a string?
1. The entire input has been read
2. The PDA is in a final state
3. The stack is empty
125
When is a PDA non-deterministic?
If there is more than one move available to the automaton in certain situations.
126
Can deterministic PDAs have no move available for a situation?
Yes, it is only required that in no situation there is more than one move.
127
Do non-deterministic PDAs accept exactly the languages generated by context-free grammars?
Yes.
128
Are natural languages context-free?
No, because cross-serial dependency.
129
PaQu (abbreviation)
Parse and Query application
130
What is the Parse and Query application (PaQu)?
A web application for searching in Dutch treebanks and for analysing search results.
131
Treebank
A text corpus in which each sentence has been assigned a syntactic structure.
132
What part of natural language is a regular language mostly used for?
Phonology and most morphology.
133
What part of natural language is a finite dictionary mostly used for?
Lexicon
134
What part of natural language is a context-free grammar mostly used for?
Some syntax.
135
What part of natural language is a contxt-sensitive grammar mostly used for?
Syntax
136
What formal grammar can you use the best if you want to describe syntax?
Context-free or context-sensitive.
137
What formal grammar can you use best if you want to describe phonology or morphology?
Regular language
138
When is a context-free grammar G ambiguous?
If at least one word has multiple left-most derivations or multiple trees.
139
When is a language L ambiguous?
If all grammars that generate L are ambiguous.
140
If every grammar you can possibly create for the language creates two or more trees for some word,...
you have an ambiguous language.
141
Can regular languages be represented with CFGs?
Yes
142
A grammar is regular if and only if in every rule A -> u, ...
u has no more than one nonterminal symbol,
AND
this nonterminal symbol is always at the beginning or always at the end of u.
143
A CFG is self-embedding if...
there is a nonterminal A that can be rewritten to itself with non-empty strings before and after:
A -> uAv with u and v are both non-empty
144
What distinguishes regular languages from context-free languages?
Self-embedding:
every self-embedding language is non-regular and every non-regular CFL is self-embedding.
145
What are the two main strategies of processing (parsing) CFLs?
1. Top-down (root to leaves)
2. Bottom-up (leaves to root)
146
Why is it impossible to get a^nb^nc^n pattern with CFG?
This pattern requires a memory beyond FILO.
147
What does P(w|h) denote?
The probability that word w will occur given word h.
148
Markov assumption
The assumption that the probability of a word depends only on the previous word.
149
MLE (abbreviation)
Maximum likelihood estimation
150
Relative frequency
The observed frequency of a particular sequence divided by the observed frequency of a prefix.
151
Extrinsic evaluation
Evaluation where the language model is embedded in an application and it is measured how the application improves.
152
Intrinsic evaluation
Evaluation where the quality of a language model is measured independently of any application, using a test and training set.
153
Perplexity
A probability-based metric for accuracy.
154
What is the usual division between training, development and test sets?
80% training, 10% devset and 10% testing.
155
PPL (abbreviation)
Perplexity
156
Minimizing perplexity is equivalent to...
maximizing the test set probability according to the language model.
157
What is the branching factor of a language?
The number of possible next words that can folow any word.
158
What is a requirement for comparing the perplexity of two language models?
The models need to be using identical vocabularies.
159
For what 2 reasons are zero probabilities a problem?
1. Problem of sparsity: there are always some valid sequences missing from corpus.
2. Can't compute perplexity, then we would need to divide by 0.
160
OOV (abbreviation)
out of vocabulary
161
OOV rate
The percentage of OOV words that appear in the test set.
162
Laplace smoothing
A type of smoothing where all n-gram counts are raised by 1,
163
What smoothing methods require discounting to create a probability distribution?
Back off and interpolation.
164
How are regular languages defined?
Through FSAs and regular expressions.
165
All strictly local languages are...
regular.
166
Strictly local language
A regular language where all dependencies fit into a finite (max n ) sliding window of analysis.
167
How do you ensure that dependence of a symbol on other symbols is at a distance =< n in a strictly local FSA?
Have exactly one state for every sequence of up to n-1 symbols + a sink state. Every state is only reachable through one particular sequence of symbols.
168
Formal grammar (non-mathematical definition)
A deductive system of axioms and rules of inference, which generates the sentences of a language as its theorems.
169
What two types of alphabets do formal grammars use?
A terminal alphabet and a non-terminal alphabet.
170
What is the relation between the two alphabets used by a formal grammar?
They are disjoint (the terminal and the non-terminal alphabet).
171
What is a constraint on the left side of a rule in a formal grammar?
The string on the left side of a rule cannot consist entirely of terminal symbols.
172
What is the form of each rule in a type 1 formal grammar?
alpha A beta -> alpha psi beta
With alpha, psi, beta = arbitrary strings over the union of terminal and non-terminal symbols and A= non-terminal symbol.
173
What is the form of each rule in a type 2 formal grammar?
A -> psi
With alpha, psi, beta = arbitrary strings over the union of terminal and non-terminal symbols and A= non-terminal symbol.
174
What is the form of each rule in a type 3 formal grammar?
A -> x B or A -> x
With alpha, psi, beta = arbitrary strings over the union of terminal and non-terminal symbols and A= non-terminal symbol.
175
The type 3 languages are properly included in...
The type 2 languages.
176
Type 2 languages not containing the empty string are properly included in...
the type 1 languages
177
The type 1 languages are properly included in...
the type 0 languages.
178
How can we prove that English is not a natural language?
By using the pumping theorem and the fact that regular languages are closed under intersection.
179
FAL (abbreviation)
Finite automaton language
180
What do we do if we can't model a natural language with a regular language?
We go up one level of complexity: to context-free languages (CFL).
181
Under what operations are regular languages closed?
1. Boolean operations
2. Union
3. Intersection
4. Complement
5. Difference
182
What operations on strings in a regular language yield another regular language?
1. Concatenation
2. Repetition
3. Choice
183
How do you model the expression 'all X are Y' using regex?
Given alphabet {0,1} with
1= X that is Y and
0= X that is not Y.
/1*/
there are only 1s, Xs that are Y
184
How do you model the expression 'Some X is Y' using regex over an alphabet {0,1} with 1= X that is Y and 0= X that is not Y?
/.*1*./
There is at least one 1 among all Xs.
185
How do you model the expression 'No X is Y' using regex over alphabet {0,1} with 1= X that is Y and 0= X that is not Y?
/0*/
There are only 0s, Xs that are not Y.
186
How do you model the expression 'Not all X are Y' using regex over the alphabet {0,1} with 1=X that is Y and 0= X that is not Y?
/.*0*./
There is at least one 0 ampng all Xs.
187
Why are we unable to model the expression 'There are as many 1s as 0s' with regex?
You need to remember how many 0s and 1s you've seen in order to check this, so it requires some form of memory.
188
Why can't we model the pattern a^nb^n using regex?
It requires some type of memory: we need to have seen as many a's as b's at the end of reading the string.
189
What does this pattern consist of: (ww)^R
R = reverse, so if ww = ab then the pattern will be abba.
190
What four elements does a context-free grammar (CFG) consist of?
1. Alphabet N of nonterminal symbols.
2. Alphabet Sigma of terminal symbols.
3. Set of rules P, pairs of a nonterminal symbol and string of terminal/nonterminal symbols.
4. Start symbol S, element in N.
191
How do we define a language of a context-free grammar (CFG)?
The set of all strings of terminal symbols that can be derived from the start symbol, S, in zero or more steps.
192
When do we speak of leftmost derivation of S -> w?
If only the leftmost auciliary symbol is rewritten at every step.
193
Every leftmost derivation corresponds to exactly one...
tree diagram
194
When is a context-free grammar (CFG) self-embedding?
If there is a nonterminal A that can be rewritten to itself with non-empty strings before and after.
195
When is a language self-embedding?
If all grammars that describe this language are self-embedding.
196
What type of grammar allows a nonterminal X to be rewritten to aXb, so can match an 'a' to a 'b' at an arbitrary distance?
A context-free grammar (CFG)
