Automatas Ejercio

DESARROLLO DE LAS ACTIVIDADES

Para el siguiente ejercicio, recordaremos ciertas apreciaciones, conceptos o afirmaciones acerca de las Expresiones Regulares, comúnmente denotadas como “ER”:

Una expresión regular es una forma de representar cierto tipo de lenguajes sobre un determinado alfabeto. Son exactamente los aceptados por los autómatas de estado finito.

Si tomamos como A un alfabeto, unas posibles expresiones regulares sobre ese alfabeto podrían ser: (identifique que lenguaje reconoce esa ER)….

Ø es una ER que denota el Lenguaje?

R//= L{Ø}=Ø

λ es una ER que denota el lenguaje?

R//= L{λ}=λ

En general los lenguajes que pueden representarse mediante una expresión regular se llaman lenguajes regulares. Estos coinciden con los aceptados por los autómatas finitos.

Es importante que tengamos definido o claro que Si r y s son ER denotando los lenguajes R y S, entonces se definen tres operaciones muy básicas:

- Unión: (r + s) es una expresión regular ER que denota el lenguaje R S

- Concatenación: (rs) algunos autores lo toman como (r•s) es una expresión regular ER que denota le lenguaje RS.

- Clausura: r* es una expresión regular ER que denota el lenguaje R

Para efectos de plasmar las ER, los paréntesis se pueden eliminar siempre y cuando los símbolos y caracteres no alteren la interpretación de otros caracteres o cadenas. La precedencia de las operaciones es: clausura / Concatenación / Unión.

Para los siguientes ejercicios identifique el lenguaje que reconoce y plasme cinco posibles cadenas válidas que representan esa ER:

Si A = {a,b,c}

(a + b)*(a+b)

(a + b)*

EXPRESION CADENAS POSIBLES

(a + b)* {λ}

Aaabbb

aaaaabb

abaabbaabb

aabbabab

(a + λ )ba*

EXPRESION CADENAS POSIBLES

(a + λ )ba* A

Aba

Aaaa

Abbbaaa

Ababab

b (aba)*

λ* (Es una ER?)

EXPRESION CADENAS POSIBLES

λ* {λ}

Si A = {0,1}

0*+1*(01)

10* + 10

EXPRESION CADENAS POSIBLES

10* + 10 10

1010

1011

1010

101010101

01* + 0

EXPRESION CADENAS POSIBLES

01* + 0 0

010

0100

00

010101010

(1 – 110) *

EXPRESION CADENAS POSIBLES

(1 – 110) * {λ}

1110

11110

1110110

1111110

(1 + 10) + 0

EXPRESION CADENAS POSIBLES

(1 + 10) + 0 110

1110

11110

1110110

1111110

1* 0*10

00* 11*

EXPRESION CADENAS POSIBLES

00* 11* {λ}

0011

00

11

00110011

(0+1)*11(1+0)*

EXPRESION CADENAS POSIBLES

(0+1)*11(1+0)* 11

011110

0111

111111

0101010111101010

SOLUCION EJERCICIO No. 9

9. Para el siguiente autómata finito determinista dado por:

M = ({q0, q1, q2, q3} , {0, 1} , δ, q0, {q1})

Donde la función δ : {q0, q1, q2, q3 } × {0, 1} → {q0, q1, q2, q3} viene dada por:

δ(q0, 0) = q0

δ(q0, 1) = q1

δ(q1, 0) = q0

δ(q1, 1) = q2

δ(q2, 0) = q3

δ(q2, 1) = q1

δ(q3, 0) = q3

δ(q3, 1) = q2

Plásmelo en los simuladores

Realice el diagrama de Moore.

Identifique la tabla de transición correspondiente

Verifique el lenguaje aceptado y las cadenas válidas para el autómata.

Identifique la expresión regular que lo representa.

PLASMADO ENE LE SIMULADOR (VAS)

PLASMADO EN EL SIMULADOR (JFLAP)

TABLA DE TRANSICION (VAS)

CONCLUSIONES

Diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que recuerda cada cual.

Un lenguaje regular sobre un alfabeto Σ dado se define recursivamente como:

El lenguaje vacío es un lenguaje regular

El lenguaje cadena vacía {ε} es un lenguaje regular

Para todo símbolo a ∈ Σ {a} es un lenguaje regular

Si A y B son lenguajes regulares entonces A ∪ B (unión), A•B (concatenación) y A* (clausura o estrella de Kleene) son lenguajes regulares

Si A es un lenguaje regular entonces (A) es el mismo lenguaje regular

No existen más lenguajes regulares sobre Σ

Los lenguajes finitos, aquellos que solo contienen un número finito de palabras.

...