Æ es una ER que denota el conjunto vacío

Î es una ER que denota el conjunto {Î}

Para cada a Î S, a es una ER que denota el conjunto { a }

Si p  y q son ER entonces (p+q), (pq) y (p*) denotan los conjuntos PÈQ, PQ y P* respectivamente

A continuación se muestran algunos ejemplos de algunas expresiones que son regulares y de las que no los son :

(x + y)*w

(0 + 1)*

(0 + 1 + ... + 9 )* (0 + 1 + ... + 9 )*

No son expresiones regulares :

xⁿ yⁿ

aⁿ b^2k aⁿ

Cada expresión regular r de un alfabeto S representa un lenguaje denotado por L(r)

            Existen diferentes formas de representar expresiones regulares, dependiendo de la complejidad de la condición establecida. Como veremos, el significado de una ER da como resultado un conjunto, por lo tanto las propiedades de los conjuntos son válidas para las ER.

AUTÓMATAS FINITOS DETERMINISTAS

            Una máquina de estado finito se utiliza para representar expresiones regulares. Para entender su funcionamiento es conveniente familiarizarnos con algunos conceptos de la simbología formal y hacer la relación con un grafo. Una máquina de estados finitos es un quíntuplo en el cual se señalan el alfabeto y la función de traslación entre estados. La transición es única, ya que de cada estado salen exactamente el número de elementos del alfabeto.

Estos autómatas no tienen almacenamiento temporal. Debido a que el número de estados es finito, un AFD puede tratar únicamente con situaciones en las cuales la información a ser almacenada en determinado tiempo está estrictamente limitada. Para representar estos autómatas, usamos grafos de transición, en los cuales los vértices representan los estados y las ligas las transiciones. Un lenguaje es el conjunto de cadenas aceptadas por un Autómata.

ACEPTACIÓN DE UNA PALABRA

Cuando rastreamos el AFD, nos damos cuenta que la cantidad de caminos desde un estado se reduce al número de elementos del alfabeto. Por lo tanto hay que concentrarnos en las configuraciones convenientes para armar un buen autómata. Muchas veces hacemos autómatas redundantes, y aunque aceptan las palabras requeridas, no son óptimos y eso se manifiesta en la implementación del AFD por computadora.

Una  máquina de estados finitos  es un quíntuplo (K, S, d,s, F ), donde

K es un conjunto de identificadores de estados

S es el alfabeto de entrada

s Î K es el estado inicial

F Í K es un conjunto de estados finales

d: KxS ® K es la función de transición

Una configuración  es la situación en que se encuentra la máquina en un momento dado.

            A continuación se muestran algunas definiciones necesarias para entender cuando es aceptada una palabra en un AF.

Definición 1.-  [q₁,w₁] a_M [q₂,w₂]  ssi w₁=sw₂ para un s Î S, y existe una transición en M tal que

d (q₁, s)=q₂

Definición 2.-  Una palabra w Î S* es aceptada por una máquina M=(K, S, d,s, F )  si existe un estado

q Î F tal que   [s,w] a_M* [q, e]

Definición 3.-  Un cálculo en una máquina M es una secuencia de configuraciones c₁,c₂,...,c_n tales que c_i a c_i+1.

Teorema.  Dados una palabra w Î S* y una máquina M, sólo hay un cálculo

 [s,w] a_M... a_M[q, e] .

Definición 4.-  Dos autómatas M₁ y M₂ son equivalentes, M₁ » M₂ , cuando aceptan exactamente el mismo lenguaje.

Definición 5.-  Dos estados son compatibles si ambos son finales o ninguno es final.

Definición 6.-  Dos estados q₁ y q₂ son equivalentes, q₁ » q₂ , ssi al intercambiarlos en cualquier configuración, no se altera la aceptación o rechazo de toda palabra.

Definimos una función d de KxS* ® K de la siguiente manera

d(q,e)

d(q,wa) = d( d(q,w), a )

La intención es que d(q,w) represente al estado en que estará el AF después de leer la cadena w del estado q.

Existen algunas características interesantes en un AFD que es conveniente analizar. Por ejemplo, el número de transiciones que salen de cada estado está en función de los

elementos del alfabeto. Esta característica parece dificultar la representación regular  del autómata, pero la definición lo pide, por lo cual, el alumno deberá pensar un poco más antes de obtener el AFD definitivo.

Una palabra es reconocida por un AFD cuando se realizan una serie de configuraciones hasta llegar a un estado final y la cadena haya sido consumida en su totalidad.

Cuando se rastrea una palabra en un AFD, se conocen los estados por donde se va pasando; sin embargo este camino es único, ya que de cada estado solo sale una transición por cada elemento del alfabeto. El alumno deberá demostrar esta unicidad, reforzando con aplicaciones. El cálculo de una palabra en un AFD es único.