Studied by 47 People

0.0(0)

get a hint

hint

Tags & Description

New cards47

Still learning0

Almost done0

Mastered0

47 Terms

New cards

NP-complete problems

A set of problems where no efficient solution has been found

New cards

New cards

Hamilton Path

a path that visits all the vertices of a connected graph once and only once

New cards

New cards

Euler Path

a path that travels along each edge of a graph once and only once

New cards

New cards

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.

New cards

New cards

Clique

a subset V ′ of V such that every pair of vertices in V ′ are adjacent (a complete subgraph)

New cards

New cards

Vertex Cover

a subset V ′ of V such that every edge has at least one endpoint in V ′

New cards

New cards

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 ′

New cards

New cards

Independent set

a subset V ′ of V such that each edge e ∈ E is adjacent to at most one vertex in V ′

New cards

New cards

angled brackets 〈 〉

denote a string encoding of an object.

New cards

New cards

Automaton

A machine that performs a function according to a predetermined set of coded instructions.

New cards

New cards

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

New cards

New cards

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.

New cards

New cards

The language recognized by a (D/N) finite automaton M , denoted L(M) is

the set of all strings that are accepted by M

New cards

New cards

Every state in a FSA must have a transition for each element of Σ. (a) True (b) False

(a) True

New cards

New cards

A language is regular if and only if

Some NFA recognizes it

New cards

New cards

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

New cards

New cards

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.

New cards

New cards

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

New cards

New cards

What are the regular operations

Union, concatenation, kleene star

New cards

New cards

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

New cards

New cards

R*

0 or more concatenations of k R's with each other

New cards

New cards

R+

1 or more concatenations of k R's with each other

New cards

New cards

(a ∪ b)∗ = Σ∗

All words

New cards

New cards

b∗∅

concatenation with empty set is empty

New cards

New cards

∅∗

= {e}

New cards

New cards

(a ∪ b)∗b

all strings ending with b

New cards

New cards

(a ∪ b)(a ∪ b)a(a ∪ b)∗

all strings where the third character is a

New cards

New cards

b∗(ab∗ab∗)∗ab∗

{w | w has an odd number of a's}

New cards

New cards

(e ∪ 1)(01)∗(e ∪ 0)

a regular expression for the language consisting of all binary strings with alternating 0's and 1's

New cards

New cards

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

New cards

New cards

A language A is regular if and only if some regular expression R describes it. (a) True (b) False

(a) True

New cards

New cards

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.

New cards

New cards

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

New cards

New cards

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

New cards

New cards

|y| > 0

Clearly y must follow at least one transition if the state r is repeated

New cards

New cards

|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

New cards

New cards

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.

New cards

New cards

CFG terminals

the input alphabet, usually lower case letters or numbers

New cards

New cards

CFG variables

usually represented by capital letters: A, B, C . . .

New cards

New cards

derivation

The sequence of substitutions to obtain a string in a CFG

New cards

New cards

language of the grammar

All strings generated by a derivation in a CFG

New cards

New cards

context-free language

Any language that can be generated by some context-free grammar

New cards

New cards

non-context-free grammar

each production rule is a NOT single variable

New cards

New cards

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

New cards

New cards

CFL's are closed under which operations

The regular operations: union, concatenation, star

New cards

New cards

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

New cards

New cards

A language is context-free if and only if

some pushdown automaton recognizes it

New cards