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

...