Ejercicios propuestos: Autómatas finitos PDF

Preview

Summary

Download Ejercicios propuestos: Autómatas finitos PDF

Description

Grado en Ingeniería Informática Teoría de Autómatas y Lenguajes Formales

EJERCICIOS PROPUESTOS. Autómatas finitos 1. Diseñar y definir formalmente un AFD para cada uno de los siguientes lenguajes. Minimizar, si es posible, los autómatas definidos. a) Las palabras en {a, b} que contienen un número par de aes. b) Las palabras en {a, b} que contienen un número impar de aes. c) Las palabras del lenguaje en {0, 1} con a lo sumo dos unos consecutivos. d) Las palabras del lenguaje en {a, b} que tienen un número impar de ocurrencias de la subcadena ab. e) El lenguaje en {a, b} donde las palabras que contienen aba terminan en bb. f)

(jun 2012) Dado el alfabeto {a,b} diseñar y definir formalmente un AFD que acepte el lenguaje formado por las palabras que terminan en “bbb”.

g)

(jun 2011) Diseñar y definir formalmente un AFD que acepte el lenguaje formado por las cadenas en el alfabeto {a, b} cuyas palabras no comienzan con aa.

h)

(nov 2010) Diseñar y definir formalmente un Autómata Finito Determinista que acepte el lenguaje formado por las cadenas en {a, b} que terminan en bb.

i)

(nov 2011) Diseñar y definir formalmente un AFD que acepte el lenguaje formado por las palabras {x ∈ {0,1}* | x termina en 01}.

j)

L={x∈ {a,b}* | toda a en x está entre dos bes}

k) L={x∈ {a,b}* | x tiene un número múltiplo de 3 de aes} l)

L={x∈ {a,b}* | x no tiene 2 aes consecutivas}

m) L={x∈ {a,b}* | x no contiene la subpalabra aa ni bb} 2. Diseñar y definir formalmente un AFND para el lenguaje formado por las cadenas del alfabeto {0,1,2,3,4,5,6,7,8,9} de forma que el dígito final haya aparecido antes en la misma cadena. 3. Minimizar los siguientes autómatas: a) A1 = ({0,1}, {p, q,r, s, t}, f, p, {t}) donde f es: f

0

1

→p

q

r

q

q

s

r

q

r

s

q

t

*t

q

r

1

4. Sea el AFND, cuya función de transición se define mediante la tabla siguiente. Transformarlo en un autómata finito determinista. 0

1

{p, q}

{p}

Q

{r}

{r}

R

{s}

∅

*s

{s}

{s}

→p

5. Diseñar el AFD equivalente al AFND, cuya función de transición se define mediante la siguiente tabla

→p

a

b

{p, q}

{q}

*q

{p,q}

6. (nov 2010) Diseñar el Autómata Finito Determinista mínimo equivalente al Autómata Finito No Determinista AFND = ({0,1, 2}, {p,q,r,s,t,u,v}, f, p, {v}) donde f se define como: 7. 0

f

1

2

λ {q,t}

→p {r,s}

q

{r,s}

r

{q,u}

s

{t,p}

{u}

t

{v}

u {s,q }

{q} {v}

*v

{s} {r}

8. Diseñar el Autómata Finito Determinista mínimo equivalente al Autómata Finito No Determinista AFND = ({a, b}, {p,q,r,s,t}, f, p, {t}) donde f se define como: f

0

1

λ

→p q r

{q}

{q}

{r}

{r} {p}

{q} {t}

{s}

S

{t}

{q}

*t

{t}

{t}

9. (dic 2011) Diseñar el Autómata Finito Determinista mínimo equivalente al Autómata Finito No Determinista AFND = ({0, 1}, {p,q,r}, f, p, {q}) donde f se define como: f →p *q r

0

1

{q}

{q}

{p,r}

{q} {q}

2

λ {r}

10. ¿Cuáles de los siguientes autómatas son equivalentes entre sí? A1 = ({p,q,r,s,t,u}, {a,b}, f1, p, {q,r}) A1 a b →p q p *q r s t *r q s t u t s u u q u A3 =({p,q,r,s,t,u}, {a,b}, f3, p, {s,t,u}) A3 a b u q →p r q t r s r *s t r *t u q *u s p A5 = ({p,q,r,s,t}, {a,b}, f5, p, {r,s}) A5 a b →p q r t q q *r s q *s r q t r q

A2= ({p,q,r,s,t,u}, {a,b}, f2, p, {u}) A2 a b →p q u q r t t r s s r t t u s *u u q A4 = ({p,q,r,s,t,u}, {a,b}, f4, p, {r,s}) A4 a b r q →p q q r *r s t *s r t t t q u u p A6 = ({p,q,r,s,t,u}, {a,b}, f6, p, {r,s,t}) A6 a b →p q r s q p *r t u *s t u *t t u u u u

11. Construya un AFD mínimo que reconozca el lenguaje generado por las siguientes gramáticas: a) G = ({A,B,C}, {0, 1},A, {A ::= 0B | λ; B ::= 1C | 1; C ::= 0B}) b) G = ({S,A,B}, {a, b}, S, {S ::= bS | aA | λ; A ::= aA | bB | b; B ::= bS}) 12. Dados los autómatas siguientes definidos sobre Σ = {a, b}:

a) Determinar si son equivalentes (calculando los AFDs equivalentes mínimos). b) Obtener una gramática lineal por la derecha que genere el lenguajs reconocido por cada uno de dichos autómatas si son equivalentes.

3

13. Sea el autómata descrito por la siguiente tabla de transiciones: 0 →p *q

{p}

r

{r}

1

λ

{q, r}

{r}

{p, q} {s}

s a) b) c) d) e)

Calcular f’(p, λ), f’(p, 1), f’(p, 0), f’(p, 110), f’(p, 001), f’(p, 1010), f’(q,1), f’(q, 110) ¿Acepta el autómata la palabra vacía? ¿Qué lenguaje reconoce este autómata? Definir la gramática que genera el lenguaje reconocido por el autómata.

14. ¿Qué lenguaje reconoce el siguiente autómata?

4...