Resumo de Linguagens Formais e Complexidade Computacional

chap. 3 Linguagem:

turing-reconhecivel (recursively enumerável): - Oil

Turing decidível (linguagem recursive): - Oil and rejeitar

ch. 4

linguagens Decidíveis: AAFD, Aafn,

Aexp.Reg (se uma gera uma expressão regular given cadeia)

Vafd (se um determ finite automaton. Aceita alguma cadeia)

EQafd (linguaegm oil per se a um é igual AFD)

-1. L (C) * = (L (A) ^ (L (B)) ') U ((L (A))' ^ L (B))

-2. Testa avacuidade on C.

* A classe é das regular linguagens óperações dated as of complementação sob, and interseção união;

Aglc (se uma gera uma cadeia specific GLC)

Vglc (GLC gera alguma se uma cadeia)

All Linguagem livre-do-context; ---

Theorem 4.11: "Amt indecidível é"

Theorem 4.12: "Uma linguagem decidível se e somente é ela é is turing-reconhecível and co-Turing-reconhecível"

Chap.5

* (se uma uma linguagem MT reconhece regular AFD is there um equivalent)

Theorems, "is A ? M B e A é 'something' B então é 'something'

Theorem: Turing eqmt não é nem-nem reconhecível co-Turing-Reconhecivel. "

Cap. 7

T.7.8: "seja t (n) uma função, onde t (n) ? N, então any tempo Multifita MT t (n) MT de uma tem uma fita equivalent tempo only O (t ² (n))"

T.7.11: "Seja t (n) uma função, onde t (n) ? N.Entao for all MT ND tempo uma fita unique t (n) exists deter uma MT. Unica de uma fita de tempo 2 ^ ( O (t (n)))

D.7.12: "P é a classe de linguagens tempo em que são decidíveis MT uma polynomial Det. Unica de uma fita.

D.7.19 "é a classe das NP linguagens that polynomial têm tempo verifiers.

T.7.20: "Uma linguagem em NP is determined by sse ela é alguma tempo MT ND polynomial."

D.7.34: "Uma linguagem é is NP-Complete satifaz duas condições: 1. B is em NP and 2. All A NP é em tempo polinomial em redutível to B."

T.7.35: "B is NP-complete B epertence P então P = NP"

T.7.36 "pic is NP-complete B and B ? C p C and C belongs então é NP NP-complete."

Cap. 8

Savitch's theorem: "For qualquer função f: N -> R, onde f (n) ? N, NSPACE (f (n))C SPACE (f ² (n)) "Ou seja: Uma MT Det. Use somente o quadro do espaço da sua MT ND equivalent.

D8.6: PSPACE = classe das que são decidíveis linguagens espaço em uma polynomial by MT Det ..

D.8.8: "Uma linguagem é B is PSPACE-complete satisfaz condições 2: 1. B is em SPACE and 2. PSPACE em all A redutível é em tempo polinomial B. '

D.8.22: "Uma linguagem é B is NL-complete: 1. B é NL and 2. All A NL em espaço é em redutível log B.

É PSPACE dated na União complementação, dated é estrela na união NL, intersecao, estrela (same afn) PSPACE-hard NP-hard subconjuntoDE belongs to PSPACE EQexr linguagem are all NP-hard também é PSPACE-hard, PSPACE = NP Aall é PSPACE-complete AAFD belongs to L Aafn é é Vafd NL-FULL COMPLETE 2SAT é NL-NL-complete