Theory of Comp Midterm Study

studied byStudied by 47 People
0.0(0)
get a hint
hint

NP-complete problems

1/47

Studying Progress

New cards
47
Still learning
0
Almost done
0
Mastered
0
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:

  1. for each i ≥ 0, xy^iz ∈ A,

  2. |y| > 0, and

  3. |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