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

...