Complejidad Computacional v/s Jerarquía de Chomsky

1. Complejidad computacional: Complejidad
computacional, una medida de la cantidad de recursos informáticos (tiempo y espacio) que consume un algoritmo en particular cuando se ejecuta.

La complejidad temporal de una máquina de Turing viene dada por la función T(n), donde

      T(n) = Número máximo de movimientos realizados por la TM para procesar una string de longitud n.

La complejidad espacial de la máquina de Turing viene dada por la función S(n), donde

       S(n) = Número máximo de cuadrados de cinta utilizados por el TM para una entrada de longitud n.

La complejidad temporal de una máquina de Turing simple:
Considere el lenguaje,

L = {ωcωR  |ω∈(0+1)*}

Para reconocer una string de la forma ωcω ^R , el TM requerirá :

Compara el primer y el último carácter = 2n + 1 movimientos 

Compare el segundo carácter de dos extremos = 2 (n -1) + 1 movimientos

Encuentra el carácter central c = 1 movimiento

Número total de movimientos T(n),

= (2n + 1) + (2 (n - 1) +1)+.......(2(n -(n -1)) + 1) + 1
 = 2(1+2+.........+n)+n = 2 X (n)(n+1) / 2 + n = n2 + 2n
= n2+2n 
= O(n2)

La complejidad del tiempo se puede reducir tomando una máquina de dos cintas.

• La máquina copia la string de entrada a la izquierda de c en la segunda cinta.
• Cuando se encuentra c en la cinta de entrada, el TM mueve su segundo cabezal de cinta hacia la izquierda.
• El cabezal de cinta de entrada continúa moviéndose hacia su derecha y el segundo cabezal de cinta hacia su izquierda.
• Los símbolos debajo de las dos cabezas se comparan a medida que se mueven las cabezas.
• Si todos los símbolos coinciden y el carácter central es c, se acepta la string.

El TM realiza un máximo de n+1 movimientos.

 T(n) = n+1 = O(n)

La complejidad espacial de TM viene dada por S(n) = n + 1 [longitud de string n y un símbolo en blanco]

Complejidad de tiempo y espacio no determinista:
una TM no determinista tiene una complejidad de tiempo T(n) si ninguna secuencia de opciones hace que la máquina realice más de T(n) movimientos. La complejidad del espacio es de S(n) si ninguna secuencia de opciones necesita más que las celdas de cinta S(n).

Jerarquía de Chomsky :
una gramática se puede clasificar en función de las reglas de producción. Chomsky clasificó las gramáticas en los siguientes tipos:

Tipo de gramática	Gramática	Autómata
tipo 0	gramática sin restricciones	Máquina de Turing
Tipo 1	Gramática sensible al contexto	Autómata acotado linealmente
Tipo 2	gramática libre de contexto	autómata de empuje hacia abajo
Tipo 3	gramática regular	Autómata de estado finito

Tipo-3 o gramática regular:
una gramática se llama tipo 3 o gramática regular si todas sus producciones son de las siguientes formas:-

A ⇢ ε     A ⇢ a
A ⇢ aB    A ⇢ Ba

donde a ∈ ∑ y A, B ∈ V.

Un lenguaje generado por la gramática de tipo 3 se conoce como lenguaje regular .

Gramática de tipo 2 o libre de contexto :
una gramática se llama tipo 2 o gramática libre de contexto si todas sus producciones son de la siguiente forma A ⇢ α donde A ∈ V y α ∈ (V ∪ T)*.

V es un conjunto de variables y T es un conjunto de terminales.

El lenguaje generado por una gramática de tipo 2 se denomina lenguaje libre de contexto . 

Gramática de tipo 1 o sensible al contexto:
una gramática se denomina gramática de tipo 1 o sensible al contexto si todas sus producciones tienen la siguiente forma: α ⇢ β, donde β es al menos tan larga como α.

Tipo-0 o gramática sin restricciones:
las producciones se pueden escribir sin ninguna restricción en gramática sin restricciones. Si hay una producción de α ⇢ β, entonces la longitud de α podría ser mayor que la longitud de β.

• Cada gramática es también una gramática de Tipo 0 de números.
• La gramática de tipo 2 también es una gramática de tipo 1.
• La gramática de tipo 3 también es una gramática de tipo 2.
   

Complejidad Computacional v/s Jerarquía de Chomsky:

Complejidad computacional	Jerarquía de Chomsky
La complejidad computacional es una medida de la cantidad de recursos informáticos (tiempo y espacio) consumidos por un algoritmo en particular mientras se ejecuta.	La Jerarquía de Chomsky representa la clase de lenguajes que son aceptados por las diferentes máquinas.
La complejidad computacional es muy importante en el análisis de algoritmos.	La jerarquía de Chomsky es importante en la ciencia cognitiva porque la complejidad de una gramática en la jerarquía se puede utilizar para evaluar.
La complejidad computacional es la gramática sin restricciones	La jerarquía de Chomsky es una gramática sensible al contexto
Complejidad computacional utilizada en Turing Automaton	Jerarquía de Chomsky utilizada en autómatas con límites lineales