Studied by 47 peopleNP-complete problems
A set of problems where no efficient solution has been found
Hamilton Path
a path that visits all the vertices of a connected graph once and only once
Euler Path
a path that travels along each edge of a graph once and only once
k-coloring
a simple graph G is an assignment of one of k colours to each vertex so that no two adjacent vertices are assigned the same colour.
Clique
a subset V ′ of V such that every pair of vertices in V ′ are adjacent (a complete subgraph)
Vertex Cover
a subset V ′ of V such that every edge has at least one endpoint in V ′
Dominating Set
a subset V ′ of V such that every vertex in V is either in V′ or is adjacent to a vertex in V ′
Independent set
a subset V ′ of V such that each edge e ∈ E is adjacent to at most one vertex in V ′
angled brackets 〈 〉
denote a string encoding of an object.
Automaton
A machine that performs a function according to a predetermined set of coded instructions.
A finite (state) automaton is a 5-tuple M = (Q, Σ, δ, q0, F ) where
Q: a finite set of states Σ: a finite input alphabet δ : Q × Σ → Q a transition function q0 ∈ Q: the initial or start state F ⊆ Q: the set of accept (final) states
We say that an input string α is accepted by a deterministic finite state automaton M if
The input string starts from q0 and ends at an accept state.
The language recognized by a (D/N) finite automaton M , denoted L(M) is
the set of all strings that are accepted by M
Every state in a FSA must have a transition for each element of Σ. (a) True (b) False
(a) True
A language is regular if and only if
Some NFA recognizes it
A non-deterministic finite automaton (NFA) is a 5-tuple M = (Q, Σ, δ, q0, F ) where
Q: a finite set of states Σ: a finite input alphabet δ : Q × Σ → P(Q) is a transition function q0 ∈ Q: called the initial or start state F ⊆ Q: the set of accept (final) states
An NFA is said to accept an input string x, if
there exists a final state that can be obtained from the start state q0 using x.
If the language L is recognized by some NFA M0, then it can also be recognized by some deterministic FA M1 (a) True (b) False
(a) True
What are the regular operations
Union, concatenation, kleene star
What is meant by 'closure properties' of regular operations
Performing one of these operations means that the resultant will be closed, in other words, will remain regular if and only if every language in the operation was also regular
R*
0 or more concatenations of k R's with each other
R+
1 or more concatenations of k R's with each other
(a ∪ b)∗ = Σ∗
All words
b∗∅
concatenation with empty set is empty
∅∗
= {e}
(a ∪ b)∗b
all strings ending with b
(a ∪ b)(a ∪ b)a(a ∪ b)∗
all strings where the third character is a
b∗(ab∗ab∗)∗ab∗
{w | w has an odd number of a's}
(e ∪ 1)(01)∗(e ∪ 0)
a regular expression for the language consisting of all binary strings with alternating 0's and 1's
Generalized nondeterministic finite automaton
an NFA where the transition arcs may also have regular expressions as labels in addition to the normal alphabet symbols and empty string
A language A is regular if and only if some regular expression R describes it. (a) True (b) False
(a) True
Pumping Lemma
If A is a regular language, then there is a number p where, if s is any string in A of length at least p, then s may be divided into 3 pieces s = xyz, satisfying:
for each i ≥ 0, xy^iz ∈ A,
|y| > 0, and
|xy| ≤ p. p is called the pumping length.
What does the pumping lemma theorem reflect
Given a long enough word in a regular language A, we can take some specific substring y and repeat it an arbitrary number of times to get a longer word that is also in A
for each i ≥ 0, xyiz ∈ A
Since s ends in an accept state (it is in A), then repeating the y multiple times will take us to the same accept state and thus xy^iz ∈ A
|y| > 0
Clearly y must follow at least one transition if the state r is repeated
|xy| ≤ p
Since we chose r to be the first repeated state, the length of xy cannot be longer than p, since no other states are repeated
What is the p in the pumping lemma meant to demonstrate?
If p is equal to the number of states in the equivalent DFA to the language then, for all strings s in the language where |s| >= p, there must be some repeated state for that string to be accepted. Meaning, we should be able to 'pump' this repeated state and still have a string that is in the language.
CFG terminals
the input alphabet, usually lower case letters or numbers
CFG variables
usually represented by capital letters: A, B, C . . .
derivation
The sequence of substitutions to obtain a string in a CFG
language of the grammar
All strings generated by a derivation in a CFG
context-free language
Any language that can be generated by some context-free grammar
non-context-free grammar
each production rule is a NOT single variable
A context-free grammar is a 4-tuple (V, Σ, R, S)
V is a finite set of variables
Σ is a finite set of terminals
R is a finite set of rules with each rule being a variable (on the left) and a string of terminals and variables (on the right)
S ∈ V the start variable
CFL's are closed under which operations
The regular operations: union, concatenation, star
A pushdown automata is a 6-tuple (Q, Σ, Γ, δ, q0, F )
Q is a finite set of states Σ is a finite input alphabet Γ is the finite stack alphabet δ : Q × Σe × Γe → P(Q × Γe) q0 ∈ Q is the start state F ⊆ Q is the set of accept states
A language is context-free if and only if
some pushdown automaton recognizes it
Note
Flashcard