martes, 26 de mayo de 2015
lunes, 25 de mayo de 2015
CÓDIGO EN C++ DE LAS REGLAS DE PRODUCCIÓN (Muestra de los símbolos terminales).
CENTRO UNIVERSITARIO UAEM
ATLACOMULCO
LICENCIATURA EN INGENIERÍA EN COMPUTACIÓN
NOMBRE DEL DOCENTE:
INGENIERO. HÉCTOR
CABALLERO HERNÁNDEZ
NOMBRE MATERIA:
AUTÓMATAS Y LENGUAJES FORMALES
NOMBRE
DE LA ALUMNA:
HEIVILINA PÉREZ
ARIAS
GRUPO:
ICO-19
TURNO:
TRABAJO A ENTREGAR:
CÓDIGO EN C++ DE LAS REGLAS DE PRODUCCIÓN (Muestra de los símbolos
terminales).
FECHA DE ENTREGA:
MAYO DE 2015.
CÓDIGO EN C++ DE LAS REGLAS DE PRODUCCIÓN (Muestra de los símbolos terminales).
#include <iostream>
#include <string>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
FILE *doc;
using namespace std;
void introducirLetra (char *,char
*,char *, int);
void mostrarReglasDeProduccion();
void lecturaDeArchivo();
const int num=1000;
struct Gramaticas{
char regla[100];
char
produccion[100];
char
letras[100];
};
Gramaticas gram[num];
int main(int argc, char** argv) {
cout<<"\nCENTRO
UNIVERSITARIO UAEM ATLACOMULCO "<<endl;
cout<<"\nAUTOMATAS
Y LENGUAJES FORMALES"<<endl;
cout<<"\nPROGRAMA
DE REGLAS DE PRODUCCION"<<endl;
cout<<"\t(Salida
de simbolos terminales)"<<endl;
cout<<"\nELABORADO
POR:"<<endl;
cout<<"---->
HEIVILINA PEREZ ARIAS"<<endl;
cout<<"---->
MAYTE RICARDO CRUZ"<<endl;
lecturaDeArchivo();
mostrarReglasDeProduccion
();
system("pause");
return EXIT_SUCCESS;
}
void lecturaDeArchivo(){
ifstream
lecturaArchivo("produccion.txt", ios::in);
if(!lecturaArchivo){
cerr<<"No
se pudo abrir el archivo"<<endl;
exit(1);
}
char
reglas[100];
char
producciones[100];
char
variables[100];
int
i=0;
while(lecturaArchivo>>reglas>>producciones>>variables){
introducirLetra(reglas,producciones,variables,i);
i++;
}
}
void introducirLetra(char
*nx,char *ox,char *dx, int posicion){
if(posicion==-1){
cout<<"Ya
no hay lugar"<<endl;
return;
}
strcpy
(gram[posicion].regla, nx);
strcpy
(gram[posicion].produccion,ox);
strcpy
(gram[posicion].letras, dx);
}
void mostrarReglasDeProduccion(){
ofstream
salida("salida.txt");
doc=fopen("salida.txt","a+");
cout<<endl;
cout<<setw(10)<<"REGLAS
DE PRODUCCION(simbolos terminales)"<<' '<<endl;
cout<<endl;
for(int
i=0; i<num;i++){
if(strcmp(gram[i].letras,"")!=0){
cout<<setw(10)<<gram[i].letras<<' '<<endl;
doc=fopen("salida.txt",
"a+");
}
}
}
domingo, 24 de mayo de 2015
CODIGO EN C++ PARA REALIZAR UN ARBOL BINARIO Y SUS RECORRIDOS
CENTRO UNIVERSITARIO UAEM
ATLACOMULCO
LICENCIATURA EN
INGENIERÍA EN COMPUTACIÓN
NOMBRE DEL DOCENTE:
INGENIERO.
HÉCTOR CABALLERO HERNÁNDEZ
NOMBRE MATERIA:
AUTÓMATAS Y LENGUAJES FORMALES
NOMBRE DE LA ALUMNA:
HEIVILINA PÉREZ ARIAS
GRUPO:
ICO-19
TURNO:
MATÚTINO
TRABAJO A ENTREGAR:
CODIGO EN C++ PARA REALIZAR UN
ARBOL BINARIO Y SUS RECORRIDOS
FECHA DE ENTREGA:
MAYO DE 2015.
CODIGO EN C++ PARA REALIZAR UN ARBOL BINARIO Y SUS
RECORRIDOS
#include <iostream>
#include <string>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
#include <cstdlib>
using namespace std;
/* run this program using the console pauser or add your own
getch, system("pause") or input loop */
//PROGRAMA QUE DEBERA AGRAGAR NUMEROS EN UNA ESTRUCTURA DE
DATOS DE UN ARBOL BINARIO
struct nodo{
int numero;
struct nodo
*izquierdo, *derecho;
};
typedef struct nodo *ARB;
ARB empezarNodo(int z){
ARB nuevonodo =
new(struct nodo);
nuevonodo->numero = z;
nuevonodo->izquierdo = NULL;
nuevonodo->derecho = NULL;
return nuevonodo;
}
void insertar(ARB &arbol, int z){
if(arbol==NULL){
arbol=empezarNodo(z);
}
else
if(z<arbol->numero)
insertar(arbol->izquierdo, z);
else
if(z>arbol->numero)
insertar(arbol->derecho, z);
}
void checarArbol(ARB arbol, int n){
if(arbol==NULL)
return;
checarArbol(arbol->derecho, n+1);
for(int i=0;
i<n; i++)
cout<<"--->";
cout<<arbol->numero<<endl;
checarArbol(arbol->izquierdo, n+1);
}
void Pre_Orden(ARB arbol){
if(arbol!=NULL){
cout<<arbol->numero<<" ";
Pre_Orden(arbol->izquierdo);
Pre_Orden(arbol->derecho);
}
}
void In_Orden(ARB arbol){
if(arbol!=NULL){
In_Orden(arbol->izquierdo);
cout<<arbol->numero<<" ";
In_Orden(arbol->derecho);
}
}
void Post_Orden(ARB arbol){
if(arbol!=NULL){
Post_Orden(arbol->izquierdo);
Post_Orden(arbol->derecho);
cout<<arbol->numero<<" ";
}
}
int main(int argc, char** argv){
system("Color 3");
cout<<"\nCENTRO UNIVERSITARIO UAEM
ATLACOMULCO"<<endl;
cout<<"\nAUTOMATAS Y LENGUAJES
FORMALES"<<endl;
cout<<"\nINTEGRANTES:"<<endl;
cout<<"\n ->HEIVILINA PEREZ
ARIAS"<<endl;
cout<<"\nELABORACION DE UN ARBOL
BINARIO Y SUS RECORRIDOS "<<endl;
cout<<" "<<endl;
int i;
ARB arbol =
NULL;
int n;
int z;
cout<<"Introdruzca la cantidad de nodos del arbol: ";
cin>>n;
cout<<endl;
for(int
i=0;i<n; i++){
cout<<"Introducir nodo numero
"<<i+1<<": ";
cin>>z;
insertar(arbol, z);
}
cout<<"\n Representacion de
arbol"<<endl;
checarArbol(
arbol, 0);
cout<<"\n\n Recorrido que realiza el arbol"<<endl;
cout<<
"..."<<endl;
cout<<"\n
In-orden : "; In_Orden(arbol);
cout<<"\n Pre-Orden :
"; Pre_Orden(arbol);
cout<<"\n Post-Orden : "; Post_Orden(arbol);
return 0;
}
Expresiones regulares
CENTRO UNIVERSITARIO UAEM
ATLACOMULCO
LICENCIATURA EN
INGENIERÍA EN COMPUTACIÓN
NOMBRE DEL DOCENTE:
INGENIERO.
HÉCTOR CABALLERO HERNÁNDEZ
NOMBRE MATERIA:
AUTÓMATAS Y LENGUAJES FORMALES
NOMBRE DE LA ALUMNA:
HEIVILINA PÉREZ ARIAS
GRUPO:
ICO-19
TURNO:
MATÚTINO
TRABAJO A ENTREGAR:
LENGUAJES REGULARES
FECHA DE ENTREGA:
MAYO DE 2015.
*GRAMATICAS REGULARES - EXPRESIONES REGULARES
**LENGUAJES REGULARES
Sea S = { a1, …, an} entonces definimos el conjunto de los lenguajes regulares en forma recursiva como
sigue:
Casos Base:
· { } es un lenguaje regular
· {l} es un lenguaje regular
· " 1 £ i £ n {a1} es un lenguaje regular
Casos Inductivos
· Si L1 es un lenguaje regular Ù L2 es un lenguaje regular ⇒ (L1.L2) es un lenguaje regular
· Si L1 es un lenguaje regular Ù L2 es un lenguaje regular ⇒ (L1ÈL2) es un lenguaje regular
· Si L1 es un lenguaje regular ⇒ L* es un lenguaje regular
· Si L1 es un lenguaje regular ⇒ L+ es un lenguaje regular
Ejemplo:
S = { a,b,c}
L1 = {a, ab, b, ccc} es regular? SI.
Demostración:
1. Si considero los lenguajes:
L11 ={a} L12 ={ab} L13 ={b} L14 ={ccc}
puedo decir que L1 = L11 È L12 È L13 È L14
2. L11 es regular? Sí, por 3er caso base.
Lo mismo ocurre con L13
3. L12 es regular?
Puedo decir que L12 = L11 . L13
Por lo tanto, por primer caso inductivo, L12 es regular
4. L14 es regular?
Si considero el lenguaje L15 = {c}
Puedo decir que L14 = L15 . L15 . L15
Por lo tanto, por primer caso inductivo, L14 es regular
5. Entonces, si volvemos al principio:
L1= {a} È {ab} È {b} È {ccc}
Podemos decir, por 2do caso inductivo, que L1 es regular
**Expresiones regulares
Se denominan expresiones regulares sobre un alfabeto A, a las expresiones que se pueden construir a
partir de las siguientes reglas:
- Æ es una expresión regular que describe el lenguaje vacío;
- l es una expresión regular que describe el lenguaje {l}, esto es el lenguaje que contiene
únicamente la cadena vacía;
- Para cada símbolo a Î A, a es una expresión regular que describe el lenguaje {a}, esto es el
lenguaje que contiene únicamente la cadena a;
- Si r y s son expresiones regulares que describen los lenguajes L(r) y L(s) respectivamente:
i) r / s es una expresión regular que describe el lenguaje L(r) È L(s)
ii) r . s es una expresión regular que describe el lenguaje L(r) . L(s)
iii)r* es una expresión regular que describe el lenguaje L(r)*.
El operador de clausura es el que tiene mayor precedencia, seguido por el operador de concatenación y
por último el operador de unión.
Las expresiones regulares describen los lenguajes regulares (aquellos reconocidos por autómatas finitos).
Por ejemplo las siguientes son expresiones regulares válidas:
- a* . b que describe el lenguaje L = {anb / n ³ 0}
- (a / b)* que describe el lenguaje L = { x / x Î {a, b}* }
UNIDAD ARITMÉTICA Y LÓGICA (ALU)
CENTRO UNIVERSITARIO UAEM
ATLACOMULCO
LICENCIATURA EN
INGENIERÍA EN COMPUTACIÓN
NOMBRE DEL DOCENTE:
INGENIERO.
HÉCTOR CABALLERO HERNÁNDEZ
NOMBRE MATERIA:
AUTÓMATAS Y LENGUAJES FORMALES
NOMBRE DE LA ALUMNA:
HEIVILINA PÉREZ ARIAS
GRUPO:
ICO-19
TURNO:
MATÚTINO
TRABAJO A ENTREGAR:
UNIDAD ARITMÉTICA Y LÓGICA
(ALU)
FECHA DE ENTREGA:
MAYO DE 2015.
UNIDAD ARITMÉTICA Y LÓGICA
(ALU)
Una
unidad aritmética lógica puede realizar un conjunto de operaciones aritméticas
básicas y un conjunto de operaciones lógicas, a través de líneas de selección.
En inglés ALU significa Arithmetic Logic Unit (Unidad
Aritmética Lógica). La figura 3.12.1. Muestra el diagrama de bloques de
una ALU.RE
Figura 3.12.1. Diagrama de bloques de una ALU
Las cuatro entradas de A se combinan con las de B generando
una operación de salida de cuatro bits en F. La entrada de
selección de modo S2 distingue entre las
operaciones aritméticas y lógicas. Las entradas de selección S0 y S1 determinan
la operación aritmética o lógica. Con las entradas S0 y S1 se
pueden elegir cuatro operaciones aritméticas (con S2 en
un estado) y cuatro logicas (con S2 en otro
estado). Los acarreos de entrada y salida tienen sentido únicamente en las
operaciones aritmét icas. El diseño de una ALU implica el
diseño de la sección aritmética, la sección lógica y la modificación de la
sección aritmética para realizar las operaciones aritméticas y lógicas.
Sección
Lógica
Los
datos de entrada en una operación lógica son manipulados en forma separada y
los bits son tratados como variables binarias. En la tabla 3.12.1. se listan cuatro
operaciones lógicas OR, OR - Exclusiva, AND y NOT.
En el circuito, las dos líneas de selección (S1, S0)
permiten seleccionar una de las compuertas de entrada, correspondientes a la
función Fi .
|
S1
|
S0
|
Salida
|
Función Fi
|
|
0
|
0
|
F=Ai+Bi
|
OR
|
|
0
|
1
|
F=AiÅBi
|
XOR
|
|
1
|
0
|
F=Ai·Bi
|
AND
|
|
1
|
1
|
F=A'i
|
NOT
|
Tabla 3.12.1. Tabla de Función Lógica.
El
circuito lógico de la fig ura 3.12.2 es una etapa de un circuito lógico
de n bits.
Figura 3.12.2. Diagrama lógico de un circuito
lógico de una ALU
Sección
Aritmética
El
componente básico de la sección aritmética es un sumador en paralelo. Las operaciones aritméticas
configuradas en el circuito aritmético se presentan en la tabla 3.12.2. En
una ALU, la suma aritmética se puede implementar con un número
binario en A, otro número en la entrada B y el
acarreo de entrada Cin en un valor lógico 0.
El resto de las funciones se enuncian en la columna descripción.
|
Selección de Función
|
Salida N
|
Función
|
Descripción
|
||
|
S1
|
S0
|
Cin
|
N
|
F
|
|
|
0
|
0
|
0
|
0
|
A
|
Transferir A
|
|
0
|
0
|
1
|
0
|
A+1
|
Incrementar A
|
|
0
|
1
|
0
|
B
|
A+B
|
Suma ó agregar B a A
|
|
0
|
1
|
1
|
B
|
A+B+1
|
Suma con accarreo ó agregar B a A más 1
|
|
1
|
0
|
0
|
B’
|
A+B’
|
Agregar el complemento de 1 de B a A
|
|
1
|
0
|
1
|
B’
|
A+B’+1
|
Agregar el complemento de 2 de B a A
|
|
1
|
1
|
0
|
Todos unos
|
A-1
|
Decrementar A
|
|
1
|
1
|
1
|
Todos unos
|
A
|
Trasferir A
|
Tabla
3.12.2. Tabla de la Función F en un Circuito Aritmético
La
implementación de las funciones anteriores por medio de un circuito lógico
sencillo se describe a continuación. El circuito se diseña bajo el precepto de
intervenir cada entrada Bi para obtener las
siguientes funciones:
|
S1
|
S0
|
Ni
|
|
0
|
0
|
0
|
|
0
|
1
|
Bi
|
|
1
|
0
|
Bi'
|
|
1
|
1
|
1
|
Tabla 3.12.3. Tabla del circuito para la entrada Bi
La figura 3.12.3.
muestra el circuito.
Figura 3.12.3. Circuito para la tabla 3.12.2.
Por
medio de estas funciones se pueden lograr las funciones de la tabla 3.12.2 al
agregar el número Ni (tabla 3.12.3) a la entrada A a través de
un sumador en paralelo para cada etapa, teniendo en cuenta el valor de la
entrada Cin. El circuito combinacional aritmético se muestra en la
figura 3.12.4. En la figura, la entrada A se denomina Mi en el
sumador completo.
Figura 3.12.4. Circuito aritmético
Diseño de una
Unidad Aritmética Lógica
En
el diseño de una ALU se deben seguir los siguientes pasos:
1.
Diseñar la sección aritmética
independientemente de la sección lógica.
2.
Determinar las operaciones lógicas
del circuito aritmético, asumiendo que los acarreos de salida de todas las
etapas son 0.
3.
Modificar el circuito aritmético para
obtener las operaciones lógica requeridas.
El
diseño simple de una ALU se hace utilizando el sumador completo para generar
las operaciones lógicas de la unidad. Por lo tanto es necesario introducir una
variable de control adicional (S2), con el fin de seleccionar entre las operaciones
lógicas y aritméticas. En este diseño, un valor S2 = 1 hace que el circuito efectúe operaciones lógicas. Recordando la salida de un sumador completo:
F = (Ai Å Bi) Å Cin
A
partir de esta ecuación, es posible obtener la función lógica requerida,
utilizando la debida manipulación lógica. La función requerida se expone en la
tabla 3.12.4.
|
S2
|
S1
|
S0
|
Ai
|
Bi
|
Cin
|
Operación Sumador Completo
|
Función requerida Fi
|
Manipulación
|
Salida
|
|
1
|
0
|
0
|
Ai
|
0
|
0
|
Ai
|
OR
|
Aplicar una función OR Ai +
Bi
|
Ai+Bi
|
|
1
|
0
|
1
|
Ai
|
Bi
|
0
|
Ai Å Bi
|
XOR
|
Ninguna
|
AiÅBi
|
|
1
|
1
|
0
|
Ai
|
Bi'
|
0
|
Ai·Bi
|
AND
|
Aplicar una función OR Ai +
Bi'
|
Ai·Bi
|
|
1
|
1
|
1
|
Ai
|
1
|
0
|
A'i
|
NOT
|
Ninguna
|
A'i
|
Tabla 3.12.4. Tabla de obtención de las funciones
lógicas con un sumador completo
Partiendo
de la tabla 3.12.4., las entradas Mi, Ni y Cini en
un sumador completo, son equivalentes a las siguientes expresiones:
Mi = Ai + S2·S1'·S0'·Bi + S2·S1·S0'·Bi'
Ni = S0·Bi + S1·Bi'
Cini = S2'·Ci
La
figura 3.12.5. muestra el diagrama de la unidad aritmética lógica de dos
etapas.
Figura 3.12.5. Diagrama lógico de una ALU
Las
doce operaciones generadas en el ALU se resumen en la tabla
3.12.5., la función en particular se selecciona a través de S2, S1, S0 y Cin.
Las operaciones aritméticas son las mismas del circuito aritmético.
|
Selección
|
Salida F
|
hDescripción
|
|||
|
hS2
|
hS1
|
hS0
|
Cin
|
F
|
|
|
0
|
0
|
0
|
0
|
A
|
Trasferir A
|
|
0
|
0
|
0
|
1
|
A+1
|
Incrementar A
|
|
0
|
0
|
1
|
0
|
A+B
|
Suma
|
|
0
|
0
|
1
|
1
|
A+B+1
|
Suma con accarreo
|
|
0
|
1
|
0
|
0
|
A-B-1
|
Resta con préstamo
|
|
0
|
1
|
0
|
1
|
A-B
|
Sustracción
|
|
0
|
1
|
1
|
0
|
A-1
|
Decrementar A
|
|
0
|
1
|
1
|
1
|
A
|
Transferir A
|
|
1
|
0
|
0
|
X
|
A+B
|
OR
|
|
1
|
0
|
1
|
X
|
A Å B
|
OR-Exclusiva
|
|
1
|
1
|
0
|
X
|
A·B
|
AND
|
|
1
|
1
|
1
|
X
|
A’
|
Complementar A
|
Tabla 3.12.5. Tabla de verdad de una ALU
Suscribirse a:
Comentarios (Atom)