Teoria de la Computació: Llenguatges i Complexitat

Lema de bombeig per a llenguatges regulars

Llenguatge Multi-full: L = {(a³b²)ᵏ | k > 0}

• 1. Assumim que és regular.
• 2. p serà la longitud de bombeig // S = (a³b²)ᵖ.
• 3. S té almenys una longitud p.
• 4. Partim s de la següent manera: x = ε, y = (a³b²), z = ε.

Condicions:

• Condició 1: Per a cada i ≥ 0, xyⁱz ∈ A (D'acord).
• Condició 2: |y| > 0 (D'acord).
• Condició 3: |xy| ≤ p (D'acord).

Tancament de la classe de llenguatges regulars

Demostreu que la classe dels llenguatges regulars és tancada sota l'operació de concatenació:

Fem dos NFA, un per a A₁ i un per a A₂, i els combinem en un nou NFA N. L'inici de N serà l'inici de N₁. Si N₁ es troba en un estat d'acceptació, significa que ha trobat una peça inicial de l'entrada que constitueix una cadena a A₁. Per tant, acceptarà quan l'input pugui ser separat en dues parts: la primera acceptada per N₁ i la segona per N₂.

Definició d'una Gramàtica Lliure de Context (CFG)

Una CFG és una 4-tupla (V, Σ, R, S) on:

• V: És un conjunt finit de variables.
• Σ: És un conjunt finit i disjunt de V (terminals).
• R: És un conjunt finit de regles, on cada regla és una variable o una cadena de variables i terminals.
• S ∈ V: És la variable inicial.

Exemple: G₃ = ({S}, {a, b}, R, S).

Llenguatges Turing-reconeixibles i enumeradors

Pregunta: Si existeix una Màquina de Turing enumeradora per a L, llavors L és Turing-reconeixible?

Cert: Un llenguatge és Turing-reconeixible si i només si algun enumerador l'enumera. La resposta és Sí.

La qüestió P = NP

La relació entre les classes de complexitat NP i P és una pregunta que la teoria de la complexitat computacional encara no ha pogut respondre. En essència, la pregunta ¿és P = NP? significa: si és possible verificar ràpidament solucions positives a un problema del tipus SÍ/NO (on "ràpidament" significa en temps polinòmic).

És regular el llenguatge MULTI-FULL?

Llenguatge: MULTI-FULL = {(a³b²)ᵏ | k > 0}

Sí. (a³b²)+ és una expressió regular definida a partir de la iteració de concatenacions. Tanmateix, es pot definir mitjançant el següent DFA:

Σ = {
(q_start, a, q₁); (q_start, b, q_reject);
(q₁, a, q₂); (q₁, b, q_reject);
(q₂, a, q₃); (q₂, b, q_reject);
(q₃, b, q₄); (q₃, a, q_reject);
(q₄, b, q_accept); (q₄, a, q_reject);
(q_accept, a, q₁); (q_accept, b, q_reject)
}

Llenguatge Hyper Pair

Pregunta: ¿És lliure de context el llenguatge HYPER PAIR = {CⁱPʲ | i, j > 0 ∧ i = j}?

Sí. Es pot definir una CFG a partir de G = ({S}, {C, P}, {S → CSP | CP}, S).