Introducción autómatas y gramáticas

Introducción autómatas y gramáticas

                                        Introducción autómatas y gramáticas

Jorge Andrés Gómez Vasco

Facultad de Ingeniería y Ciencias Agropecuarias, Tecnología en desarrollo de Software

Asignatura: autómatas, Lenguajes y gramáticas

Docente: Joaquín Fernando Aguilar

14/07/2021

1. (10%) Obtenga un AFD con el lenguaje definido en el alfabeto Σ={0,1}, que pueda

generar entre otras, un subconjunto de las siguientes cadenas {010}, {01110},

{01011}, {010101}, {01110}, {101}, {10001}, {1111}.

[pic 1]

2. (10%) Obtenga un AFND diferente al AFD del punto anterior, con el lenguaje definido en el alfabeto Σ={0,1}, que pueda generar entre otras, un subconjunto de las siguientes cadenas {010}, {01110}, {01011}, {010101}, {01110},

{101}, {10001}, {1111}.

[pic 2]

3. (20%) Dado el alfabeto Σ= {a,b}, construir un Autómata Finito Determinista, que acepte el lenguaje representado por la siguiente expresión regular a*(ab+ba)(bb)∗ 

[pic 3]

[pic 4]

         a. (5%) Indicar si es AFD o AFND y justifique su respuesta.

R/ ES un automata no determinístico, ya que cuando entra un 0 o 1 entra a dos estados al mismo tiempo.

        b. (15%) Indique la quíntupla del autómata

A=({Q1,Ø,Q2,Q3,Q4},{0,1},δ,Q0,{Q4,Q2})

c. (15%) Dibuje el autómata en un simulador

[pic 5]

d. (5%) Señale tres cadenas que cumplan y tres cadenas que no cumplan con ese autómata.

             e. (20%) Indique el autómata en lenguaje regular.

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

...