• Author / Uploaded
• Christian Pastor Urquiaga

• Categories
• Teoría de autómatas
• Métodos formales
• Teoría de la computación
• Modelos de computación
• Informática

Citation preview

UNIVERSIDAD NACIONAL DE TRUJILLO

PROCESADORES DIGITALES “PROGRAMACIÓN EN MICROCODE STUDIO PARA LEER UNA ECUACIÓN DE TERCER GRADO ORDENADA” INTEGRANTES:    

CARBAJAL VALDERRAMA, AXEL ESPINOLA VEGA, JOSEPH MORILLO MINCHOLA, GIORGINO PASTOR URQUIAGA, CHRISTIAN

ESCUELA: INGENIERIA DE SISTEMAS

2018

1

Indice I.

Introducción ......................................................................................................................... 3

II.

Objetivo General: ................................................................................................................ 4

III.

Marco Teórico: ................................................................................................................ 4

3.1.

Autómata:..................................................................................................................... 4

3.1.1. 3.2.

Polinomios ................................................................................................................... 7

3.2.1.

Grado de un polinomio ...................................................................................... 7

3.2.2.

Clases de polinomio ........................................................................................... 7

Desarrollo......................................................................................................................... 9

IV.

V.

Autómata finito determinista ............................................................................. 5

4.1.

Elaboración del autómata determinista ................................................................... 9

4.2.

Implementación del programa en Protheus ......................................................... 10

4.3.

Desarrollo del programa en MicroCode Studio .................................................... 11

4.4.

Simulación del programa en Protheus .................................................................. 22

Conclusiones ..................................................................................................................... 24

2

I.

Introducción

En el proyecto que se presenta a continuación se dará a conocer como se programó la lectura de un polinomio de tercer grado ordenado en MicroCode Studio y a la vez la implementación del mismo, en el programa Protheus para su posterior simulación. El equipo de trabajo se basó en la elaboración de un autómata determinista para desarrollar la lógica de lectura de dicho polinomio.

3

II.

Objetivo General:

Desarrollar un programa que sea capaz de leer una ecuación de tercer grado ordenada como entrada, y que valide si es correcta o incorrecta dependiendo lo ingresado.

III.

Marco Teórico:

3.1. Autómata: La teoría de autómatas es una rama de la teoría de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer. También son de gran utilidad en la teoría de la complejidad computacional. Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados un determinado estado y símbolo. La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene. Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si éste termina en el estado "acepta", el autómata acepta la palabra. Si lo hace en el estado "rechaza", el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

4

3.1.1. Autómata finito determinista Es el autómata finito que tiene todas sus transiciones no vacías y que por cada símbolo desde un estado de origen se llega a un único estado destino. Los AFD son definiciones ideales dentro de los lenguajes regulares por su cercanía formal hacia la creación de máquinas de reconocimiento fundamentalmente lexicográficas, en tanto sus transiciones son únicas por símbolo, pudiendo a la hora de su implementación en software, matemática y física realizarse con mayor facilidad. Sea un autómata finito definido por la 5-tupla A=, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones ó (léase: del estado qi mediante el terminal x se va a qj), F son los estados finales o de llegada dentro de Q, q0 es el estado inicial o de partida; se dice que A es un autómata finito determinista (AFD) si y sólo si se satisface en g las siguientes propiedades: 



Toda transición de g no es vacía (cosa que se cumple en este caso, debido a la definición particular de g que excluye de los símbolos de transición a las cadenas vacías, cosa que no sucede en la definición general de autómata finito donde ). Desde cualquier estado y con el mismo terminal solo se va a uno y solo un estado, es decir

.

En términos planos, esto significa que solo se podrá ir desde un estado A mediante el terminal x a un único estado B: 

y los siguientes casos:

 

.

Son transiciones de autómatas finitos no deterministas.

5

3.1.1.1. Consecuencias La definición formal de AFD se basa en la consideración de que las transiciones múltiples para un mismo símbolo y las vacías son indeseables sobre todo para la implementación material, fundamentalmente mecánica, de los autómatas finitos. En caso de uno de los usos más frecuentes de éstos, la modelación de analizadores lexicográficos de los elementos gramaticales de los lenguajes de programación, la exclusión del indeterminismo libra al sistema de dicho comportamiento y lo hace más específico y por tanto más potente. Una resultante evidente de la definición AFD es que en las tablas de transición de los mismos no hay más que un estado en cada casilla, haciendo más clara la interpretación y reconocimiento de cadenas mediante el reconocedor. En definitiva, los AFD son los autómatas finitos ideales, aunque no siempre pueden formalizarse a la primera y en no pocas ocasiones son el resultado de la depuración de AFND y de AFNDTV. Donde es bueno señalar que esta transformación siempre es posible.

3.1.1.2. Transformación de AFD a gramáticas regulares. Sea un AFD A=, éste puede transformarse a gramática regular G= (Q, conjunto de no terminales; T, conjunto de símbolos terminales; P, sistema de producciones de G y q0 es el símbolo de inicio), como puede verse los elementos de la 5-tupla del autómata finito se transforman directamente a los de la 4-upla de la grámatica regular. Luego el sistema de producciones P se contruye a partir de las transiciones g mediante los pasos:

1. Transición: ó se convierte en . 2. Transición a estado final: donde B es un estado final, ó 3. Lazo: ó

se convierte en

.

se convierte en

.

4. Lazo en estado final: donde A es un estado final, ó convierte en .

6

se

3.2. Polinomios Un polinomio es una expresión algebraica compuesta de dos o más monomios. Un polinomio es una expresión algebraica de la forma:

Siendo an, an-1 … a1, a0 números, llamados coeficientes.

a0 Es el término independiente. 3.2.1. Grado de un polinomio El grado de un polinomio P(x) es el mayor exponente al que se encuentra elevada la variable x.  Polinomio de grado cero P(x)= 2  Polinomio de primer grado P(x)= 3x + 2  Polinomio de segundo grado P(x)= 2x2 + 3x + 2  Polinomio de tercer grado P(x)= x3 - 2x2 + 3x + 2  Polinomio de cuarto grado P(x)= x4 + x3 - 2x2 + 3x + 2

3.2.2. Clases de polinomio  Polinomio Nulo El polinomio nulo tiene todos sus coeficientes nulos.  Polinomio Homogéneo El polinomio homogéneo tiene todos sus términos o monomios con el mismo grado.

7

 Polinomio Heterogéneo Los términos de un polinomio heterogéneo son de distinto grado.

 Polinomio Completo Un polinomio completo tiene todos los términos desde el término independiente hasta término de mayor grado.

 Polinomio Ordenado Un polinomio está ordenado si los monomios que lo forman están escritos de mayor a menor grado

8

IV.

Desarrollo

4.1.

Elaboración del autómata determinista

Para realizar nuestro autómata determinista, tuvimos que tener presente la forma de una ecuación de tercer grado ordenada y heterogénea, sin importar que sea completa. Como observamos por cada cambio de estado se estará leyendo un elemento de la ecuación de tercer grado. Siendo el estado inicial el número 0 y el estado final el número 12.

9

4.2. Implementación del programa en Protheus Se usó un KeyPad-Calculator para recepcionar las entradas emitidas por el usuario, además se usó un PIC 16F876 que se encargara de procesar el programa realizado en MicroCode, y un LM041L que se encarga de mostrar al usuario si la ecuación ingresada es correcta, validando si esta es de tercer grado y ordenada.

10

4.3. Desarrollo del programa en MicroCode Studio DEFINE OSC 4 DEFINE LCD_DREG PORTC DEFINE LCD_DBIT 4 DEFINE LCD_RSREG PORTB DEFINE LCD_RSBIT 5 DEFINE LCD_RWREG PORTB DEFINE LCD_RWBIT 6 DEFINE LCD_EREG PORTB DEFINE LCD_EBIT 7 DEFINE LCD_BITS 4 DEFINE LCD_LINES 2 DEFINE LCD_COMMANDUS 2000 DEFINE LCD_DATAUS 50 LOW PORTB.6 TRISA= %000000 TRISB = %11111111 TRISC = %00000000 LEC VAR BYTE TECLA VAR BYTE TECLA = 250 ACT VAR BIT ACT=1 TAM VAR BYTE TAM = 22 NUM VAR BYTE[22] I VAR BYTE ESTADO VAR BYTE ESTADO = 0

11

COND VAR BIT COND = 1 TEMP VAR BYTE CONT VAR BYTE REPIT VAR BIT J VAR BYTE 'coeficientes: SIG_A VAR BYTE SIG_B VAR BYTE SIG_C VAR BYTE SIG_D VAR BYTE A VAR BYTE B VAR BYTE C VAR BYTE D VAR BYTE CURSOR VAR BYTE lcdout $FE,128+70,"EMPEZAR" lcdout $FE,128 LCDOUT $FE,$0E

INICIO: TRISB = %11111111 PORTA = 63 LEC = PORTB IF LEC0 AND ACT=1 THEN GOSUB TECLADO IF LEC=0 AND ACT=0 THEN ACT=1 if tecla250 then GOSUB PANTALLA PAUSE 10 GOSUB coeficientes GOTO INICIO TECLADO: ACT=0 TECLA = "@" PORTA = 1 LEC = PORTB 12

IF LEC=1 THEN TECLA="#" GOSUB BORRADO ENDIF IF LEC=4 THEN TECLA="^" IF LEC=8 THEN TECLA="Y" PORTA = 2 LEC = PORTB IF LEC=1 THEN IF LEC=2 THEN IF LEC=4 THEN IF LEC=8 THEN

TECLA="7" TECLA="4" TECLA="1" tecla="0"

PORTA = 4 LEC = PORTB IF LEC=1 THEN IF LEC=2 THEN IF LEC=4 THEN IF LEC=8 THEN

TECLA="8" TECLA="5" TECLA="2" GOSUB COEFICIENTES

PORTA = 8 LEC = PORTB IF LEC=1 THEN IF LEC=2 THEN IF LEC=4 THEN IF LEC=8 THEN

TECLA="9" TECLA="6" TECLA="3" tecla="="

PORTA = 32 LEC = PORTB IF LEC=1 THEN TECLA="X" IF LEC=2 THEN TECLA="-" IF LEC=4 OR lec=8 THEN TECLA="+" IF I="0" AND TECLA0 then FOR J = 0 TO I-1 STEP 1 SELECT CASE ESTADO CASE 0 if NUM[J] = "Y" THEN ESTADO = 1 ELSE ESTADO = 99 ENDIF CASE 1 if NUM[J] = "=" THEN ESTADO = 2 ELSE ESTADO = 99 ENDIF CASE 2 if NUM[J] = "+" OR NUM[J] = "-" THEN ESTADO = 3 'signo coeficiente A SIG_A=NUM[J] ELSEIF NUM[J]>="0" AND NUM[J]="0" AND NUM[J]="1" AND NUM[J]="1" AND NUM[J]="0" AND NUM[J]