Automata Theory and Formal Languages

Flashcards about Automata Theory and Formal Languages, covering computability and complexity theory.

What is Computability Theory?

Deals with which problems can be solved on a computer in finite time.

What does it mean for a problem to be 'solved by a computer'?

There exists an algorithm for solving the problem.

What is a Turing machine?

A very simplified machine model, which needs only a few instructions.

What does Church's thesis state?

The class of Turing-computable functions corresponds to the class of intuitive computable functions.

Why is the function f(n) = 1 if n is prime, 0 otherwise, computable?

One can specify an algorithm that solves the problem.

Is the Halting Problem computable?

This function is not computable.

How are functions and languages related in the context of computability?

They can be transferred into each other.

What is Complexity Theory?

Deals with the runtime behavior of algorithms.

What is the runtime complexity of sorting natural numbers?

O(N log N)

What does the exact time/memory requirements of complexity theory depend on?

Input Size, Programming Language, Compiler, and Computer

In Complexity Theory, what is the simplification for abstraction of the concrete computer?

Calculate the number of arithmetic operations (*, /, +, -).

What are the two simplifications used in Complexity Theory?

Relate the number of operations to the input size and ignore constant factors.

What are Landau Symbols?

A formal tool for doing complexity estimations and simplifications such that constant factors can be ignored.

Which Landau Symbol is most often used in Computer Science?

O (big O) is used most often.

What is the formal definition of O(f) in O notation?

{g : R -> R | ∃c > 0 ∃N0 ∀N > N0 |g(N)| ≤ c|f(N)|}

What should we consider when using O Notation?

Factors can be ignored, and just the term that increases most strongly needs to be considered.

What is O(1) complexity?

Constant Complexity (accessing a random field in an array).

What is O(log N) complexity?

Logarithmic Complexity (search in a sorted array).

What is O(N) complexity?

Linear Complexity (search in an unsorted array).

What is O(N log N) complexity?

Super Linear Complexity (sort an array).

What is O(N^2) complexity?

Quadratic Complexity (matrix-vector multiplication).

What is O(2^N) complexity?

Exponential Complexity (decrypt an encrypted message).