Api Developer: Lenguajes de Programación y Compiladores


POST


Post Top Ad

Post Top Ad

miércoles, 12 de julio de 2017

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos

7/12/2017 03:50:00 p.m. 0
Juan Jesús de la Cruz nos consultaba como resolver un Autómata para el siguiente planteamiento:


Se requiere construir un autómata para reconocer cadenas, cuyo número de ceros sea divisible entre 3 y el número de unos sea divisible entre 5.


¿Cómo llego a obtener S que  son los estados y F que es el estado final?

Para comenzar compartimos algunas publicaciones realizadas sobre los Autómatas.




Autómata Solución # 1.


Primera propuesta, verán que aún tiene errores.

Este es el Diagrama de Transición propuesto, puede mejorarse. Fue la primera solución que dimos antes que llegara la iluminación y completarlo con éxito.

En las entradas podemos ver que esta propuesta deja pasar algunas cadenas que no deberían ser aceptadas.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Primera solución del Diagrama de Transición

Símbolos y Estados del Autómata Solución # 1.


En el caso de esta propuesta inicial los estados quedan de la siguiente forma:

Gramática                 A = {0,1}

Estados                      S = {q0, q1, q2,  q3}

Estados Finales         F = {q0, q1,  q3}

Estado inicial            q1 = {q0}



Autómata Solución # 2.


Propuesta final, esta sería la solución correcta.

Mucho puede pasar mientras vamos de viaje en el autobús, en este caso no podía concentrarme en disfrutar del viaje por el mencionado Autómata que propuso resolver Juan Jesús, uno de nuestros lectores. Me propuse dar solución mejorada y este fue el resultado de mis apuntes expres en el autobús.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Borrados del diagrama

Realizado en JFlap el segundo Diagrama de Transición lo dejamos así.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Diagrama de Transición con ventana de pruebas.


Ahora si vemos que el Autómata solo acepta cadenas de 3 ceros y 5 unos, todas las demás cadenas son rechazadas.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Autómata desarrollado de forma correcta.

El truco fue encontrar la forma de definir los estados finales, y resultó que el problema se resolvía perfectamente dejando como estado final el mismo estado inicial, pero con los retornos que podemos ver en la figura.

Ventana de pruebas.

Ejemplo de Autómata para Reconocer Cadenas de Ceros y Unos
Pruebas realizadas de forma correcta.

Símbolos y Estados del Autómata Solución Correcta.


Gramática                 A = {0,1}

Estados                      S = {q0, q1, q2,  q3,  q4, ,  q5, ,  q6}

Estados Finales         F = {q0}  también se le conoce como qf

Estado inicial            q1 = {q0}

Gramáticas Válidas


000
11111
00011111
11111000
00011111000
1111100011111
00000011111
111111111100011111000
Etc.

Gramáticas Inválidas


0
00
000
1
11
111
1111
0011111
1111000


Si tienes alguna opinión o otra propuesta de solución puedes dejarnos comentarios que apreciaremos mucho.

Si tienes algún ejemplo de autómatas y quieres compartirlo escríbenos en nuestro formulario de contactos, lo compartiremos en el blog.

Read More

martes, 7 de marzo de 2017

Como Aumentar Visitas en Tu Blog de Programación

3/07/2017 04:45:00 p.m. 0
Saludos, vamos a poner el día este blog, después de tanto tiempo sin publicar vemos que tienen potencial. Han pasado cinco años desde que estamos hablando de Lenguajes de Programación, Compiladores y Lenguajes Interpretes. El tema sigue vigente, desde que hace unos años comencé con la enseñanza de esta temática que para muchos estudiantes de ingeniería es de las más complejas y causa muchas preocupaciones por su lógica complicada. 

Aumentar Visitas en Tu Blog de Programación



Estrategias Utilizadas Para Aumentar las Visitas del Blog 

En este caso vamos hablar de nuestro recorrido por la web y nuestras estrategias para posicionar este blog, hemos estado revisando mucho los temas y vídeos sobre aumentar las visitas en tu blog publicados por ROMUALFONS, específicamente su vídeo 77 formas de aumentar el trafico de tu blogEn el que comparten los mejores consejos para ir subiendo de nivel en esto del SEO y ponerle buena cara a los buscadores.


Crecimiento del Blog Lenguajes de Programación 

Puedes revisar los contenidos que te sugerimos, son muchos consejos que mejoran las condiciones de tu sitio. Desde que aplicamos mejoras por ejemplo podemos mencionar que pasamos en menos de un año de un poco más de 50,000 visitas a la fecha que estamos llegando a unas 120,000 visitas. Con un promedio de 300 visitas diarias y unas 10,000 mensuales. Estamos pensando mejorar estas cifras, porque vamos a ser claros, son para que cualquier blogger experto se ría en nuestra cara, pero en nuestro caso que estamos creando una comunidad de seguidores que gustan de la programación, me parece que vamos por buen camino.

Blog Lenguajes de de Programación Pavillalta

Aumento en las Estadísticas del blog Lenguajes de Programación



Mejoras Implementadas en Blog Lenguajes de Programación 

Progresivamente hemos aplicado mejoras, en nuestro caso quedamos cortos, no podemos hablar como expertos, por eso te proporcionamos las URL de referencias, las que nos han iluminado con unos consejos muy buenos.

En nuestro caso ha funcionado lo siguiente:

Definir una lista de categorías

Creamos un menú con las categorías principales, al menos cinco palabras clave que vamos a tratar de ir posicionando a medida publicamos. Estas categorías son: Lenguajes de Programación, Compiladores, Intérpretes, Autómatas y Libros. Consideramos que son en las que debemos enfocarnos.

Implementar una Plantilla Responsiva

Este blog ha pasado por muchas etapas, por ejemplo durante unos años no tenía una plantilla responsiva que se adaptara el tipo de dispositivo, desde el año pasado seguimos los consejos y la observación directa que google realiza a los blogger para que hagan lo posible de poner plantillas responsivas en sus sitios. En esta web puedes encontrar muchas plantillas responsivas para blogger.


Descripción con Palabras Clave

Usamos en la descripción del blog palabras puntuales muy relacionadas con la temática de programación y las etapas del desarrollo de lenguajes compiladores. Realiza el análisis de palabras clave con planeador de palabras clave de google.


Incorporación de Meta Etiquetas

Incorporamos desde modo edición de código de la plantilla muchas meta etiquetas como Title, Keyword, Description, Author, etc.


Utilizamos TxtFull y TotalPing

Estos dos sitios permiten promocionar tu blog de forma gratuita, a cambio debes incorporar su enlace en una zona visible, parece que algunos blogger no les parece la idea pero eso será en nuestro caso cuando ya tengamos mejor posicionamiento o no sea necesaria mucha ayuda.


Componente de Visitantes en Línea.

En el sidebar a la derecha del blog hemos implementado un componente que muestra las últimas diez entradas visitadas. Es muy parecido al componente lo más leído, pero este es en tiempo real y ayuda a motivar los visitantes que den clic, tu sabes, a veces por pura curiosidad seguimos las tendencias de lectura y pensamos, si otros lo han leído es porque es útil.

Seguiremos agregando enlaces de referencia y más consejos. Por el momento quedamos aquí.

Read More

miércoles, 11 de marzo de 2015

Guia de Autómatas Finitos Deterministas (AFD) Parte1

3/11/2015 09:18:00 p.m. 0

Autómatas Finitos Deterministas (AFD). Parte I


Esta es una guía sobre autómatas finitos deterministas que trabajé hace un tiempo con mis estudiantes en la asignatura “Compiladores”, son varios ejemplos que te permitirán comprender los AFD, los ejemplos tienen como finalidad lo siguiente:


  • Evaluar el nivel de comprensión de los AFD.
  • Encontrar los elementos (A,S,F,q0,q1) del autómata partiendo del diagrama.
  • Crear la tabla de transición partiendo del diagrama.
  •  Identificar cuando un AF es o no determinista.

Como lecturas adicionales he publicado en los siguientes enlaces temas relacionados:

PARTE I: En esta primera parte el objetivo es poder comprender cuales son los símbolos de entrada, aceptación y de estado, también a partir del diagrama crear la tabla de transición.

EJEMPLO 1: A partir del siguiente diagrama

Automatas-Finitos-Deterministas-(AFD)-002
Determine:

Los símbolos de entrada              A
Los estados del diagrama             S
Los estados de aceptación           F
El estado inicial                             q1
Ejemplifique gramáticas válidas

SOLUCIÓN:
A = {a, b}
S = {q0, q1, q2}
F = {q0, q1}
q1 = {q0}
Gramáticas validas: aaaa, aba, a, bab, bababab


EJEMPLO 2: A partir del siguiente diagrama determine:

Automatas-Finitos-Deterministas-(AFD)-003

Determine:

Los símbolos de entrada              A
Los estados del diagrama             S
Los estados de aceptación           F
El estado inicial                              q1
Ejemplifique gramáticas válidas

SOLUCIÓN:
A = {a, b, c}
S = {q0, q1, q2}
F = {q0}
q1 = {q0}
Gramáticas validas: abb, aca, cacbaca, bbbaa, baccaaa


EJEMPLO 3: A partir del siguiente diagrama construya la tabla de transiciones y determine los siguientes datos.

Automatas-Finitos-Deterministas-(AFD)-004


Determine:

Los símbolos de entrada              A
Los estados del diagrama             S
Los estados de aceptación           F
El estado inicial                            q1
Ejemplifique gramáticas válidas

SOLUCIÓN:
A = {a, b, c}
S = {0, 1,2,3,4,5}
F = {1,4,5}
q1 = {0}

ESTADOS
ENTRADA DE DATOS
a
b
C
0
1
3
5
1
-
2
-
2
-
1
-
3
-
-
4
4
-
-
-
5
-
-
-


EJEMPLO 4: Construya una tabla de transiciones a partir del siguiente diagrama y escriba símbolos reconocidos por el autómata.

Automatas-Finitos-Deterministas-(AFD)-005


SOLUCIÓN:
ESTADOS
ENTRADA DE DATOS
0
1
1
2
2
2
-
2


EJEMPLO 5: Construya una tabla de transiciones a partir del siguiente diagrama y escriba símbolos reconocidos por el autómata.

Automatas-Finitos-Deterministas-(AFD)-006

SOLUCIÓN:
ESTADOS
ENTRADA DE DATOS
letra
:
Digito
=
1
2
3
5
-
2
2
-
2
-
3
-
-
-
4
4
-
-
-
-
5
-
-
5
-
 


EJEMPLO 6: Construya una tabla de transiciones a partir del siguiente diagrama y escriba un analizador léxico basado en esa tabla.
Automatas-Finitos-Deterministas-(AFD)-007
Gramática valida
Digito, digito, digito
[0-1][0-1][0-1]*    OK

Tabla de transiciones
ESTADOS
ENTRADA DE DATOS
digito
1
3
3
4
4
4


EJEMPLO 7: Dado el siguiente diagrama de transiciones obtener A, S, f, qi, F y decir que lenguaje se genera.
Automatas-Finitos-Deterministas-(AFD)-008
Obtener A, S, f, qi, F

A = {a, b}
S = {q0, q1, q2,q3,q4}
F = {q2,q3,q4}
q1 = {q0}

Tabla de transición


ESTADOS

ENTRADA DE DATOS

a
b
q0
q1, q4
q3
q1
q1
q2
q2
-
-
q3
-
-
q4
-
q4

Lenguaje que genera:

A(a/b)*
a/b*
b

EJEMPLO 8: Dado el siguiente diagrama de transiciones obtener A, S, f, qi, F y decir que lenguaje se genera.
Automatas-Finitos-Deterministas-(AFD)-009
Obtener A, S, f, qi, F
A = {a, b}
S = {q0, q1, q2,q3}
F = {q2}
q1 = {q0}

Tabla de transición


ESTADOS

ENTRADA DE DATOS

a
b
q0
q1
q3
q1
q3
q2
q2
q1
q3
q3
q3
q3

Lenguaje que genera:

A(a/b)


EJEMPLO 9: El siguiente diagrama, ¿Es un diagrama de transición correspondiente a un AFD? ¿Por qué si o porque no?
Automatas-Finitos-Deterministas-(AFD)-010
No es AFD porque existe más de una transición, con el mismo símbolo de entrada (el símbolo a sale de q0 a q1 pero también se retorna a q0), ya que por ello se caracterizan los autómatas finitos no deterministas.

Read More
Derechos Reservados. Postecnologia.com. Con tecnología de Blogger.

Post Top Ad