Teoría de autómatas resumen

Materia: Teoría de la computación.
Facultad: Ciencia y Tecnología
“Lenguajes aceptados por los autómatas”
Los lenguajes regulares son los aceptados por los autómatas.
LENGUAJES REGULARES: un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades:
1. Puede ser reconocido por:
* Un autómata finito determinista
* Un autómata finito no determinista* Un autómata finito alterno
* Una máquina de Turing de sólo lectura
Un autómata finito determinista: Es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir salida.
Un autómata finito no determinista: posee un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.
Un autómata finito alterno.
Unamáquina de Turing de solo lectura: Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
2. Es generado por:
UNA GRAMÁTICA REGULAR:
Una gramática regular es una gramática formal (N, Σ, P, S) que puede ser clasificada como regular izquierda o regular derecha. Las gramáticas regulares sólo puedengenerar a los lenguajes regulares de manera similar a los autómatas finitos y las expresiones regulares.

Dos gramáticas regulares que generan el mismo lenguaje regular se denominan equivalentes. Toda gramática regular es una gramática libre de contexto.

Una gramática regular derecha es aquella cuyas reglas de producción P son de la siguiente forma:
A → a, donde A es un símbolo no-terminal en N ya uno terminal en Σ
A → aB, donde A y B pertenecen a N y a pertenece a Σ
A → ε, donde A pertenece a N.

Análogamente, en una gramática regular izquierda, las reglas son de la siguiente forma:
A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ
A → Ba, donde A y B pertenecen a N y a pertenece a Σ
A → ε, donde A pertenece a N.

Una definición equivalente evita la regla 1 (A→ a) ya que es sustituible por:
A → aL
L → ε

En el caso de las gramáticas regulares derechas y por:
A → La
L → ε

En el caso de las izquierdas.

Algunos autores alternativamente no permiten el uso de la regla 3 suponiendo que la cadena vacía no pertenece al lenguaje.

Un ejemplo de una gramática regular G con N = {S, A}, Σ = {a, b, c}, P se define mediante las siguientes reglas:
S → aSS → bA
A → ε
A → cA

Donde S es el símbolo inicial. Esta gramática describe el mismo lenguaje expresado mediante la expresión regular a*bc*.

Dada una gramática regular izquierda es posible convertirla, mediante un algoritmo en una derecha y viceversa.

UNA GRAMÁTICA DE PREFIJOS O LIBRE DE CONTEXTO
Una gramática libre de contexto (o de contexto libre) es una gramática formal en la quecada regla de producción es de la forma:
V → w

Donde V es un símbolo no terminal y w es una cadena de terminales y/o no terminales. El término libre de contexto se refiere al hecho de que el no terminal V puede siempre ser sustituido por w sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es libre de contexto si hay una gramática libre de contexto que lo genera.

Lasgramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la síntaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen comopuede ser generada desde la gramática. Los analizadores LL y LR tratan restringidos subconjuntos de gramáticas libres de contexto.

La notación más frecuentemente utilizada para expresar gramáticas libres de contexto es la forma Backus-Naur.
3. Es descrito por:

UNA EXPRESIÓN REGULAR:
Una expresión regular, a menudo llamada también patrón, es una expresión que describe un conjunto de...