Decidability

Question 1

Theorem 4.1 (Decidable Language)

Answer 1

The language A_(FA) = {(B, w) | B is a deterministic FA that accepts input string w} is decidable.

Question 2

Theorem 4.2 (Decidable Language NFA)

Answer 2

The language A_(NFA) = {(B, w) | B is an NFA that accepts input string w} is decidable.

Question 3

Theorem 4.3 (Decidable Language RE)

Answer 3

The language

A_(REX) = {(R, w) | R is a regular expression that generates string w} is decidable.

Question 4

Theorem 4.4 (Decidable Language)

Answer 4

The language E_(FA) = {(A) | A is a FA and L(A) = ∅} is decidable.

Question 5

Theorem 4.5 (Equality of decidable languages)

Answer 5

The language EQ_(FA) = {(A, B) | A and B are FAs and L(A) = L(B)} is decidable.

Question 6

Theorem 4.6 (Decidable Language CFG)

Answer 6

The language A_(CFG) = {(G, w) | G is a CFG that generates string w} is decidable.

Question 7

Theorem 4.7 (Decidable Language CFG empty language)

Answer 7

The language E_(CFG) = {(G) | G is a CFG and L(G) = ∅} is decidable.

Question 8

Theorem 4.8 The set of context-free languages is contained …

Answer 8

in the set of decidable languages.

Question 9

Theorem (Undecidability of the halting problem)

Answer 9

The language HALT_(TM) = {(M, w) | M is a TM and M halts on input w} is undecidable.

Question 10

Definition 4.1 (Same Cardinality)

Answer 10

Let A, B be sets. A and B have the same size / same cardinality, if there exists a bijective function f with f : A → B.

Question 11

Definition 4.2 (Countable)

Answer 11

A set A is countable, if it is either finite or has the same size as N. Otherwise it is uncountable.

Question 12

Theorem 4.10 (Undecidability TM)

Answer 12

The language A_(TM) = {(M, w)| M is a TM and M accepts w} is undecidable.

Question 13

Theorem 4.11 (Undecidability of the halting problem)

Answer 13

The language HALT_(TM) = {(M,w) | M is a TM and M halts on inputw} is undecidable.

Question 14

Definition 4.3 (Computable Function)

Answer 14

A function f : Σ∗ → Σ∗ is a computable function, if some decider M, on every input w, halts with f(w) on its tape.

Question 15

Definition 4.4 (Mapping Reducible)

Answer 15

Let A, B be languages over Σ. A is mapping reducible to B, short A ≤m B, if there is a computable function f : Σ∗ → Σ∗, such that for all w ∈ Σ∗, it holds

               w ∈ A iff f(w) ∈ B .

f is called reduction from A to B.

Question 16

Theorem 4.12

Answer 16

Let A ≤m B. If B is decidable, then A is decidable.

Question 17

Theorem 4.13

Answer 17

The language REGULAR_(TM) = {(M)|M is a TM and L(M) is a regular language} is undecidable.

Question 18

Theorem 4.14 (Turing-Recognizablility)

Answer 18

The language A_(TM) = {(M, w) | M is a TM and M accepts w} is Turing-recognizable.

Question 19

Theorem 4.15 (Non-Turing-Recognizable)

Answer 19

There exist languages that are not Turing-recognizable.

Question 20

Definition 4.5 (co-Turing-recognizable)

Answer 20

We call a language L co-Turing-recognizable if L is Turing recognizable.

Question 21

Theorem 4.16 (Decidability TM)

Answer 21

A language is decidable if and only if it is Turing-recognizable and co-Turing-recognizable.

Question 22

Theorem 4.17 (Turing Recognizable)

Answer 22

Let A ≤_m B. If B is Turing-recognizable, then A is Turing recognizable

Question 23

Theorem 4.18 (Not Turing Recognizable)