tixtix_practica2

Vista previa del material en texto

INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE CÓMPUTO
PRÁCTICA NO. 2
OPERACIONES CON LENGUAJES
UNIDAD DE APRENDIZAJE: TEORIA DE LA COMPUTACIÓN
GRUPO: 4CM1
EQUIPO: tixtix
INTEGRANTES:
ALVAREZ CAMPOS SAUL MIGUEL	
	MEDINA ANGELES ANA CRISTINA
	MORALES MARTÍNEZ JOSÉ ANTONIO
PROFESORA: SANCHEZ GARCIA LUZ MARIA
FECHA: 04 DE MAYO DE 2023
OBJETIVO
Realizar un programa en lenguaje C que dado un alfabeto Σ={0,1}, realice operaciones con los siguientes dos lenguajes:
L = {1,10,100}
M = {10, 01, 11}
PLANTEAMIENTO DEL PROBLEMA
El problema que resolveremos en esta práctica es realizar de forma correcta las operaciones con lenguajes siguientes: unión, intersección, diferencia, concatenación e inverso. 
Para el desarrollo de esta, se tiene en cuenta la definición de un alfabeto, de una cadena, lenguajes, así mismo como el concepto y propiedades de las operaciones a realizar mencionadas anteriormente. Para la implementación de cada operación utilizaremos el lenguaje c++ y el uso de funciones.
Finalmente se podrá observar las características, consideraciones y propiedades de las operaciones con lenguajes sobre un alfabeto. 
ACTIVIDADES
1. Programar en ANSI C, cada una de las siguientes operaciones:
· Unión N= {1, 01, 10, 11, 100}
· Intersección N= {10}
· Diferencia L-M = {1, 100} M – L= {01, 11}
· Concatenación LM = {110, 101, 111, 1010, 1001, 1011, 10010, 10001, 10011} ML= {101, 1010, 10100, 011, 0110, 01100, 111, 1110, 11100}
· Inverso L= {1, 01, 001} y M= {01, 10, 11}
2. El programa deberá ser capaz de recibir al cualquier número de cadenas binarias sobre Σ={0,1} para realizar cada una de las operaciones. Cadenas que no sean binarias, serán rechazadas.
3. Usar un menú de opciones para que el usuario elija el tipo de operación a realizar, el cual debe iterar hasta que el usuario desee abandonar el programa.
4. Mostrar la salida en pantalla de cada uno de los resultados de las operaciones con cadenas.
5. Finalmente responda a las siguientes preguntas
a) ¿Cuál de las operaciones es más fácil de implementar?
La unión fue la operación más fácil de implementar. Esto se debe al uso de la estructura de datos (set) la cual solo acepta valores únicos (keys). Con esta estructura que además es dinámica, se pueden agregar los elementos de ambos lenguajes en un set y finalmente basta con imprimir mediante iteradores el contenido de esta estructura de datos.
b) ¿Cuál de las operaciones es el más difícil de implementar?
La operación más laboriosa de implementar fue la diferencia, sin embargo, con el método erase de un vector el trabajo se simplifica. Retomando la definición de la diferencia, son todos los elementos que se encuentran en un lenguaje, pero no en el otro. Con ello, resultó conveniente copiar los elementos del lenguaje minuendo a un vector, si estos elementos se encuentran en el otro lenguaje, se eliminan dado que un vector es una estructura dinámica, cuando se usa el método erase, el vector modifica el número de elementos e un índices sin dejar un espacio en el arreglo del elemento borrado. 
c) ¿Cuáles fueron los errores que se presentaron al programar las operaciones en su programa?
Algunos errores que presentamos al programar las operaciones solicitadas en esta práctica fueron el manejo de arreglos y cadenas de caracteres. 
Al trabajar con vectores y arreglos de string para manipular las cadenas de cada uno de los lenguajes, el tamaño fijo de los arreglos y el acceso a los elementos fueron un problema. De la misma forma, la implementación de cada una de las operaciones resulto en un principio complicada, ya que no se consideraban casos especiales, manejo incorrecto de las excepciones, o se realizaba una mala implementación de la operación, mismo que resultaba en errores en el programa, tal como en la operación unión, que una cadena no puede repetirse, pero en la concatenación si puede existir una misma cadena más de una vez.
d) Escriba las aplicaciones que pueden tener las operaciones con lenguajes.
Las operaciones con lenguajes son fundamentales en el estudio de lenguajes formales y tienen diversas aplicaciones en diferentes campos, como:	
Unión: La operación de unión se utiliza para combinar dos lenguajes. Algunas aplicaciones comunes incluyen:
· La creación de un lenguaje que contiene todas las palabras de dos lenguajes diferentes.
· La combinación de dos conjuntos de reglas de producción en una gramática.
· La combinación de dos conjuntos de expresiones regulares para crear una nueva expresión que acepte las cadenas aceptadas por cualquiera de las dos expresiones originales.
Intersección: La operación de intersección se utiliza para encontrar las cadenas comunes entre dos lenguajes. Algunas aplicaciones comunes incluyen:
· La identificación de las palabras que se encuentran tanto en el diccionario de inglés como en el de español.
· La creación de un lenguaje que contenga solo las palabras que se encuentran tanto en un lenguaje como en otro.
· La eliminación de las cadenas que no cumplen ciertas propiedades comunes entre dos lenguajes.
Diferencia: La operación de diferencia se utiliza para eliminar las palabras que se encuentran en un lenguaje, pero no en otro. Algunas aplicaciones comunes incluyen:
· La eliminación de las palabras en una lista negra de palabras prohibidas.
· La creación de un lenguaje que contenga solo las palabras que se encuentran en un lenguaje, pero no en otro.
· La eliminación de ciertas cadenas que no cumplen con ciertas propiedades en un lenguaje.
Concatenación: La operación de concatenación se utiliza para unir dos cadenas. Algunas aplicaciones comunes incluyen:
· La creación de una nueva palabra a partir de dos palabras existentes.
· La unión de dos cadenas de bits para formar una cadena de bits más larga.
· La construcción de una URL completa a partir de una URL base y un camino relativo.
Inverso: La operación de inverso se utiliza para invertir el orden de una cadena. Algunas aplicaciones comunes incluyen:
· La inversión del orden de una cadena de caracteres para que se lea de derecha a izquierda.
· La creación de una versión invertida de una cadena de ADN.
· La inversión del orden de las palabras en una oración.
e) ¿Qué recomendaciones daría a nuevos equipos para realizar esta práctica?
La primera recomendación y más importante, es primero entender cómo funciona la operación de lenguaje en lápiz y papel y dominarla, antes de empezar la programación, esto facilitará la abstracción del algoritmo además de que, si se tiene idea del algoritmo a seguir, la codificación se vuelve sumamente sencilla y rápida. 
Otra recomendación respecto al lenguaje de programación que se está usando es antes de programar una función básica que ayude a la realización de tu algoritmo, es una buena idea verificar en la documentación del lenguaje si no existe ya un método o función que realice lo que se desea programar. 
Finalmente, en caso de estar trabajando en equipo, una buena idea es usar un IDE en el que todos puedan colaborar al mismo tiempo, algo similar a los documentos de Google. Nuestro equipo optó por el uso de replit IDE en línea que permite usar todas las herramientas propias de un IDE como visual studio code, pero puede ser ejecutado en cualquier navegador web.
PRUEBAS
Cadena rechazada
Lenguajes aceptados
Menú de opciones
Unión
Intersección
Diferencia
Concatenación 
Inverso
ANEXO
/*
    Titulo: Operaciones con lenguajes
    Descripción: Programa en c++ que dado un alfabeto Σ={0,1} realiza
   operaciones con lenguajes: 
   ->unión
   ->intersección
   ->diferencia
   ->concatenación
   ->inverso 
   Fecha: 04/05/2023 Versión: 1.0 Autores: Saúl Miguel Alvarez Campos, Ana Cristina Medina Angeles y José Antonio Morales
*/
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
/*Función que recibe como parametro la cadena de entrada y en base a ello no
 * realiza ninguna accion en caso de que la cadena sea aceptada, si la cadena es
 * invalida se muestra un mensaje alusivo al problema y se sale del programa.
 */
void validar_cadena(stringcadena) {
  int i;
  // Recorre el arreglo
  for (i = 0; i < cadena.size(); i++)
    // Si encuentra un caracter distinto de 0 y 1, el programa termina
    if (cadena[i] != '0' && cadena[i] != '1') {
      cout << "\nLa cadena " + cadena + " fue rechazada";
      exit(0);
    }
}
/*Función que recibe como parametro 2 arreglos de cadenas junto con 2 enteros que 
 * representan el tamaño de estos arreglos, la función realiza la operación de union
 * con ayuda de un set, al finalizar se imprime esta estructura de datos, no regresa ningun valor
 */
void Union(string L[], string M[], int l, int m) {
  set<string> uni;
  // Inserta las cadenas del lenguaje L en un set
  for (int i = 0; i < l; i++)
    uni.insert(L[i]);
  // Inserta las cadenas del lenguaje M en el set
  for (int i = 0; i < m; i++)
    uni.insert(M[i]);
  // Imprimir los caracteres mediante un for each
  cout << "{";
  for (auto it = uni.begin(); it != uni.end(); ++it) {
    if (it == uni.begin())
      cout << *it;
    else
      cout << ", " << *it;
  }
  cout << "}\n" << endl;
}
/*Función que recibe como parametro 2 arreglos de cadenas junto con 2 enteros que 
 * representan el tamaño de estos arreglos, la función realiza la operación de interseccion
 * con ayuda de un vector, al finalizar se imprime esta estructura de datos, no regresa ningun valor
 */
void interseccion(string L[], string M[], int l, int m) {
  vector<string> aux;
  // Recorre los arreglos L y M
  for (int i = 0; i < l; i++) {
    for (int j = 0; j < m; j++) {
      // Si encuentra una cadena que este en L y M la saca del arreglo aux
      if (L[i] == M[j])
        aux.push_back(L[i]);
    }
  }
  // Imprime los caracteres
  cout << "{";
  for (int i = 0; i < aux.size(); i++) {
    if (i == 0)
      cout << aux[i];
    else
      cout << ", " << aux[i];
  }
  cout << "}\n" << endl;
}
/*Función que recibe como parametro 2 arreglos de cadenas junto con 2 enteros que 
 * representan el tamaño de estos arreglos, la función realiza la operación de diferencia
 * mediante un vector el cual se le aplica el metodo erase (se usanel atributo de begin como+i como si se 
 *tratase de un iterador)en caso de que se encuentre la cadena en 
 *el otro arreglo, al finalizar se imprime el vector resultante de la diferencia tanto L-M  AUX(1)
 *como M-L aux (2).
 */
void diferencia(string L[], string M[], int l, int m) {
  vector<string> aux, aux2;
  // Se copia el arreglo de cadenas a un vector
  for (int i = 0; i < l; i++) {
    aux.push_back(L[i]);
  }
  // Se copia el segundo arreglo de cadenas a otro vector auxiliar
  for (int i = 0; i < m; i++) {
    aux2.push_back(M[i]);
  }
  // L-M
  for (int i = 0; i < l; i++) {
    for (int j = 0; j < m; j++) {
      if (aux[i] == M[j])
        aux.erase(aux.begin() + i);
    }
  }
  // M-L
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < l; j++) {
      if (aux2[i] == L[j])
        aux2.erase(aux2.begin() + i);
    }
  }
  // Imprime L - M
  cout << "L - M = {";
  for (int i = 0; i < aux.size(); i++) {
    if (i == 0)
      cout << aux[i];
    else
      cout << ", " << aux[i];
  }
  cout << "}" << endl;
  // Imprime M - L
  cout << "M - L = {";
  for (int i = 0; i < aux2.size(); i++) {
    if (i == 0)
      cout << aux2[i];
    else
      cout << ", " << aux2[i];
  }
  cout << "}\n" << endl;
}
/*Función que recibe como parametro 2 arreglos de cadenas junto con 2 enteros que 
 * representan el tamaño de estos arreglos, la función realiza la operación de concatenación
 * para ello agrega a un vector resultado, la concatenación (L1+L2) de todos los caracteres de ambos
 *arreglos de cadenas, al finalizar se imprime el resultado dentro de la función 
 */
void concatenacion(string L[], string M[], int l, int m) {
  vector<string> aux;
  // Recorre el arreglo
  for (int i = 0; i < l; i++)
    for (int j = 0; j < m; j++)
      // Copia L[i]+M[j] a aux
      aux.push_back(L[i] + M[j]);
  // Imprime LM
  cout << "{";
  for (int i = 0; i < (l * m); i++) {
    if (i == 0)
      cout << aux[i];
    else
      cout << ", " << aux[i];
  }
  cout << "}\n" << endl;
}
/*Función que recibe como parametro 2 arreglos de cadenas junto con 2 enteros que 
 * representan el tamaño de estos arreglos, la función realiza la operación de inversion 
 *para ello se hace uso del metodo reverse en cada cadena que compone el lenguaje, al finalizar 
 *se imprime el resultado
 */
void inverso(string l[], int n) {
  vector<string> aux;
  // Copia el lenguaje l en aux
  for (int i = 0; i < n; i++)
    aux.push_back(l[i]);
  // Invierte cada cadena de aux
  for (int i = 0; i < n; i++)
    reverse(aux[i].begin(), aux[i].end());
  // Imprime los caracteres
  cout << "{";
  for (int i = 0; i < aux.size(); i++) {
    if (i == 0)
      cout << aux[i];
    else
      cout << ", " << aux[i];
  }
  cout << "}" << endl;
}
int main() {
  int op = 0, l, m;
  cout << "\t\tOPERACIONES CON LENGUAJES" << endl;
  // Lenguaje L
  cout << "Ingresa el numero de cadenas del lenguaje L: " << endl;
  cin >> l;
  string L[l];
  for (int i = 0; i < l; i++) {
    cout << "Ingresa la cadena " << i + 1 << " del lenguaje L: " << endl;
    cin >> L[i];
    // Validación del lenguaje L
    validar_cadena(L[i]);
  }
  // Lenguaje M
  cout << "\nIngresa el numero de cadenas del lenguaje M: " << endl;
  cin >> m;
  string M[m];
  for (int i = 0; i < m; i++) {
    cout << "Ingresa la cadena " << i + 1 << " del lenguaje M: " << endl;
    cin >> M[i];
    //Validación del lenguaje M
    validar_cadena(M[i]);
  }
  system("clear");
  // Ciclo do-while que ietra hasta que el usuario seleccione salir del programa.
  do {
    // Se imprime el menu de opciones
    cout << "\t\tMenu de opciones" << endl;
    cout << "1. Unión\n2. Interseccion\n3. Diferencia\n4. Concatenacion\n5. "
            "Inverso\n6. Salir\n Que opcion desea realizar?"
         << endl;
    // Ingreso de la opcion del menu seleccionada por usuario
    cin >> op;
    /*mediante el switch se selecciona el bloque de código que realiza lo que el
     * usuario selecciona. En cada una de ellas se llama a la función en
     * cuestion y se realiza formato al texto para que sea visible al usuario*/
    switch (op) {
    case 1:
      system("clear");
      cout << "UNION\nN = ";
      Union(L, M, l, m);
      break;
    case 2:
      system("clear");
      cout << "INTERSECCION\nN = ";
      interseccion(L, M, l, m);
      break;
    case 3:
      system("clear");
      cout << "DIFERENCIA" << endl;
      diferencia(L, M, l, m);
      break;
    case 4:
      system("clear");
      cout << "CONCATENACION" << endl;
      cout << "LM = ";
      concatenacion(L, M, l, m);
      break;
    case 5:
      system("clear");
      cout << "INVERSO" << endl;
      cout << "L = ";
      inverso(L, l);
      cout << "M = ";
      inverso(M, m);
      cout << endl;
      break;
    case 6:
      break;
    default:
      system("clear");
      // En caso de que no se haya introducido una opcion valida se imprime el mensaje 
      cout << "Opcion invalida" << endl;
      break;
    }
  } while (op != 6);
  return 0;
}
BIBLIOGRAFÍA
· Kelley, D. (1995). Teoría de autómatas y lenguajes formales. PRENTICE HALL.