Theory of Computation - EPFL

20 flashcards · Computer Science · by Athena Papkouf

1. When does machine M recognise the set of strings A?

   If A is the set of all strings that machine M accepts, we say that A is the language of machine M and write L(M) = A. We say that M recognizes A or that M accepts A. If the machine accepts no strings, it still recognizes one language — namely, the empty language ∅

2. regular language

   L is a regular language if there is a DFA such that L = L(M)

3. theorem about DFAs and NFAs

   Every nondeterministic finite automaton has an equivalent deterministic finite automaton.

4. A language is regular if

   and only if some nondeterministic finite automaton recognizes it

5. pumping lemma

   If A is a regular language, then there is a number p (the pumping length) such that, for every string s in A of length at least p, there exists a division of s into three pieces, s = xyz s.t. ∀i≥0,xyiz∈A\forall i \geq 0, xy^iz \in A∀i≥0,xyiz∈A ∣y∣≥1|y|\geq 1∣y∣≥1 and ∣xy∣≤p|xy|\leq p∣xy∣≤p

6. A TM machine M recognizes a language L ⊆ Σ* iff

   for all inputs w∈Σ∗w \in \Sigma^*w∈Σ∗ If w∈L→M accepts ww\in L \rightarrow M~accepts~ww∈L→M accepts w If w∉L→Mw \notin L \rightarrow Mw∈/L→M doesn't halt (or rejects w)

7. A TM machine M decides a language L ⊆ Σ* iff

   for all inputs w∈Σ∗w \in \Sigma^*w∈Σ∗ M halts on w and M accepts w iff w∈Lw \in Lw∈L

8. Halting problem

   HALT = {(M,w) : M is a TM and M halts on input w} undecidable, recognisable, while complement not recognisable

9. ATM problem

   ATM = {(M, w) : M is a TM and M accepts w} undecidable, recognisable, complement not recognisable

10. theorem about recognisability and decidability

    A language L is decidable iff it is recognizable and its complement is also recognizable

11. REGTM problem

    REGTM = = {(N) | L(N) is regular} undecidable

12. Language A is mapping reducible to language B, written A≤mBA \leq _m BA≤m​B

    if there is a computable function f:Σ∗→Σ∗f: \Sigma^* \rightarrow \Sigma^*f:Σ∗→Σ∗ , such that ∀w∈Σ∗: w∈A ⟺ f(w)∈B\forall w \in \Sigma^*: ~ w\in A \iff f(w)\in B∀w∈Σ∗: w∈A⟺f(w)∈B

13. reductions and decidability

    If A ≤m B and B is decidable, then A is decidable. If A ≤m B and A is undecidable, then B is undecidable.

14. reductions and recognisability

    If A ≤m B and B is recognisable, then A is recognisable. If A ≤m B and A is unrecognisable, then B is unrecognisable

15. verifier for language L

    A Turing machine M such that ∀x∈Σ∗\forall x \in \Sigma^*∀x∈Σ∗ If x∈L→∃Cs.t. M accepts (x,C)x\in L \rightarrow \exists C s.t.~M~accepts~(x, C)x∈L→∃Cs.t. M accepts (x,C) If x∉L→∀C, M rejects (x,C)x\notin L \rightarrow \forall C, ~M~rejects~(x, C)x∈/L→∀C, M rejects (x,C)

16. nondeterministic decider for language L

    A non-deterministic Turing machine N such that ∀x∈Σ∗\forall x \in \Sigma^*∀x∈Σ∗ every computation of N halts and moreover, If x∈L→∃Cs.t. M accepts (x,C)x\in L \rightarrow \exists C s.t.~M~accepts~(x, C)x∈L→∃Cs.t. M accepts (x,C) If x∉L→∀C, M rejects (x,C)x\notin L \rightarrow \forall C, ~M~rejects~(x, C)x∈/L→∀C, M rejects (x,C)

17. equivalence of poly-time deciders and verifiers

    For any languge L⊆Σ∗L\subseteq \Sigma^*L⊆Σ∗ L has a non-deterministic poly-time decider ⟺ \iff⟺ L has a poly-time verifier.

18. NP definition

    NP is the class of languages which have poly-time nondeterministic deciders, or equivalently, have poly-time verifiers.

19. reductions and P class

    If A≤pBA \leq_p BA≤p​B and B is in P, then A is in P. If A≤pBA \leq_p BA≤p​B and A is not in P, then B is not in P.

20. NP-completeness

    A language L is said to be NP-complete if L is in NP. For every language L' in NP, L' ≤P L.