Taller Introducción autómatas y gramáticas
Enviado por daba12 • 17 de Junio de 2023 • Informes • 478 Palabras (2 Páginas) • 47 Visitas
[pic 2][pic 1]
Taller
Introducción autómatas y gramáticas
Presentado por:
Diego Alejandro Barros Ballestas
CC 1082889414
Curso:
Autómatas, Gramáticas y Lenguajes
PREICA2301B020046
Docente:
Joaquín Aguilar
Programa en Tecnología en Desarrollo de Software
Facultad de Ingeniería y Ciencias Agropecuarias
Institución Universitaria Digital de Antioquia
Periodo_2023-1-B2A
Taller
- (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 3]
- (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 4]
- (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 5]
[pic 6]
- (60%) Dada la siguiente tabla de transición hacer los siguientes puntos:
→ Q0 | {Q0, Q3} | {Q0, Q1} |
Q1 | ∅ | Q2 |
#Q2 | Q2 | Q2 |
Q3 | Q4 | ∅ |
#Q4 | Q4 | Q4 |
- (5%) Indicar si es AFD o AFND y justifique su respuesta.
Rta// De acuerdo con los datos de la tabla se puede deducir que es un autómata finito no determinista AFND, debido a que su estado inicial Q0 cuando toma el valor de 0 tiene 2 transiciones, y lo mismo cuando toma el valor de 1. Adicionalmente el autómata presenta 2 estados finales tales como Q2 y Q4.
...