RESUMEN

DE
SISTEMAS OPERATIVOS
PRACTICO
 Linux
Es un sistema operativo basado en Unix desarrollado inicialmente por Linus Torvalds en 1991 y de
libre distribución (se encuentra bajo la licencia GPL)
Posee gran portabilidad hacia muchas plataformas, y el mismo sistema se utiliza junto a un
empaquetado de software a la que se denomina distribución Linux.
Linux es flexible y estable, ampliamente usado en redes, navegación de internet y programación.
GPL
Una licencia de derechos de autor de amplio uso que consiste en garantizar a los usuarios el poder
estudiar, modificar, usar y compartir el software.
El Proyecto GNU
EL proyecto GNU inició en 1983 por Richard Stallman (rms), y tiene como objetivo el desarrollo de
un sistema operativo completo similar a Unix y compuesto enteramente de software libre
Software Libre
Software que una vez adquirido se obtiene la libertad de ejecutarlo, copiar el programa para
reproducirlo, cambiar el codigo fuente como se desee, y distribuir versiones mejoradas con el fin de
aportar a la comunidad del sistema.
El Comienzo de Linux
Unix era ampliamente utilizado en el mundo de la informática y fué desarrollado alrededor de los
70’, con el inconveniente para programadores y desarrolladores de que era inaccesible. Linus
Torvalds, estudiante de la universidad finlandesa de Helsinki buscó, en 1991, realizar un reemplazo
para Minix, un clon de Unix creado por Andrew Tannebaum.
El núcleo fué escrito inicialmente en Assembler y C, y luego de un par de versiones Linus logró
obtener un software estable que lanzó bajo la licencia GPL, completando un sistema GNU
completo, denominado “Sistema Operativo GNU/Linux”. El mismo fué liberado en internet lo que
permitió que muchos programadores lo obtuvieran y realizaran sus propias sugerencias y
modificaciones.
Unix
Unix es un Sistema Operativo desarrollado en los laboratorios Bell durante 1970, inspirado en los
sistemas CTSS y Multics. Con el pasar de la década y el lanzamiento de nuevas y mejoradas
versiones la popularidad de Unix fue creciendo, otorgando licencias para producción y educación.
Así nacieron sistemas basados en Unix, como BSD, Solaris, Sistem V, etc.
Fue el primero en implementar código escrito en lenguaje de alto nivel para el desarrollo de un
sistema operativo (partes escritas en lenguaje C).
Característias de Linux
1. Multitarea
2. Multiusuario
3. Diseño Modular del Kernel
4. Soporte de Consolas Virtuales
5. Opera sobre todos los sistemas de archivos estandar.
6. Muchas capacidades para redes y comunicaciones.
7. Soporte completo para distintos tipos de hardware.
8. Poderoso entorno gráfico.
9. Distribución G.N.U/GLP
10. Tiene la capacidad de “shared libraries” al cargar librerias en memoria y permitir su uso a
cualquier proceso que los necesite, lo que hace a los binarios más pequeños.
11. Administración de Memoria.
12. La licencia GNU permite el desarrollo de aplicaciones para prácticamente todas las
necesidades.
 13. Es un sistema operativo pensado por y para los programadores, por lo que cuenta con una
gran cantidad de herramientas de desarrollo integradas.
14. El kernel de Linux, con cada actualización ha ido incluyendo soporte a variedad de técnicas
de seguridad, como firewalls y control de acceso.
15. Linux es capaz de convivir dentro de un disco con otros sistemas operativos mediante el
soporte de gestor de arranque para multiboot.
Kernel
Es la porción del sistema que se encarga de la interfaz con el hardware. En la arquitectura
micronúcleo, muchas de las funcionalidades del sistema se encuentran en forma de módulos
(programas que ofrecen servicios específicos del SO), mientras que en el kernel se mantienen
únicamente los servicios más esenciales. Si un programa necesita de un servicio, el mismo o
mediante una biblioteca realizará una llamada al sistema que lo comunicará con dicho servicio
mediante el traspaso de mensaje

lsmod
Comando que muestra el estado de los módulos del kernel que están cargados

Módulos
los módulos son programas que aportan funcionalidades de todo tipo al sistema, con la
característica de no encontrarse en el núcleo, sino que son cargados en memoria principal y luego
ejecutados cuando se requeren, dando extensibilidad, flexibilidad, portabilidad, y demás
características de una arquitectura microkernel. También pueden encontrarse dentro de la lista de los
procesos actuales.

uname
Comando que muestra información resumida del sistema
Opciones:
• -s nombre del kernel
• -r revisión del kernel
• -n nombre por el cual se identifica el sistema de red.
• -m tipo de arquitectura del sistema
• -v version del kernel.
• -p información sobre el procesador.
• -i plataforma de hardware (arquitectura de procesador)
• -o nombre del sistema operativo.
• -a muestra toda la información en el siguiente formato: Nombre del Kernel – hostname del
nodo de red – revisión del kernel – versión del kernel – nombre de la máquina – tipo de
procesador – plataforma de hardware.

Versiones del Kernel

Existen dos versiones del kernel más comunes: versión de producción y de desarrollo.
Versión de Producción: es la versión más estable que hay, como resultados de otras versiones
experimentales que le antecedieron
Versión de Desarrollo: Esta versión es experimental y es la que utilizan los desarrolladores para
programar, comprobar y verificar nuevas características, correcciones, etc. Estos núcleos suelen ser
inestables.

Números de una Versión del Kernel

Se representan como VV.XX.YY.ZZ

• VV indica la serie principal del kernel. El número cambia cuando el kernel ha sufrido un
cambio muy importante.
• XX indica el número de revisión del kernel.
• YY indica nuevas revisiones, donde se incorporaron características nuevas y drivers.
• ZZ indica la realización de parches de seguridad y corrección de errores.

El mismo puede estar acompañado de letras especiales, que indican alguna particularidad o
nombre de desarrollador abreviado.

Distribución
Una distribución es un conjunto de utilerías o herramientas y programas que facilitan el trabajo con
el sistema.
Algunas son.

• Debian.
• Slackware.
• Ubuntu.
• Mandriva.
• Conectiva.
• Caldera.
• Ututo.
• Goobuntu.
Paquetes de Software
Las distribuciones están divididas en paquetes, cada una contiene un programa o servicio
específico, es generalmente distribuida en su versión compilada y la instalación y desinstalación de
dichos paquetes son controlados mediante un sistema de gestión de paquetes.
Algunos de los sistemas de paquetes son:
• Paquetes Debian de extensión .deb e introducidos por la distribución Debian.
• Paquetes RPM (Red Hat Package Manager), formato de la Linux Standard Base.
• Paquetes TAR.GZ o TGZ, usado por Slackware, que empaqueta el software usando tar o
gzip.

lsb_release
Muestra información de la distribución GNU/Linux del Equipo
-a, –all Muestra toda la información
-i, -id Muestra el nombre de la distribución GNU/Linux
-d, –description Muestra la descripción de la distribución
-r, -release Muestra la versión de la distribución
-c, -codename Muestra el código de la distribución
-s, -short Muestra la información solicitada en formato corto, sin el título inicial.
-h, -help Muestra la ayuda y finaliza
-v, -version Muestra la versión de la especificación LSB de la que es compatible y finaliza

/etc/os-release Archivo donde se almacena la información completa de la distribución del

sistema.

Shell
programas encargados de interpretar lineas de comandos para realizar las acciones
correspondientes.. Permiten además construir programas a través de comandos, llamados
shellscripts, con las posibilidad de automatizar diversas tareas.

Shells más conocidos

Ash A shell
Ksh Korn shell
Bsh Bourne shell
Bash Bourne Again shell
Csh C shell
Tsh Extensión de C shell

Funciones destacadas de bash:

• Autocompletado durante la escritura.
• Historial de Comandos
• Estructuras de control (if, for, while, select y case)
• Definición de funciones y alias: las funciones permiten la definición de la subrutinas, y los
alias asocian nombre a comandos con ciertas opciones y argumentos de forma más
nemotécnica y abreviada.
Comandos
Los comandos son cualquier archivo ejecutable o interpretado (shellscript) por el shell. Los mismos
podran ser ejecutados desde una terminal de texto.

Formato de los Comandos

Comando [opciones] argumento1 argumento2

Interfaces de Usuario
EN linux existen dos vías fundamentales para interactura con el sistema una vez arrancado el
mismo: La poderosa interfaz por linea de comandos (CLI), conocida como Consola de Texto, y la
interfaz gráfica de usuario (GUI), un programa lanzado desde la linea de comandos tras arrancar el
sistema.

Interfaz Gráfica de Usuarios

La GUI en linux se implementa a través del estandar de sistema de ventanas “X Window”, entorno
operativo gráfico que permite dar soporte a aplciaciones en red y muestra información gráfica
independiente del sistema. La arquitectura de un sistema X Windows es de protocolo Cliente-
Servidor, es decir, el servidor gráfico (llamado X Server) se encarga de renderizar y mostrar en
pantalla el contenido que le es pasado por el gestor de ventanas y el entorno de escritorio.
Se habla también de un “entorno de escritorio” o Desktop Environment (DE), al conjunto de
software dentro de la gestión X Window encargada de las funciones y acciones del escritorio
gráfico, como barra de herramientas, íconos, carpetas, fondos de pantallas y widgets. Algunas DE
famosas son GNOME, KDE, CDE, Xfce o LXDE.
Por último, se hace referencia con “Gestor de Ventanas” o Windows Manager, al programa
encargado de todas las acciones que corresponden a las ventanas, como cerrar, maximizar, mover,
escalar, arrastrar y mantener un listado de las ventanas abiertas. Suele integrar también decorador de
ventanas, panel, visor de escritorios virtuales, íconos y tapiz. Entre los gestores más conocidos se
encuentran AfterStep, Kwin, Metacity, FVWM, AmiWM, IceWM, OpenBox y otros.
Interfaz de Linea de Comandos
Las consolas de textos consisten en que, a partir de una entrada estandar (el teclado) y una salida
estandar (el monitor), se simulen varias terminales donde el mismo usuario, o distintos de ellos,
puedan conectarse indistintamente al sistema operativo.

Concepto de Arranque
El arranque del sistema o “bootstrapping” es el proceso en donde se inicia el sistema partiendo
desde encender el ordenador hasta una estado operativo para el usuario.

El Bootstrapping comienza al enceder la computadora donde el procesador leerá instrucciones de la

memoria BIOS ROM, y su configuración de una memoria RAM alimentada con una batería.
Seguido ejecutará la rutina POST (Power Of Self Test), que verifica el estado de los dispositivos del
sistema, y por último se carga el MBR (Master Boot Record) en disco, primer sector de memoria
que contiene información sobre las particiones del sistema y el programa gestor de arraque multi-
boot, como GRUB o LILO.

El gestor correspondiente carga en memoria la imagen comprimida del Kernel de Linux, se

inicializa el gestor de sistema de archivos del Sistema Operativo montando el directorio raiz “/”, la
memoria Swap, se inicializan las interfaces elementales de la placa madre y, por último, llama al
proceso “init”.

El proceso “init” es el proceso a nivel de núcleo encargado de llevar al sistema a un estado operable
por usuario. “init” es comunmente usado en sistemas de base Unix SystemV, pero actualmente fué
reemplazado por la mayoria de distribuciones por el proceso “systemd” que ofrece más
funcionalidades.

“init” tiene PID 1 (es el primer proceso planificado), es el padre del resto de procesos y no puede
ser interrumpido.

Archivos relevantes durante el proceso de bootstrapping Linux basados en SystemV Init

/boot/grub/ Directorio donde se encuentra la imagen del
gestor de arranque GRUB del sistema.
/boot/vmlinuz-version Directorio donde se encuentra la imagen del
kernel de Linux, indicando su versión actual.
/etc/inittab Archivo desde donde “init” lee la configuración
sobre los procesos a ejecutar.
/etc/rc Procesos que ejecutan comandos de
inicialización como montar el sistema de
archivos, inicializar el swap, configurar la red y
arrancar los demonios
/etc/getty Proceso ejecutado en cada terminal para que el
usuario pueda conectarse al sistema, llamando
primero al proceso “login” para identificarlo.

Niveles de Ejecución
0 Halt. Apaga el sistema
1 Modo monousuario (modo de rescate)
2-5 Modo Multiusuario
6 Reboot o reinicio del sistema
S Se utiliza para el mantenimiento del sistema en
monousuario

Los runlevels se organizan bajo sus correspondientes directorios en /etc/rcN.d cambiando “N” por
el número correspondiente. Dentro de estos se encuentran un conjunto de scripts que controlan los
servicios a ejecutar. Tienen un nombre en formato [K | S] nn [string], donde “K” y “S” indican si el
proceso se detiene (Kill) o se inicia (Start); nn representa el número de prioridad y “string” es el
nombre del proceso. Todos los archivos son enlaces simbólicos al directorio /etc/init.d

runlevel
Comando que permite conocer los niveles de ejecución realizados. De haber iniciado el sistema
aparecerá un “N” primero seguido del runlevel actual.

init
Comando que permite iniciar el sistema en un runlevel determinado o cambiar el runlevel actual
del sistema.

systemd
software para la administración del sistema y de los servicios de Linux, padre de todos los procesos.
Mejora el framework para expresar dependencias, permite el procesamiento en concurrencia
durante el arranque del sistema. Posee los demonios de init junto con journald, longind, networkd, y
otros componentes de bajo nivel. Realiza muchos otros servicios.

Shutdown [opciones] [tiempo] [mensaje de aviso]

Apaga o reinicia el sistema
-h apaga la computadora.
-r reinicia la computadora.
+n minutos
hh:mm hora y minutos.

Login [opciones] [username]

Realiza una nueva autenticación con el usuario y establece una nueva sesión con el sistema.
-h nombre del host remoto para este inicio
-p preservar el entorno
-r realizar un servicio de inicio de sesión automático para rlogin

/etc/passwd Archivo que contiene información acerca de los

usuarios del sistema.
/etc/shadow Archivo que almacena información sobre la
clave de los usuarios.
/etc/motd Archivo que contiene el mensaje a mostrar luego
del inicio de sesión exitoso con login.
/etc/issue Contiene el mensaje a mostrar en terminal antes
de ejecutar la solicitud de usuario de login. El
contenido a mostrar depende de los caracteres
precedidos de una barra invertida:

• \d : fecha actual.
• \m : identificador de arquitetura de la
máquina.
• \o : nombre del dominio de la máquina.
• \s : nombre del sistema operativo.
• \r : versión del kernel
• \t : hora actual.
/var/run/utmp Lista de sesiones abiertas actualmente
/var/log/wtmp Lista de inicio de sesion anteriores
/etc/nologin Usuarios no-root que no pueden ingresar
/etc/tty Lista de tipos de terminales
var/log/btmp Lista de inicios de sesion fallidos

Who
Muestra información sobre las sesiones actualmente abiertas
-b tiempo transcurrido desde el inicio de sesion
-q conteo de usuarios logueados en el sistema
-r runlevel actual del sistema
-u usuarios logueados
-a listado detallado de sesiones con informacion extendida
-H cabecera de las columnas

Last
Listado de las ultimas sesiones abiertas

Lastb
Lista los inicios de sesion fallidos del sistema

logout
Realiza el cierre de la sesión actual en el sistema

Sistema de Archivos
EL sistema de archivos es la parte del sistema operativo que se encarga de la gestión de los datos
almacenados en los dispositivos de memoria, manejados como archivos y directorios, como por
ejeemplo la ubicación de archivos almacenados y espacios libres, la asignación, modificación y
liberación de ese espacio.
Los discos rígidos se encargan de almacenar los datos en sectores, mientras que el software del
sistema de archivos se encarga de manejar dichos datos en forma de “archivos”. También puede
utilizarse para manejar datos de forma dinámica y que no es necesario que pase por el
almacenamiento secundario, como los datos de red o procesos.
En Linux el Sistema de Archivos presentado al usuario es el resultado de los sistemas de archivos
montados de dispositivos de almacenamiento (disco, medios extraibles, etc). Los datos
correspondientes a los archivos se guardan dentro de bloques llamados i-nodos. El sistema que
adopta Linux actualmente es ext4 (cuarto sistema de archivos extendido).

Entre los sistemas más conocidos encontramos:

Ext4
Una mejora del anterior sistema ext3, incluyendo compatibilidad con versiones anteriores, soporte a
archivos y espacio de almacenamiento mucho mayores, técnicas de persistencia de espacio para
almacenamiento contiguo (reducción de fragmentación), además de mejoras en el rendimiento.

Btrfs
Sistema desarrollado por Oracle Corporation, de copia en escritura (copy-on-write), destacando la
tolerancia a fallos, reparación y administración sencilla.

Zfs
Sistema desarrollado por Sun MicroSystems para el sistema operativo Solaris. Entre sus
características se destacan la integridad de los datos mediante el modelo transaccional,
autoreparación con configuración RAID-Z, uso de instantáneas del sistema de archivos, bandas de
tamaño variable y manejo del estandar POSIX.

Directorios en Sistemas Linux

Se basa en el estandar FHS (Filesystem Hierarchy Standard) de Debian.

/ The root directory. Where everything begins

/bin Contains binaries (programs) that must be present for the system to boot and run.
/boot Contains the Linux kernel, initial RAM disk image (for drivers needed at boot time),
and the boot loader. Interesting files:
● /boot/grub/grub.conf or menu.lst, which are used to configure the boot loader.
● /boot/vmlinuz (or something similar), the Linux kernel
/dev This is a special directory which contains device nodes. “Everything is a file” also
applies to devices. Here is where the kernel maintains a list of all the devices it
understands.
/etc The /etc directory contains all of the system-wide configuration files. It also contains a
collection of shell scripts which start each of the system services at boot time.
Everything in this directory should be readable text. Interesting files: While everything
in /etc is interesting, here are some all-time favorites:
● /etc/crontab, a file that defines when automated jobs will run.
● /etc/fstab, a table of storage devices and their associated mount points.
● /etc/passwd, a list of the user accounts.
/home In normal configurations, each user is given a directory in /home. Ordinary users can
only write files in their home directories. This limitation protects the system from errant
user activity.
/lib Contains shared library files used by the core system programs. These are similar to
DLLs in Windows.
/ Each formatted partition or device using a Linux file system, such as ext3, will have this
lost+fou directory. It is used in the case of a partial recovery from a file system corruption event.
nd Unless something really bad has happened to your system, this directory will remain
 empty.
/media On modern Linux systems the /media directory will contain the mount points for
removable media such as USB drives, CD-ROMs, etc. that are mounted automatically at
nsertion.
/mnt On older Linux systems, the /mnt directory contains mount points for removable
devices that have been mounted manually.
/opt The /opt directory is used to install “optional” software. This is mainly used to hold
commercial software products that may be installed on your system.
/proc The /proc directory is special. It's not a real file system in the sense of files stored on
your hard drive. Rather, it is a virtual file system maintained by the Linux kernel. The
“files” it contains are peepholes into the kernel itself. The files are readable and will
give you a picture of how the kernel sees your computer.
/root This is the home directory for the superuser account
/sbin This directory contains “system” binaries. These are programs that perform vital system
tasks that are generally reserved for the superuser.
/tmp The /tmp directory is intended for storage of temporary, transient files created by
various programs. Some configurations cause this directory to be emptied each time the
system is rebooted.
/usr The /usr directory tree is likely the largest one on a Linux system. It contains all the
programs and support files used by regular users.
/var With the exception of /tmp and /home, the directories we have looked at so far remain
relatively static, that is, their contents don't change. The /var directory tree is where data
that is likely to change is stored. Various databases, spool files, user mail, etc. are
located here.
/usr/ Contiene las cabeceras de las librerias para los lenguajes de programacion
include
/usr/lib Contiene las bibliotecas compartidas por los binarios almacenados
/usr/local Almacena el software instalado localmente por el administrador del sistema

Sectores
Unidades de bytes sobre las cuales trabaja el disco. Suele rondar los 512 bytes.
bloque
El bloque o cluster es una agrupacion de sectores del disco, generalmente de 4K, que tienen el fin
principal de formar la unidad de referencia de operaciones de entrada/salida (leer o escribir bloques
de 4k como mínimo).

Ls
Lista los archivos y directorios de un determinado directorio
-a muestra todos los archivos, incluso ocultos
-l formato extendido de la informacion de archivos
-h muestra el tamaño de los archivos (human-readable)
-d muestra solo directorios
-1 listado de una sola columna
-1 muestra el número de i nodo de cada archivo
-R presenta los datos de forma recursiva
--color muestra los archivos con diferentes colores
 pwd
Nos permite conocer el directorio activo de trabajo

cd
Nos permite cambiar el directorio de trabajo

Unidad 4 - Manejo de Archivos

Tipos de Archivos en Linux:

- Común – Ordinario.
d Directorio.
b Especial de Bloque.
c Especial de Caracter.
p Archivo de Tuberia para la comunicación de procesos.
s Archivo de Socket que son abiertos y referenciados por los procesos con el fin de
comunicarse.

i-nodo
Cada archivo posee un bloque de i – nodo, que contiene su forma de identificación, los atributos y
los punteros a donde se localiza. Al crearse un archivo se agrega una entrada al directorio que lo
contiene con su nombre y número de i – nodo.

Los atributos que posee son :

• UID (User Identifier),
• GID (Group Identifier),
• Tipo de Archivo,
• Modo de Acceso
• Marcas de Tiempo
• Número de Enlaces
• Longitud
• Punteros a Bloques
Descriptores de Archivos
Cada proceso tiene asociado en la zona del kernel una tabla de entradas de los archivos de los cuales
puede leer (primitiva read) o escribir (enviar datos mediante la primitiva write), los cuales son
asociados a un número entero en particular, denominados descriptor del archivo. En sistemas GNU/
Linux basado en Unix existen tres descriptores estándares que son abiertos dentro de las terminales,
stdin (descrioptor 0 para entrada de datos, usualmente el teclado) , stdout (descriptor 1, para la
salida, usualmente la pantalla del tty (terminal) o pts (pseudoterminal de lado escladvo)) y stderr
(2, indica la salida para mensajes de errores, como la misma pantalla o los archivos logs),
TTY, PTM y PTS
Históricamente se le ha asignado a las terminales de los sistemas GNU/Linux como “tty”,
abreviatura de “teletipo”, máquinas donde antes se mostraban las mismas. Dentro de los entornos
gráficos estas mismas terminales deben emularse para mostrarse dentro del gestor de ventanas
(como el programa emulador xterm), las cuales se basan en la en el canal de comunicación dual de
dos lados (ends): el lado maestro (/dev/ptmx, conocido como ptm) y el lado esclavo (/dev/pts/x). El
objetivo de esta arquitectura es la de ejecutar los procesos de linea de comandos del lado de “pts”
como si se tratase de un terminal verdadero, comunicándose a su vez con “ptm” para obtener el
acceso al sistema y el flujo de datos, como las entradas por teclado. Abriendo el archivo
“/dev/ptmx” se crea un nuevo esclavo correspondido de un maestro. Los esclavos creados (termianl
emulada) se pueden encontrar en el directorio “/dev/pts/x”, comenzando desde el “0”.
Redireccionamiento de Entrada/Salida
los archivos stdin, stdout y stderr se encuentran en el directorio “/dev”, sin embargo, es posible
reasignar los archivos sobre el cual el programa ejecutado en shell lee o escribe, mediante los signos
“<” (redirección de archivo de entrada), “>” (redirección de archivo de salida sobreescribiendo
cualquier contenido), “>>” (redirección de archivo de salida a partir del EOF del mismo) y
“2>”(redirección de archivo de salida de errores).

touch
Crea un archivo de texto vacio

cat
Muestra, concatena o permite crear archivos.

mkdir
Crea un directorio o lista de directorios
-p permite crear los directorios padres de ser necesario.

rm
Borrar un archivo o lista de archivos.
-i pide al usuario que confirme la eliminacion del archivo.
-f borra el archivo sin tener en cuenta los permisos del archivo.
-r borrar de forma recursiva en directorios
-v explica que se esta haciendo

rmdir
Borra un directorio

more
Muestra un archivo de forma paginada
-n cantidad de lineas que muestra por página.

head
Muestra las n primeras lineas de un archivo
-n muestra las n primeras lineas
-c muestra los c primeros bytes del archivo
–bytes[ ]k muestra los primeros c kilobytes del archivo

tail
Muestra las últimas lineas del archivo.
-n ultimas n lineas
-c ultimos c bytes
-f muestra las lineas que se van adicionando

cp
Copia un archivo/lista de archivos en un directorio

mv
Mueve o renombra un archivo

Enlaces
Los enlaces dentro del sistema de archivos son las entradas en direcotorios diferentes hacia el
mismo archivos, con nombre distintos o iguales, pero con el mismo número de i nodo (único
identificador de archivo dentro de Linux). Existen los enlaces duros que apuntan a la misma
dirección de memoria donde el archivo se encuentra (por ende con el mismo numero de i nodo), lo
que dificulta el enlace entre distintos volúmenes físicos. Luego se encuentra el enlace simbólico,
que es un archivo diferente (diferente i nodo) que contiene la ruta hacia el nombre del archivo
original, con la desventaja de quedar inutilizable si la entrada de dicho archivo donde apunta cambia
de nombre o es removido.

ln
Crea un enlace entre archivos
-d permite al superusuario hacer enlaces duros a directorios
-s crea enlaces simbólicos.
-f borrar los archivos del destino que ya existen.

Respaldo de Archivos
Los backups o respaldos de archivos son copias de seguridad que nos aseguran mantener un grupo
de archivos y su contenido almacenados para prevenir su pérdida en caso de perder o modificar los
archivos originales.
Las técnicas de backups más conocidas son :
• Completas. (Respaldo de todo el contenido).
• Incremetales. (Respaldo del contenido modificado a partir del último respaldo incremental).
• Diferenciales (Respaldo del conteindo modificado a partir del último respaldo completo).

tar
Crea archivos de respaldo dentro de los sistemas Unix
-c acción de crear un archivo de respaldo
-v muestra los archivos a medidas que realiza operaciones
-f indica que el parámetro siguiente es el nombre del archivo a crear.
-p conserva los permisos de los archivos.
-z realiza la compresión de los archivos.
-d busca diferencias entre los archivos.
-r agrega los archivos al final de un archivo.
-t lista el contenido de los archivos del backup.
-x extrae los archivos del respaldo
X FILE exclude del relpado a los archivos listados en el archivo FILE
--exclude=“archivo” excluye un archio del respaldo.
-N crea un backup diferencial.
-g crea un backup incremental.

Crear respaldos incrementales

Se crea un archivo de meta-datos que lista los cambios realizados entre respaldos partiendo del full -
backup (el archivo meta – dato todavia no existe).
tar -cg “archivo.snar” -vvf backup.tar archivos
para crear el archivo incremental basta con cambiar el nombre “backup.tar” (que es el full backup)
por otro que represente el nuevo incremento, los cambios efectuados son registrados en
“archivo.snar”. Snar es la convención para este tipo de archivos.
Crear archivos diferenciales
El comando “tar” utiliza la opción “-N” (newer) para utilizar una fecha de referencia sobre la cual
solo respaldará los archivos que se crearon/modificaron después del mismo. Si se le pasa como
parámetro el nombre de un archivo, utilizará la fecha mtime de este como referencia.
tar -cN fullbackup.tar -vf backupDif.tar datos
Se obtiene un respaldo diferencial diferente en cada ejecución cambiando el nombre de
“backupDif.tar” por otro.
Agregar archivos nuevos al backup:
Basta con escribir tar -rvf respaldo.tar archivos.nuevos
Excluir archivos mediante un listado:
El listado se guarda dentro de de un archivo de texto que luego debe ser referenciado como
argumento de la opcion X. Por ejemplo tar – cX lista -vf respaldo.tar archivos
rsync: Herramientas de copias de eguridad rápida y versatil. Permite copias localmente, hacia o
desde un host mediante un shell remoto.

gzip
Comprime archivos, agrega el sufijo “.gz” por defecto
-c Esccribe la salida en la salida estandar, deja los archivos originales tal cual. Con varios archivos
de entrada, la salida consiste en una secuencia de miembros comprimidos independientemente.
-d Descomprime
-f Fuerza la compresión/descompresión.
-l Lista diferentes campos para los archivos siendo comprimidos.
--verbose muestra los campos correspondientes al métodos de compresión, bits y tiempos.
-r recorre la estructura de directorios recursivamente.
-# Regula la velocidad y calidad de compresión. (1 a 9, parte desde el archivo más grande en
menor tiempo, hasta el más pequeño pero con mayor tiempo).

zcat
Muestra el contenido de un archivo comprimido

gunzip
Comando que se utiliza para descomprimir archivos (comando gzip con la opción -d activa)

split [opciones] archivo nombre

Divide un archivo en subarchivos pequeños de misma longitud.
-a N cantidad de caracteres que tendrá el sufijo al crear los archivos.
-b SIZE generar los archivos de un tamaño SIZE (b (512), kB (1000), K (1024), etc), cortando
lineas de ser necesario.
-C SIZE mismo que b, sin cortar las lineas.
-d Indica que los sufijos son numéricos.
-l NUMBER decidimos cuantas lineas tiene cada archivo de salida.

Unir las particiones en un solo archivo

Para volver a obtener el archivo original, pueden unirse utilizando “cat” y redireccionando la salida
a un archivo, agregando “*” donde estarán los sufijos para pasar por cada uno de ellos: cat cortes*
> archivo

diff [opciones] archivo1 archivo2

Permite ver las diferencias entre dos archivos
-a trata a todos los archivos como de texto y los compara linea por linea.
-b ignora los espacios y las tabulaciones de linea.
-B No considera cambios consistentes en insertar y borrar lineas en blanco.
-r compara los archivos de directorios en forma recursiva.
-e genera un “edit script” (archivo editable).

cmp archivo1 archivo2 [salto1] [salto2]

Compara dos archivos byte por byte. Se utiliza para comparar todo tipo de archivos. Los saltos
indican el número de bytes a saltar en cada archivo antes de leer. Colocando un guion (-) en
archivo2 leerá desde la entrada estandar. La salida es 0 si son igual, 1 si son diferentes y 2 si hubo
algún fallo en la comparación.

Filtros
Familia de comandos (grep, sort, find, locate, wc, cut, sed, tr, uniq, tee, etc), que obtienen salidas
mediante el filtrado del contenido de archivos contenedores de caracteres.

grep [opciones] patron archivos

Busca en uno o más archivos un patrón y muestra las lineas que las contienen. Sus variantes son
egrep, pgrep, fgrep, rgrep
-n Muestra la linea y su número dentro del texto.
-v Busca las lineas que no contiene el patron.
-i Ignora la diferencia entre mayúsculas y minúsculas.
-c Muestra solo el número de lineas coincidentes.
-l Solo lista los archivos donde hubo coincidencias.
-L Solo lista archivos que no contienen el patron.
-r Búsqueda recursiva dentro de directorios.

Expresiones Regulares
^ Indica inicio de linea
$ Final de linea
\ Evita dar significado especial al siguiente carácter
[] Indica un conjunto o rango de caracteres.
[^] Negación del conjunto.
. Culaquier carácter.
* Puede existir (o no) un conjunto de caracteres de cualquier longitud.
 El carácter anterior puede existir entre x a z veces.
\{x,z\}
\{x\} El caracteres/expresion anterior debe existir exactamente x veces.
\{x,\} El caracter/expresion anterior puede existir x veces o mas.

egrep
Mismo de grep, utiliza la opción “e” (uso listado extendido de caracteres para las expresiones
regulares).

+ Una o más repeticiones del carácter precedentes.

? Cero o mñas repeticiones del carácter precedente.
| Cualquiera de dos o más caracteres.
() Trata el texto entre paréntesis como un grupo.

tr [opciones] conjunto1 conjunto2 < entrada

Reemplaza o elimina un conjunto de caracteres de la entrada estandar (stdin)
-c Complemento de la definicion dada por el usuario.
-d Borra los caracteres definidos en CONJUNTO1
-s Elimina la secuencia continua ,repetida o única, de caracteres de CONJUNTO1 y los reemplaza
por una sola repetición de CONJUNTO2.
-t Trunca la longitud del CONJUNTO1 según la de CONJUNTO2.

Algunos caracteres predefinidos para los conjuntos:

\f Salto de página.
\n Nueva linea.
[:lower:] Letras minúsculas.
[:upper:] Letras mayúsculas.

cut [opciones] archivo

Muestra segmentos o porciones de la linea de archivos o desde la entrada estandar stdin,
delimitando campos mediante caracteres.
-f Enumerar los campos a seleccionar.
-c Muestra los caracteres indicados en el o los rangos.
-b Muestra los bytes indicados en el o los rangos.
-d Denota el carácter delimitador de los campos.
-s Las lineas que no posean delimitador no serán mostradas.

Find path [opciones] argumentos [acciones]

Permite buscar archivos en el sistema de archivos. Una vez encontrados permite realizar una o más
acciones sobre las mismas de ser necesario. Las opciones hacen referencia al tipo de búsqueda, el
path desde donde se empieza a buscar.
-name {patron} archivos que coincidan con el patrón
-iname ignora dif entre mayúsculas y minúsculas.
-lname {patron} enlaces simbólicos.
-liname anterior sin dif. mayus/inús.
-type busca por tipo de archivo (F:regular, D:direc, B:bloque, C:caracter, L:enlace, p:conector)
-newer busca cont. Más reciente que un archivo.
-inum busca por i - nodo
-empty archivos vacíos.
-maxdepth n baja hasta n niveles en el árbol
-mindepth n busca a partir del n nivel del arbol
-group {nombre} busca por grupo
-perm {modo} archivos de los mismos permisos (octal o simbólico).
-links n busca por cantidad de enlaces.
-sizen[ckMG] busca por cantidad de tamaño.
-amin {n} archivos leidos hace n minutos
-atime {n} archivos leidos hace 24xn horas
-cmin {n} archivos de permisos cambiados hace n minutos
-mtime archivos modificados dentro de los n días.
-uid {n} archivo con propietario de uid especificado.
-user {usuario} archio con propietario de nombre especificado.

+n mayor a
-n menor a
n igual a

* Cualquier o ningun carácter

? Cualquier carácter sencillo
[cadena] Coincidencia con exactamente un carácter contenido en la cadena. Puede especificar
rangos
[^cadena] Cualquier carácter no contenido en la cadena

Los patrones suelen usarse entre comillas simples.

-delete Borra el archivo

-exec comando Ejecuta el comando pasando como parámetro el path del archivo encontrado {}
{} \;

sort [opciones] archivosAOrdenar

Ordena alfabéticamente las lineas de uno o más archivos que se indican como argumentos y
muestras las salidas ordenadas por la salida estandar.
-r invierte el orden normal.
-n clasifica según el valor numérico.
-nr orden numérico inverso.
-f no dif mayús/minus.
-u clasifica y elimina lineas idénticas.
-k n1,[n2] Especifica un campo comp clave de ordenación (comienza en n1 y acaba en n2).
-t indica el carácter usdao como separador de campos.
 wc [opciones] archivo
Permite contar lineas, palabras y caracteres de una entrada, sea la entrada estandar o un grupo de
arhivos, y entrega un informe de salida estandar.
-l cuenta solo las lineas.
-w cuenta solo las palabras.
-c cuenta solo los caracteres.

Seguridad

La seguridad informática consiste en la protección de los datos asegurando la confidencialidad,

integridad y disponibilidad. El control de acceso al sistema incluye las acciones de identificación y
autenticación.

Autenticación
Acción por la cual demostramos, mediante algún método fiable, la identidad de decimos tener. Es la
acción de login que realizamos para acceder al sistema.

passwd [opciones] usuario

Permite realizar el cambio de contraseña de un usuario

Autorización
Propiedades particulares ligadas a nuestra identidad que especifica el acceso y tipo de acceso que
tendremos a los recursos de un sistema informático, como archivos u opciones de ejecución de
programas. En Linux el sistema de permisos de archivos delimita la autorización de los usuarios
sobre los mismos, incluyendo el permiso de ejecución.

R Leer
W Escribir/modificar
X Ejecutar

El tipo de información sobre usuarios que guarda el archivo para manjar permisos son UGO:

U User
G User’s Group
O Others
A All the users

chmod [permisos] arhivos

Permite modificar los permisos rwx de los archivos indicados. Los mismos pueden modificarse
por tres formatos: absoluto (campo=permisos, etc), simbólico (campos+/-permiso) u octal o
numérico (XXXX, cada X representa el campo correspondiente de la combinación de los tres tipos
de permisos en forma de bits, pasados a valor octal, la primer X es usada para los permisos
especiales de suid, sgid y sticky).

Suid, Sgid y Sticky

Su uso permite otorgarle los permitos del propietario (suid), grupo (sgid), mientras que sticky indica
además que el archivo es muy utilizado, por lo que es conveniente que permanezca en memoria el
mayor tiempo posible.

Permisos sobre los Directorios

Para leer un archivo, es necesario tener el permiso de lectura del mismo y el permiso de ejecución
del directorio que lo contiene. Para modificar el listado de archivos dentro del directorio debemos
tener el permiso de escritura, y para listarle, el permiso de lectura.
Atributos de los Archivos

A La fecha de último acceso no se modifica.

a El archivo solo se puede abrir en modo adjuntar para escritura.
c El archivo es comprimido antes de almacenarlo en disco duro.
D Equivalente a la opción dirsync de mount. Guarda los datos de un directorio
automásticamente en disco en la escritura.
d Estable que el archivo no sea candidato a respaldo al usar la herramienta
dump(utilidad de respaldo).
e El archivo usa extensiones para la cartografía de los bloques en el almacenamiento. Es
incapaz de eliminar este atributo con chattr.
i Indica que el archivo será inmutable.
j (proviene de journal), si el sistema es montado con ciertas opciones, el archivo será
escrito en el registro por diario (journal).
s Los bloques utilizados en disco son escritos con ceros, de modo que no se puedan
recuperar por medio alguno, seguro para la eliminación de datos.
S Sus datos son escritos de forma síncrona en disco. Similar a la opción sync de mount.
u Guarda los datos de un archivo eliminado con el fin de poder recuperarlos de ser
necesarios.

Los atributos útiles en el área de la seguridad son a,i,s y S.

lsattr archivo
Lista los atruibutos del archivo especificado.

chattr [+-=] [atributos] archivo

Permite cambiar los permisos del archivo especificado.

Administración de Procesos
Procesos
Estructura de datos que representa a la ejecución de un programa, incluyendo los datos, código y
bloques de control que utiliza el sistema para la gestión de los mismos.

S (SLEEP) Suspendido con espera interrumpible (espera que se cumpla un evento).

D (SLEEP) Suspendido con espera no interrumpible.
T Detenido con alguna señal de detención.
(STOPPED)
R En Ejecución.
(RUNNING)
W Paginado
Z (ZOMBIE) Finalizado, se mantiene los datos en memoria para su uso por el sistema y otros
procesos.
X (DEAD) Muerto (no se visualiza).

En linux existen los procesos interactivos (iniciados y controlados por shell, estango en bg o fg), en
cola (Esperar a ejecutarse secuencialmente) y demonios (se lanzan al iniciar el sistema y se
ejecutan en bg).

pstree
Muestra el arbol jerárquico de procesos (padres e hijos).
-p Muestra los PIDs.
-a Muestra los argumentos de la linea de comandos.
-h Resalta el procesos actual y los que se encuentren encima de el.

ps
Muestra información sobre los procesos activos del sistema.
-e info sobre todos los procesos
-l información más completa de los procesos.
-f visualizar parámetros con los que se levantó un proceso.
-x procesos que no estan controlados por ningun terminal.
-uusuario procesos del usuario indicado.
-a todos los procesos asociados a un terminal.
-r muestra procesos en estado de ejecucion.
-H Muestra la jerarquia de procesos.
-txx Muestra los procesos asociados a la terminal txx
-aux Muestra info adicional de todos los procesos del sistema.

top
Muestra información en tiempo real referida a los procesos.

Creación de un procesos
Si el comando analizado por el shell es de si mismo, utiliza llamadas al sistema para la interacción
directa con el hardware (mediante le kernel). Si el comando corresponde a un archivo ejecutable, se
crea un proceso mediante una llamada fork() y lo ejecuta mediante exec(). Todos los procesos
lanzados desde un shell son hijos del propio shell, quien dio la llamada de creación de proeso.

Subdirectorio proc
El subdirectorio “proc” es un sistema de archivos virtuales, es decir que no son archivos que
existen en un dispositivo físico, sino que son creados por el sistema para registro y control de
procesos, memoria y configuraciones del kernel, entre otro. Cada procesos posee un subdirectorio
debajo de proc nombrado con su número de PID y contiene información sobre el mismo, existen
además otros archivos de información y configuración general.
Listado de archivos útiles dentro del subdirectorio “/proc”:
 • PID/status : info del estado del proceso.
• Interrupts
• meminfo
• mounts
• partitions
• sys/ : informacion de configuración del propio kernel. Algunos archivos pueden modificarse.
• filesystems

Piping o Comunicación de Procesos

Los procesos puede enviar su salida como entrada de otro proceso utilizando “|” entre ellas y
omitiendo escribir argumentos de entrada en el comando que recibe. El kernel permite esta
comunicación asignándole una zona de memoria para lecto/escritura, reemplazando los stdout, stdin
y stderr.

Procesos en Segundo Plano (Background)

Los procesos lanzados en sesión pueden pasarse aun segundo plano (permitir desligar la espera del
uso del shell hasta terminal la ejecución) mediante el uso de &(ampersan) al final del comando.

jobs
Permite conocer los procesos ejecutándose en segundo plano, y procesos suspendidos.

nohup
Permite ejecutar un comando subordinado (lanzado desde una terminal, por ejemplo) para que se
ejecute hasta finalizar sin ser interrumpido.

Nohup guarda la salida en un archivo nohup.out en el directorio actual o de conexión según se

pueda, a menos que se especifique otro archivo. Nohup no evita que el procesos se lance en primer
plano (debe usarse &).
Detención y Relanzamiento
Las tareas pueden detenerse mediante el comando ctrl+z.

fg
Lanza una tarea detenida en primer plano

bg
Lanza una tarea detenida en segundo plano

kill -señal (número o palabra) proceso (PIDs o nombre)

Comando que envia una señal a un proceso, sin opciones envia una señal de matarlo.
-l lista las señales posibles.

Se utiliza el signo % para referirse a un proceso por su número de tarea (%numero) en vez de PID.
Para los procesos se hará uso de ctrl+c o ctrl+z para detener la ejecución, para luego usar el
comando kill al estar detenido o si se trata de un proceso subordinado (en background).

Planificación de Procesos
El sistema de planificación de procesos de Linux se basa en prioridades de dos tipos: normal y real-
time. Los procesos comunes se asocia un quantum para ejecutarse, en cambio el kernel ocupa el
procesador hasta terminar la ejecución de la tarea llamada.
La prioridad se mide en números, mientras menor sea mayor es la prioridad. Ocupar el CPU
depende de los valores de prioridad base + uso total de la CPU + NI.

nice
Permite asignar una prioridad a un proceso al lanzarlo.

Para poder disminuir (– opcion) el número es necesario ser superusuario, para aumentar (- opcion),
lo puede hacer cualquiera.

renice
Pemite relanzar una tarea suspendida con una prioridad diferente

Se usa ± para apuntar a un número entre -20 y 19.

at [time] [Enter] comandos

Permite ejecutar trabajos para una única ejecución posterior.

El formato usado es at time donde time puede especificarse de diferentes formas:

HH:MM Horas y minutos

midnight Medianoche
MMDDAA, Mes, dia, año,
MM/DD/AA,
DD.MM.AA
Now Hora actual
Tomorrow El dia siguiente
Noon Mediodia
+ A la hora fijada se le suma un agregado de tiempo.
(minutes,hour
s,days,weeks,
etc).

La salida de los comandos serán enviados como correo al usuario a menos que se redireccionen.

batch
Se usa para programar que un proceso se ejecute recién cuando la carga del sistema esté por debajo
de 0.8. (Mismo que at)

atq
Muestra los trabajos a finalizar por el comando at.

Demonio Cron:
es un demonio que se se planifica al iniciar el sistema y se despierta cada minuto a chequear los
comandos que deben ejecutarse para at y crontab, manteniéndose durmiendo en caso contrario.

crontab [opciones] file

Se utiliza para programar tareas, programar la ejecución de otros comandos.

Para programar tareas periódicas es necesario crear un archivo de caracteres que contengan los
comandos a realizar con el siguiente formato.

Minutos horas diaDelMes MesDelAño DiasDeLaSemana [COMANDO]

Por defecto los archivos de crontab se almacenan en el directorio var/spool/cron/crontabs

uptime
Muestra un infome sobre el desempeño del sistema.

Administracion de Archivos

/proc/meminfo Brinda informacion sobre el sistema

free [opciones]
Muestra la memoria fisica y de intercambio, así como los buffers y memoria compartida
-b bytes
-k kilobytes
-m megabytes
-g gigabytes
-h human readable
-s cantidad de segundos entre informes
-t valores totales en cada columna
-c cantidad de informes a mostrar entre intervalos

vmstat [intervalo (número)]

Muestra informes estadísticos sobre el uso de la memoria virtual. Da información sobre los
procesos, operaciones de entrada/salida, interrupciones y manejo de la cpu. Muestra la informacion
de los archivos /proc/meminfo, /proc/*/stat y /proc/stat.
Intervalo - tiempo entre refrescos (segs)
número - cantidad de informes a emitir
-a cantidad de memoria activa e inactiva
-s tabla estadísticas con varios contadores de eventos
-d informe estadísticos de discos
-D resumen estadístico sobre la actividad del disco
-p Dispositivo estadísticas detalladas sobre la partición.
-S carácter muestra estadísticas sobre el carácter indicado (representación de unidad de datos
bytes).

Dmesg
Muestra y manipula el almacenamiento intermedio del anillo del kernel.
-c limpia lo almacenado en el anillo, después de mostrarlo.

/proc/swaps muestra las áreas de intercambio activas del sistema linux

/etc/fstab almacena información sobre como serán montadas e integradas las particiones de disco y
sistemas de archivos. Desde ahí se agrega una entrada que contenga la especificación de una unidad
swap para asegurarse su uso en el próximo inicio de sesión.

dd [opciones] if=[fichero] of=[salida] bs=tamaño count=bloques

Convierte y copia un archivo.
If archivo de entrada donde se leerán los bloques, por defecto es la entrada estandar.
Of indica en que archivo se pondrán los bloques seleccionados, por defecto es la salida estandar.
Bs indica el tamaño de los bloques que serán leidos y escritos en el archivo (en bytes), por defecto
son de 512
count cantidad de bloques que serán leidos y escritos
conv=CONVERSION convierte un archivo según se halla especificado en los argumentos (ascii,
ebcdic, lcase, ucase)

mkswap [opciones] dispositivo [tamaño]

Prepara un dispositivo o un archivo como área de intercambio. El del sistema de archivos se puede
especificar en bloques.
-c comprueba que no haya bloques defectuosos primero.
-p SIZE especifica el tamaño el tamaño de páginas en bytes.

sync
Guarda el contenido de la caché de disco dentro del disco físico, forzando la escritora de los
cambios realizados.

swapon/off
Habilita o deshabilita dispositivos o archivos para el paginado de intercambio.
-p especifica la prioridad del archivo
-s muestra un resumen de uso de swap por dispositivo.

El Proceso de Entrada/Salida

fdisk [opciones] [dispositivo]

Permite crear, manipular y eliminar particiones de los dispositivos de almacenamiento.

Mkfs [opciones] [dispositivo]

Se utiliza para dar formato a los dispositivos de almacenamiento de bloque con un determinado
sistema de archivos.
-v Produce una salida detallada
-t [fstype] especifica el tipo de sistema de archivo que se construirá
-c comprueba los bloques malos en el dispositivo antes de construir el sistema de archivos.
-h Pantalla de ayuda.
 mount [opciones] dispositivos dir
Monta un dispositivo o muestra una lista de ellos.
Mount lee el contenido del archivo etc/mtab que es el mismo que el archivo /proc/mounts. Con la
opción a monta los dispositivos especificados en /etc/fstab

umount
Desmonta un dispositivo o elimina dispositivos instalados.

Los dispositivos escritos en /dev/fstab son los que se montan al inicio del sistema y /proc/devices
enumera los tipos de dispositivos de carácter y bloque a los que se les da soporte con controladores.

df [opciones]
Se usa para ver los sistemas de archivos montados y el número de bloques de espacio de disco
libres que tiene cada uno.
. muestra el espacio que está utilizando el sistema actual solamente
-i informacion sobre los i nodos ocupados y libres en cada particion
-a nos muestran todos los sistemas de archivos.

du [opciones] recurso
Se usa para estimar el uso del disco, de una archivo, de un directorio o de archivos en un sistema
de archivos.
-b mostrar en bytes
-s mostrar solamente tamaño total de argumentos
-h imprime información legible

Cuota de Disco
Para implementar la cuota se debe agregar las palabras usrquota y grpquota dentro del archivo /etc/
fstab.

quotaon/off
Se usa para activar y desactivar cuotas de disco definidas para los usuarios o grupos de usuarios.
-g abrir limite de espacio de disco de grupo
-u abrir limite de espacio de disco de usuario
-v muestra la instrucción de ejecución de comandos

edquota
Sirve para controlar y monitorear la cuota de disco de cada usuario del sistema.

quota
Nos permite conocer el espacio utilizado por el usuario o grupo.

Impresión en Linux
El encargado de gestionar la cola de impresiones es el demonio lpd, que eventualmente se
dfespierta a verificar que haya nuevos archivos enviados a impresión y los para a la correspondiente
impresora.

La informacion de las impresoras puede encontrarse en el archivo /etc/printcap, cada impresora

deberia tener su propio spool (cola de impresion) bajo un directorio con su nombre en el directorio /
var/spool/lpd
lpr opciones nombre-archivo
Comando que se utiliza para enviar un archivo a un dispositivo de impresión
Pprinter impresora a utilizar
h suprime la impresión de la página banner
# num especifica el número de copias a imprimir
s Crea un enlace simbólico en lugar de coopiar el archivo compoleto al directorio de spooling

lprm
Elimina un trabajo o archivo de la colade impresión
Pprinter cola asociada a dicha impresora
- borra todos los trabajos de un usuario
especifica el nombre del usuario dueño del trabajo a eliminar
job # hace referencia al número de trabajo a eliminar

lpq
Nos permite conocer los trabajos que están en cola de impresión

lpc
Permite activar o desactivar impresoras

lpstat
Muestra el estado de las impresoras conectadas al sistema

cups
Programa de comandos de shell que nos permite gestionar las impresiones.

completar con filminas de las clases

Administracion de Usuarios y Grupos

Los archivos que contienen las informacion sobre cada usuario y grupo ademas de sus contraseñas
cifradas son /etc/passwd /etc/group /etc/shadow /etc/gshadow:

Entradas para cada uno:

/etc/passwd:
usuario:x(significa que posee contraseña cifrada):uid:gid:descripcion:dir-conexion:shell

/etc/group:
nombre-grupo:x:gid:otros-miembros

/etc/shadow:
nombre:clave-cifrada:dias que paso desde 1970 hasta ultima mod de contra:minimo de dias antes de
poder cambiar contra: maximo de dias con un contra: catn dias para avisar antes de caducar
contra:cant dias de contra caducada:cant dias con cuenta deshabilitada:R(espacio reservado).

/etc/gshadow:
nombre:contraseña:uid:gid:descripcion:shell

adduser
Agregar usuarios (version con guia)

useradd [opciones] nombre-usuario

Agregar usuarios (version one-line)
-u uid
-g grupo primario
-G grupos secundarios
-c comentario
-p contraseña
-e fecha de expiracion
-s shell
-d directorio de conexión

groupadd [opciones] cuenta-grupo

Crea una cuenta de grupo nueva
-g gid (valores entre 0 y 99 se reservan)

groupmod [opciones] grupo

Modifica el grupo
-g gid
-n nombre

groupdel grupo
Elimina el grupo

gpasswd
Permite cambiar la contraseña del grupo

grpconv y grpuncov
Convierten al formato gshadow o eliminan el formato gshadow

newgrp nombre-grupo
Permite que el usuario cambie de grupo primaria temporalmente.

usermod [opciones] usuario

Modifica un usuario
-c Nuevo comentario
-d Asigna un nuevo directorio HOME
-e Establece fecha de expiracion
-f Esablece fecha de expiracion de la contraseña
-g (gid) nuevo grupo primario
-G estableve los grupos a los que pertenecera.
-L bloquea la cuenta de usuario.
-m mueve el directorioa HOME a otra localizacion
-o establecer una ID no unica
-s selecciona un nuevo shell
-u nuevo valor de ID al usuario
-U desbloquea la cuenta de usuario

userdel usuario
Elimina un usuario

pwconv pwuncov
Estos comandos convierte el formato shadow o elimina el formato shadow.

chown [opciones] nuevo-propiertario archivos

Cambia el propietario y grupo de un archivo
-R cambia los permisos recursivamente sobre los archivos/directorios especficados.
-c muestra un mensaje sobre los nombres de los archivos cuyo dueño cambia.

Chgrp nuevo-grupo archivos

Permite cambiar el grupo de usuarios de un archivo o directorio.

Chsh
Cambia el shell de un usuario activo

Who
Lista los nombres de los usuarios activos conectados actualmente en el sistema.
-b la hora del ultimo arranque del sistema
-s procesos muertos
-H muestra los encabezados de cada columna

etc/login.defs
En este archivo se definen las variables que permiten controlar los valores por defecto al crear un
usuario, y los valores en el archivo shadow
 Comunicacion entre Usuarios

Linux es un Sistema que facilita las comunicaciones via red para el manejo de servicios y de
aplicaciones. Entre las necesidades existe la comunicación entre usuarios conectados en este
sistema mientras que trabajan.

wall (enter)
Envia un mensaje a todos los usuarios del sistema.

Una vez dado enter se escribe el mensaje en la entrada estandar y finaliza con ctrl+d. El mismo
aparecera en las terminales de los usuarios logueados.

rwall
Mismo que wall pero envia el mensaje a todos los sistemas de la red local suscriptos al host, no
solo a los usuarios del sistema actual.

El demonio que verifica la existencia de nuevos mensajes se denomina rwalld y debe estar activo
para poder emitir y recibir mensajes.

write [usuario/terminal]
Envia mensajes a usuarios especificos.

mesg [y/n]
Habilita o deshabilita la comunicación de mensajes entre usuarios por medio de write

mail [opciones] usuarios

Utilidad de envio de mails hacia otros usuarios.

Programación en Shell
Los shellscript son archivos de texto que contienen una serie, conjunto y/o grupo de comandos con
el objetivo de la automatizacion de tareas que son interpretadas por el shell, agregándole control de
flujo instrucciones como en un lenguaje de programación.
Los shellscripts se ejecutan en un subshell, por lo que no modifican variables del entorno del shell
almenos que se explicite de la siguiente manera:
“. ./comando” (se agrega un punto inicial antes del path del comando).
Para ejecutar el shellscript debe especificarse el path del mismo si este no está incluido en la
variable $PATH del entorno. Se lo puede agregar mediante la linea: PATH=(ruta):$PATH.

Variables:
Locales: Se define en una zona de datos local (propia del shell actual). Sus valores influyen
unicacmente en la sesion de shell actual, no en otros procesos.
Entornos: Zona de datos de todas las variables cuyos valores son iguales para todos los shells, como
definidas durante el inicio de sesion.
Las variables son unicamente de tipo carácter.

Asignacion
Directa:
variable=valor
variable=“cadena de caracteres con espacios”

Por sustitucion de comandos:

var=`comando` (guardará la salida del comando)
var=$(comando) (mismo efecto)

export
Exporta los datos locales al entorno.

declare [opciones] [var=valor]

Declara un conjunto de variables o reasigna sus valores. Debe pasarse los identificadores de las
variables (sin el signo de dólar).
± i activa o desactiva
-f solo muestra nombres de funcion
-r activa el atributo de solo lectura de la variable.
± x activa o desactiva la variable para poder ser exportado al entorno.

read [vars]
Lee los valores de las variables de la entrada estandar, los espacios son separadores de valores. Si
la cantidad de entradas (separadas por espacio) sobrepasan la cantidad de variables, las restantes se
definen como una sola cadena sobre la ultima variable. SOLO LEE ENTRADA ESTANDAR, NO
ES POSIBLE EL REDIRECCIONAMIENTO.

Metodos para acceder al contenido de una Variable

$variables Sustituye por el contenido

${variable} Sustituye por el contenido, usado para concatenar el identificador con
cadenas de caracteres o el contenido de otras varaibles.
${variable-palabra} Si la variable esta configurada, se usa el contenido, sino, se coloca
“palabra”
${variable+palabra} Si la variable esta configurada, se usa “palabra”, sino, se ignora.
${variable=palabra} Si la variable no esta configurada, asigna “palabra” como valor de la
variable
${#variable} Sustitutye por la longitud, en caracteres, del valor de la variable.

$? Resultado de la ejecucion del comando anterior (0 como éxito, cualquier otro

como un codigo de error).
$! Identificador del ultimo proceso ejecutado en background
$- Opciones establecidas configuradas desde el comando “set”
$# Cantidad de argumentos posicionales pasados al comando.
$0 Nombre del comando
$[1-9…] Argumentos posicionales
$* o $@@ Lista de comandos posicionales
$$ Identificador del proceso actual.

shift: mueve los la posicion de los parametros (los argumentos pocisionales) hacia la izquierda.
Exit: retorna un código numérico hacia la variable #? finalizando la ejecucion del shellscript para
informar el estado con el que finalizó.

env [opciones ] comando

Ejecuta un comando o archivo de comandos en un entorno diferente al actual, que puede ser
modificado para su uso particular. Sin argumentos lista las variables del entorno actual.
--unset variable elimina dicha variable en el entorno.
variable=valor cambia o crea una variable con un valor determinado.
-i comienza con un entorno vacio, ignorando el heredado.

printenv variables
Imprime todos o una lista de variables pasadas como argumentos.
Estados de salida:
0 se encontraron todas las variables de entornos
1 si no se encontro almenos una de las variables de entorno
2 si ocurrio un error de escritura

Set
Muestara tanto las variables locales como de entorno sus valores correspondientes.

Unset [opciones] lista-variables

Asigna a las variables especificadas el valor NULL
-f indica que los argumentos hacen referencia a funciones y no a variables.

export [lista de variables]

Exporta el valor de una lista de variables para que pueda set accedido por un subshell

Agrupaciones de comandos

Secuencia de comandos: se usa “;”.

Órdenes condicionales:
(comando)&&(comando): El segundo comando es ejecutado solo si el primero termina con éxito.
(comando)||(comando): El segundo comando se ejecuta solo si el segundo no termina con éxito.

grupo de comandos: Son órdenes secuencias encerradas con paréntesis y donde las entradas y las
salidas las tratan como una sola.
Ejemplo: (ls ~/; pwd) >> archivo (envia las salidas de ambos al mismo archivo).

Tuberias (Pipelines): La entrada de uno es la salida del anterior : uso de “|”

Estructuras de Control de Flujo

Est. Condicional IF-FI: evalua el estado de salida de un comando ejecutado para decidir si ejecuta
(éxito) un bloque de comandos especificados. Caso contrario puede ejecutarse un bloque alternativo
con la palabra reservada “else”
if comando-a-ejecutar
then
comandos
elif (opcional)
then
comandos
else (opcional)
comandos
fi

Est. Condicional CASE-ESAC: Evalua el valor de una variable entre posible candidatos para
decidir que bloque de comandos ejecutar.
case $variable in
patron |(ó) patron-alternativo) comandos
;;
…
*) (opcional por default)
;;
esac

Est. Repetitiva FOR: ejecucion finita de veces donde cada iteracion lee un elemento diferente de
una lista dada.

for i in lista-variables
do
comandos
done

puede utilizarse la salida de un comando captado entre comillas especiales “´comando´”, como ls.

Est. Repetitiva WHILE: Ejecuta un conjunto de comandos mientras la ejecucion de un comando

especifico permanezca con una salida exitosa.

while comando
do
comandos
done

Puede usarse la palabra “true” para crear un loop infinito que sea terminado desde dentro con un
comando “break”

test
Permite comprobar el valor de una expresion. Las expresiones pasadas como argumentos pueden
combinarse con los condicionales (com)&&(com), (com)||(com) y !(com)
Verificacion de Archivos:
“test opcion archivo”
-a existe el archivo
-b existe y es especial de blqoues
-c existe y es especial de caracter
-d existe como directorio
-s existe y tiene tamaño mayor a cero
-f existe y es regular
-r el usuario tiene permiso de lectura
-w el usuario tiene permiso de escritura
-x el usuario tiene permiso de ejecucion

Comprobacion de cadenas:
“test [opcion cadena] [cadena operado cadena]”
-z cadena nula
-n existe la cadena

operadores:
cade1=cade2 cad1 igual a cad2
cade1==cade2 ambas iguales
!= cambas distintias
cadena cadena no nula
cad1<ca1d
cad1>cad2

Operadores Aritmeticos:
num -eq num
num -ne num
num -gt num
num -ge num
num -lt num
num -le num

break [n]
Finaliza la ejecucion de l estructura repetitiva. N indica la cantidad de niveles de estructuras se
finalizan

continue [n]
Finaliza la iteracion actual saltando a la siguiente. N cumople misma funcion

let
Permite operar con variables numéricas dentro de script.
Ej : let num=var1+var2, let var=var+1 o let var+=1

expr [operando] [operador] [operando]

Resuelve operaciones aritmeticas
+ suma
- resta
\* multiplicacion
% modulo
/ division
 eval
Obtiene el valor de los argumentos de la linea de comandos y los ejecuta. Al usar comillas dobles
para una cadena, las variables contenidas dentro son sustituidas, pero en comillas simples no.
Anteponiendo eval se asegura dicha sustitucion
Ej:
data=”~”
var=”ls -la $data” (se sustituye)
echo $var (muestra ls -la ~)
$var (ejecuta ls -la ~)

var2=‘ls -la $data’ (no se sustituye)

echo $var2 (muestra ls -la $data)
eval echo $var2 (muestra ls -la ~)
eval $var (ejecuta ls -la ~)

Declaracion de funciones:
function nombreFuncion() {
comandos
}

nombre [argumentos]
 RESUMEN
DE
SINTAXIS Y SEMANTICA
DE LOS LENGUAJES
 lOMoARcPSD|2834310

SSL – Teórico
Pre-RESUMEN (Rev. 3)

UTN FRC – 2018 – Digitaliza tus resúmenes y compártelos.

Este apunte es un “pre-resumen”. Se concentran en él los principales conceptos de la materia sin

mucha ejemplificación. Los ejemplos que podrían esclarecer los temas explicados se encuentran
en la bibliografía obligatoria de la cátedra en la cual está basado este pre-resumen (Lenguajes
Formales y Teoría de Autómatas – Giró, Vázquez, Meloni, Constable).
A partir de este pre-resumen, el alumno tendrá una herramienta de lectura rápida y subrayado
para repasos y preparación de parciales y finales.
También se puede utilizar este apunte para acompañar durante las clases teóricas.

Contenido
Unidad n°1: Introducción a la Teoría de la Computación ................................................................. 7
Lenguajes naturales ................................................................................................................. 7
Lenguajes formales .................................................................................................................. 7
Máquinas abstractas ............................................................................................................... 7
Características de las máquinas abstractas .............................................................................. 7
Función de transición total o completa .................................................................................... 8
Función de transición parcial ................................................................................................... 8
Máquinas traductoras ............................................................................................................. 8
Máquinas reconocedoras ........................................................................................................ 8
Autómatas finitos .................................................................................................................... 8
Máquinas secuenciales ............................................................................................................ 8
Autómatas deterministas ........................................................................................................ 9
Autómatas no deterministas ................................................................................................... 9
Diferencia entre automatismos y autonomía ........................................................................... 9
Jerarquía de máquinas y gramáticas ............................................................................................ 9
Vínculo entre máquinas y gramáticas .................................................................................... 11
Unidad n°2: Gramáticas y lenguajes formales................................................................................ 13

1
 lOMoARcPSD|2834310

Signo ..................................................................................................................................... 13
Lenguaje concepto ................................................................................................................ 13
Lingüística Matemática.............................................................................................................. 13
Alfabeto ................................................................................................................................ 13
Palabra, cadena, tira o string ................................................................................................. 14
Longitud de palabra ............................................................................................................... 14
Cadena vacía ......................................................................................................................... 14
Potencia de una palabra ........................................................................................................ 14
Partes de una palabra ............................................................................................................ 14
Operaciones con alfabetos .................................................................................................... 14
Universo de discurso de un alfabeto 𝚺................................................................................... 14
Estrella de Kleene de un alfabeto .......................................................................................... 15
Clausura positiva ................................................................................................................... 15
Lenguajes y operaciones............................................................................................................ 15
Lenguaje ................................................................................................................................ 15
Operaciones con lenguajes .................................................................................................... 16
Descripción de lenguajes: ...................................................................................................... 16
Gramáticas Formales ................................................................................................................. 16
Reglas de reescritura o producciones .................................................................................... 16
Gramática formal .................................................................................................................. 17
Lenguaje generado ................................................................................................................ 17
Equivalencia de gramáticas.................................................................................................... 17
Jerarquía de Chomsky ............................................................................................................... 18
Tipo 0: Lenguajes estructurados por frases: ........................................................................... 18
Tipo 1: Lenguajes dependientes del contexto: ....................................................................... 18
Tipo 2: Lenguajes independientes del contexto: .................................................................... 18
Tipo 3: Lenguajes regulares o lineales: ................................................................................... 18
Jerarquía inclusiva: ................................................................................................................ 19
Lenguajes regulares ................................................................................................................... 19
Expresiones regulares en forma recursivas ............................................................................ 19
Lenguajes independientes del contexto .................................................................................... 20
Gramática limpia ................................................................................................................... 20
Gramática bien formada ........................................................................................................ 20

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Análisis sintáctico ...................................................................................................................... 20

¿𝜶 ∈ 𝑳(𝑮)? ........................................................................................................................... 20
Árbol de derivación ............................................................................................................... 20
Ambigüedad .......................................................................................................................... 21
Recursión .............................................................................................................................. 21
Eliminación de la recursión por izquierda en un paso: ........................................................... 21
Eliminación de recursión izquierda en más de un paso: ......................................................... 21
Factorización por izquierda.................................................................................................... 22
Forma normal de Chomsky (FNC) .............................................................................................. 22
Forma normal de Greibach (FNG) .............................................................................................. 22
Unidad n°3: Máquinas secuenciales y autómatas finitos deterministas ......................................... 23
Autómata finito ..................................................................................................................... 23
Máquinas secuenciales .......................................................................................................... 23
Máquina de Mealy................................................................................................................. 24
Máquina de Moore ................................................................................................................ 24
Autómata finito determinista (AFD) .......................................................................................... 25
Autómata finito reconocedor (AFDR): .................................................................................... 25
Configuración o descripción instantánea ............................................................................... 25
Movimiento ........................................................................................................................... 26
Extensión al tratamiento de palabras .................................................................................... 26
Aceptación de palabras y lenguajes ....................................................................................... 26
Accesibilidad entre estados ................................................................................................... 27
Autómatas conexos ............................................................................................................... 27
Equivalencia entre estados .................................................................................................... 27
Equivalencia de longitud “k” entre estados............................................................................ 27
Equivalencia entre autómatas ............................................................................................... 27
Conjunto cociente ................................................................................................................. 27
Minimización de autómatas: ..................................................................................................... 28
Autómata mínimo ................................................................................................................. 28
Autómatas finitos bidireccionales .............................................................................................. 28
Aceptación de cadenas .......................................................................................................... 29
Configuración ........................................................................................................................ 29
Lenguaje reconocido por el AFDB .......................................................................................... 29

3
 lOMoARcPSD|2834310

Conceptos de compiladores e intérpretes ..................................................................................... 30

Conceptos relacionados:........................................................................................................ 30
Tipos de compiladores: .......................................................................................................... 30
Contexto del compilador: ...................................................................................................... 31
Estructura y componentes del compilador: ........................................................................... 32
Análisis léxico ........................................................................................................................ 32
Análisis sintáctico .................................................................................................................. 32
Análisis semántico ................................................................................................................. 33
Generación de código intermedio ......................................................................................... 33
Optimización de código ......................................................................................................... 33
Generación del programa objeto ........................................................................................... 33
Gestor de la tabla de símbolos............................................................................................... 33
Identificación y gestión de errores ......................................................................................... 33
Errores de programación ........................................................................................................... 33
Errores lexicográficos ............................................................................................................ 34
Errores sintácticos ................................................................................................................. 34
Errores semánticos ................................................................................................................ 34
Fallas en el compilador .......................................................................................................... 35
Errores de ejecución .............................................................................................................. 35
Unidad 4: Autómatas finitos no deterministas............................................................................... 36
AFND ......................................................................................................................................... 36
Transiciones 𝛌 ....................................................................................................................... 36
Extensión al tratamiento de palabras .................................................................................... 37
Equivalencia con autómatas finitos deterministas ................................................................. 37
Gramáticas regulares y autómatas finitos .................................................................................. 38
Definición de gramática regular a partir de AFD .................................................................... 38
Definición de autómatas a partir de gramáticas regulares ..................................................... 38
Conversión de gramática lineal por izquierda a lineal por derecha ........................................ 38
Expresiones regulares y autómatas finitos ................................................................................. 39
Método o algoritmo de Thompson: ....................................................................................... 39
Unidad 5: Autómatas con pila ....................................................................................................... 41
Definición del AP ....................................................................................................................... 41
Concepto de configuración o descripción instantánea ........................................................... 41

4
 lOMoARcPSD|2834310

Aceptación de lenguajes ........................................................................................................ 41

No equivalencia entre los APD y APND .................................................................................. 42
AP deterministas y transiciones 𝝀 .......................................................................................... 42
Autómatas con pila asociados a una gramática ......................................................................... 42
Analizadores sintácticos descendentes (ASD) ........................................................................ 43
Analizadores sintácticos ascendentes .................................................................................... 43
Analizadores sintácticos con preanálisis ................................................................................ 44
Unidad 6: Autómata linealmente acotado y máquina de Turing .................................................... 45
Definiciones .............................................................................................................................. 45
Configuración instantánea de ALA y MT ................................................................................ 46
Interpretaciones del ALA y MT .................................................................................................. 46
Máquina reconocedora de lenguajes ..................................................................................... 46
Máquina ejecutora de procedimientos .................................................................................. 46
Máquina de Turing modular ...................................................................................................... 47
Máquina de Turing no determinista .......................................................................................... 47
Variantes de la Máquina de Turing ............................................................................................ 47
Combinación de máquinas de Turing ..................................................................................... 47
Máquina Universal de Turing ................................................................................................. 47
Máquina de Turing generalizada............................................................................................ 47
Complejidad de la MT ................................................................................................................ 48
Concepto ............................................................................................................................... 48
Medidas de la complejidad .................................................................................................... 48
Clases de problemas .............................................................................................................. 48
Unidad 7: Simuladores de máquinas abstractas ............................................................................ 49
Especificación de requerimientos de un SMA ............................................................................ 49
Requerimientos funcionales de un SMA ................................................................................ 49
Requerimientos no funcionales de un SMA ........................................................................... 49
Interfaz gráfica (GUI) ............................................................................................................. 50
Arquitectura de los simuladores ................................................................................................ 50
Editor .................................................................................................................................... 50
Generador de movimientos ................................................................................................... 50
Gestor de representación ...................................................................................................... 50
Unidad 8: Introducción a la semántica de lenguajes ...................................................................... 51

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Aspectos generales.................................................................................................................... 51
Conceptos de semántica de lenguajes ....................................................................................... 51
Metalenguajes para la especificación semántica de lenguajes ................................................... 52
Semántica operacional .......................................................................................................... 52
Semántica denotacional ........................................................................................................ 52
Semántica axiomática ............................................................................................................ 52
Semántica algebraica ............................................................................................................. 52
Semántica de acciones .......................................................................................................... 52
Gramáticas con atributos .......................................................................................................... 53
Definición de GA .................................................................................................................... 53
Atributos ............................................................................................................................... 54
Atributos sintetizados ............................................................................................................ 54
Atributos heredados .............................................................................................................. 54
Acciones semánticas .............................................................................................................. 55
Condiciones ........................................................................................................................... 55

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Unidad n°1: Introducción a la Teoría de la Computación

Lenguajes naturales
Evolucionan permanentemente según usos y costumbres de los pueblos y épocas, con gramáticas
que deben esforzarse para explicarlos y justificarlos.
Lenguajes formales
Son desarrollados a partir de gramáticas previamente establecidas y no admiten forma alguna de
excepción o desviación. Son los apropiados para la interpretación inequívoca de mensajes.

Noam Chomsky “Teoría de las Gramáticas Transformacionales” (1956).

Máquinas abstractas
(Autómatas) dispositivos formales capaces de exhibir conductas que han sido previamente
determinadas. Se trata de sistemas reactivos que operan en respuesta a los sucesivos estímulos
recibidos del exterior, que llevan a los mismos a adoptar condiciones características que son
denominadas estados y eventualmente a enviar una respuesta al medio exterior.

Características de las máquinas abstractas

1. Reconocen que el tiempo avanza y lo hace en forma discreta;

2. En cada uno de esos intervalos de tiempo una máquina se encuentra en un cierto y único
estado. El conjunto de sus estados posibles es finito y está agrupado en un conjunto o
alfabeto de estados;
3. La máquina recibe información o estímulos del medio exterior, para lo cual se incorpora el
concepto de una cinta de entrada. En cada intervalo de tiempo la máquina lee un símbolo
de la cinta de entrada y el conjunto de todos los símbolos reconocidos por la máquina es
agrupado en un conjunto llamado alfabeto de entrada;
4. En algunos casos, la máquina de estados también actúa sobre el medio exterior, grabando
símbolos sobre una cinta de salida, los cuales pertenecen al alfabeto de salida;
5. Las lecturas y grabaciones en cinta son realizadas en cada intervalo de tiempo por
“cabezales” apropiados. Estos cabezales se van desplazando sobre los medios de entrada y
salida;
6. Función de transición: en esta función se define para cada símbolo de entrada y para cada
estado posible el próximo estado a ser adoptado. Si la máquina tiene salida, en la función
de transición debe definirse el símbolo a ser grabado en la cinta correspondiente.

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Función de transición total o completa

Si la función de transición definiera el próximo estado de la máquina para cada símbolo de entrada
y para cada estado posible, se trataría de una función total o completa. Es decir, para cada
elemento del dominio representado por el producto cartesiano de las entradas y los estados, está
definido el correspondiente elemento del codominio, que es un próximo estado. En muchos casos
esto no resulta práctico ya que resulta innecesario definir la función de transición para
condiciones en las que la máquina no se va a encontrar nunca, entonces se admite que se trate de
una función parcial.

Función de transición parcial

Cuando no todos los elementos del alcance están asociados con algún elemento del rango. Esto
significa que hay condiciones de operación en las que la máquina abstracta no tiene definido el
próximo estado de operación.
Nada impide que a todas las condiciones no definidas de una función de transición parcial se les
asigne un estado de error, lo que convierte a la función de transición en completa.

Máquinas traductoras
Son a aquellas que establecen una relación entre las cadenas de entrada y las cadenas de salida.

Máquinas reconocedoras
Validan o aceptan ciertas cadenas de entrada, arribando a estados finales definidos como de
aceptación, sin producir ninguna cadena de salida.

Autómatas finitos
Estos autómatas comienzan su operación en un estado conocido, que es denominado estado
inicial, y completan su ciclo arribando a un estado de aceptación que ha sido oportunamente
identificado. Su comportamiento es algorítmico.

Máquinas secuenciales
No tienen previsto estados de aceptación y en algunos casos, tampoco tienen definidos estados de
inicio de su operación. Esto significa que las máquinas secuenciales operan en forma
ininterrumpida, sin reconocer condiciones específicas para iniciar y terminar su actividad.

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Autómatas deterministas
Las funciones de transición de los autómatas deterministas contemplan un único próximo estado a
partir de cada estado posible y cada símbolo del alfabeto de entrada.

Autómatas no deterministas
La función de transición puede prever más de un próximo estado para cierta condición de estado y
entrada. Otro rasgo que puede diferencias a los autómatas no deterministas es la posibilidad de
realizar transiciones de un estado a otro sin necesidad de leer ningún símbolo de entrada.
Es fácil advertir que los autómatas finitos deterministas (AFD) son un caso particular de los
autómatas finitos no deterministas (AFND).
Todo autómata finito no determinista tiene siempre un autómata finito determinista equivalente,
mientras que en el caso de los autómatas con memoria de pila esta equivalencia no
necesariamente existe.

Diferencia entre automatismos y autonomía

En la conducta de un sistema automático no habrá nada que no haya sido oportunamente previsto
por su creador. Por el contrario, autonomía implica la capacidad de alterar por sí solo el propio
comportamiento y esto surge de la interacción del sistema con su entorno.
1. El comportamiento de los sistemas automáticos está completamente predeterminado;
2. Para que un sistema sea autónomo deber antes automático;
3. En los sistemas autónomos el comportamiento es una propiedad emergente de la
interacción del sistema y su ambiente.

Jerarquía de máquinas y gramáticas

En las máquinas orientadas a reconocer lenguajes, importa precisar el diferente rol que tienen las
gramáticas y las máquinas o autómatas: las primeras son metalenguajes destinados a la
generación de los lenguajes formales y las últimas son modelos de entidades reconocedoras de
esos lenguajes. El lenguaje es el vínculo que estable un isomorfismo entre ambas (isomorfismo
entre dos estructuras es cuando el estudio de cada una puede reducirse al de la otra)

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

10

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Chomsky utilizó las formas que toman las reglas de producción de las gramáticas para proponer
una clasificación en cuatro tipos, en el que las menos restringidas incluyen sucesivamente a las
siguientes:

Vínculo entre máquinas y gramáticas

1. Autómata finito y gramáticas regulares: El autómata muestra sus principales componentes

que son: un conjunto de estados, su función de transición, una cinta que contiene los
símbolos del alfabeto de entrada y su cabezal de lectura que se mueve en el mismo sentido
con el fin de leer secuencialmente la cadena a ser procesada.

11

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

2. Autómata a pila y gramáticas independientes de contexto: Al proponer este autómata es

necesario definir el alfabeto vinculado a la pila, que puede tener símbolos en común con el
alfabeto de entrada y en el que se debe identificar un símbolo destinado a señalar el fondo
de la pila. La función de transición debe ser ampliada para incorporar como argumento el
símbolo leído de la pila y para prever la salida sobre ella.

3. Autómata finito bidireccional y gramáticas regulares: Aquí también la función de transición

debe ser ampliada para incorporar la definición del movimiento del cabezal. La cadena de
datos a ser procesada es contenida entre dos símbolos especiales destinados a limitar el
movimiento del cabezal sobre la cinta.

4. Autómata linealmente acotado y gramáticas dependientes de contexto: Esta máquina

puede grabar sobre la misma cinta de entrada. Esto implica ampliar nuevamente la función
de transición para incorporarle la definición del símbolo que es grabada en cada caso. Es
decir, que esta función ahora define el próximo estado, el símbolo grabado y el sentido del
movimiento del cabezal.

5. Máquina de Turing y gramáticas sin restricciones: Cuando eliminamos los límites extremos
de la cinta de entrada/salida, permitimos el acceso a un espacio ilimitado que puede ser
usado como un área auxiliar de almacenamiento. Esta máquina está relacionada con todas
las gramáticas, incluyendo la última en la escala de Chomsky que no tiene restricciones.

12

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Unidad n°2: Gramáticas y lenguajes formales

Signo
Concepto abstracto que permite hacer referencia a objetos. El proceso por el cual se toma un
objeto como signo de algo se denomina interpretación. La interpretación determina que el signo
actúe como tal, ya sea porque permite relacionar al signo con su objeto o bien porque el signo se
asocia a una idea o pensamiento. Fundamentalmente, interesa destacar que sin interpretación no
hay signo. Si bien pueden ser tomados como sinónimos, un símbolo es un signo creado
convencionalmente.
Se llama denotado al objeto al que se refiere el signo y designado a las características o
propiedades a las que se remite el signo. Por ejemplo, el signo vaso designa a un objeto con forma
de recipiente destinado a contener líquidos y denota a todos los objetos a los que es aplicable el
signo, es decir a todos los vasos.

Lenguaje concepto
Conjunto de signos y de reglas que organizan esos signos. Estas reglas destinadas a establecer las
relaciones entre los signos de un lenguaje son de tres tipos:
1. Reglas sintácticas: establecen el orden y la relación entre los signos.
2. Reglas semánticas: relacionan los signos y sus significados.
3. Reglas pragmáticas: vinculan los signos con sus usuarios.
Al establecer el orden y la relación entre signos, las reglas sintácticas permiten combinar las
palabras para formar frases correctas.

Lingüística Matemática
Alfabeto
Se denomina alfabeto a cualquier conjunto finito y no vacío de símbolos. Como se trata de
conjuntos:
• Dos alfabetos son iguales si y solo si tienen exactamente los mismos símbolos.
• Si todos los símbolos de un alfabeto Ω están también en otro alfabeto Ω se dice que el
primero está incluido en el segundo y se lo denota Ω ⊆ Ω , también se dice que Ω es un
subconjunto de Ω . Si además, el segundo alfabeto posee al menos un símbolo que el
primero no tiene, se dice que el primero está estrictamente incluido en el segundo,
denotándose en este caso Ω ⊂ Ω , se expresa en este caso que Ω es un subconjunto
propio de Ω .
• El cardinal de un alfabeto dado Ω, denotado como |Ω| es la cantidad de símbolos que el
mismo posee y siempre será, por definición un número entero positivo.
13

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Palabra, cadena, tira o string

Una palabra definida sobre un alfabeto Σ es cualquier secuencia finita de símbolos de Σ escritos
uno a continuación del otro. Las palabras formadas con símbolos de algún alfabeto pueden a su
vez concatenarse entre ellas para formar nuevas palabras. Se indica el resultado de esta operación
entre palabras con α.β o simplemente αβ.
Longitud de palabra
La cantidad de símbolos que conforman una palabra es llamada su longitud o largo y se denota
con el nombre de la cadena entre barras verticales.
Cadena vacía
Se denota con λ a la palabra vacía, palabra que no tiene símbolos y cuyo largo es cero. La palabra
vacía resulta ser así, elemento neutro respecto de la operación de concatenación entre palabras.
Potencia de una palabra
La concatenación de una palabra consigo misma permite definir en la misma forma que se ha
hecho para símbolos, la potencia enésima de una palabra.
Se acepta la notación α −1 para denotar a la palabra refleja de una cadena α, obtenida escribiendo
los símbolos de α en orden inverso.
Partes de una palabra
Una palabra cualquiera puede dividirse en sus símbolos constituyentes y hasta en subpalabras.
Supongamos una cadena puede escribirse como concatenación de otras tres, , se dice
entonces que α es un prefijo de ω, que β es un sufijo de ω y que γ es una
subpalabra de ω. De un sufijo o prefijo de una palabra se dice que es propio si NO es la misma
palabra en cuestión o la palabra vacía.
Operaciones con alfabetos
• Σ1∪Σ2={todos los símbolos comunes y no comunes de ambos alfabetos }

• Σ1∩Σ2={todos los símbolos comunes a ambos alfabetos}

• Σ1−Σ2={todos los símbolos del primer alfabeto que no estén en el segundo}

• (en este caso debemos definir el universal contra el cual complementar)

• Dados dos alfabetos Σ 𝑦 Σ , la concatenación de Σ y Σ denotada como Σ . Σ o
simplemente Σ Σ es el conjunto de palabras formadas por la concatenación de cada
símbolo de Σ con cada uno de Σ en ese orden. Debe notarse que lo obtenido de
concatenar dos alfabetos no es generalmente un nuevo alfabeto, sino un conjunto de
palabras.
Universo de discurso de un alfabeto 𝚺
Conjunto de todas las palabras que pueden formarse con sus símbolos sean del largo que sean.
También llamado lenguaje universal y denotado 𝑊(Σ) o Σ ∗ .

14

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Estrella de Kleene de un alfabeto

También recibe el nombre de cierre o clausura del alfabeto:

Σ∗ = Σ

Clausura positiva
Si se quita de la unión anterior la potencia cero, es decir, se elimina la palabra vacía, se obtiene el
conjunto de todas las palabras de símbolos de largo uno o mayor denominado clausura positiva:

Σ = Σ = Σ − Σ = Σ∗ − {𝜆}

Lenguajes y operaciones
Lenguaje
Un lenguaje definido sobre un alfabeto es un conjunto de palabras construidas con los símbolos de
ese alfabeto. En símbolos, si Σ es un alfabeto y L es un lenguaje definido sobre Σ, entonces:
𝐿 ⊆ Σ∗

Algunos conceptos de conjuntos adaptados al contexto de lenguajes son los que siguen:
• Un lenguaje 𝐿 definido sobre Σ es subconjunto de otro 𝐿 si toda palabra de 𝐿 es también
palabra de 𝐿 :

𝐿1 ⊆ 𝐿2 ⇔ ∀𝛼 ∈ 𝛴 ∗ : 𝛼 ∈ 𝐿1 → 𝛼 ∈ 𝐿2

• Un lenguaje definido sobre 𝐿 definido sobre Σ es un subconjunto propio de otro 𝐿 si toda

palabra de 𝐿 es también palabra de 𝐿 y existe al menos una palabra del segundo que no
es elemento del primero:
𝐿 ⊂ 𝐿 ⇔ (∀ 𝛼 ∈ Σ ∗ : 𝛼 ∈ 𝐿 → 𝛼 ∈ 𝐿 ) ∧ ( ∃𝛽 ∈ Σ ∗ ⁄𝛽 ∈ 𝐿 ∧ 𝛽 ∉ 𝐿 )

• Un lenguaje L definido sobre Σ es igual a otro lenguaje L si tienen exactamente las ₁ ₂

mismas palabras:

𝐿1 = 𝐿2 ⇔ [ ∀𝛼 ∈ 𝛴 ∗ ∶ 𝛼 ∈ 𝐿1 ⇔ 𝛼 ∈ 𝐿2]

⇔ [𝐿1 ⊆ 𝐿2 ∧ 𝐿2 ⊆ 𝐿1 ]
• El conjunto vacío Ø es un lenguaje llamado lenguaje vacío, tiene cardinalidad cero y es el
único con esta propiedad, independientemente del alfabeto sobre el cual esté definido.
• {λ} el conjunto vacío cuyo único elemento es la cadena vacía, es también un lenguaje único
e independiente del alfabeto de definición. Debe notarse que su cardinalidad es uno, por lo
cual es bien distinto del lenguaje vacío definido anteriormente.

15

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Operaciones con lenguajes

Unión: 𝐿 ∪ 𝐿 = {𝛼 ⁄𝛼 ∈ L ∨ 𝛼 ∈ 𝐿 }

Intersección: 𝐿 ∩ 𝐿 = {𝛼 ⁄𝛼 ∈ 𝐿 ∧ 𝛼 ∈ 𝐿 }

Resta: 𝐿 − 𝐿 = {𝛼⁄𝛼 ∈ 𝐿 ∧ 𝛼 ∉ 𝐿 }

Concatenación: 𝐿 . 𝐿 = {𝜇 = 𝛼𝛽 ⁄𝛼 ∈ 𝐿 ∧ 𝛽 ∈ 𝐿 }

Complemento: 𝐿 = {𝛼⁄𝛼 ∈ Σ ∗ ∧ 𝛼 ∉ 𝐿 }

Descripción de lenguajes:
• Por extensión o enumeración, indicando una por una todas las palabras que son
elementos del mismo;
• Por compresión, explicitando propiedades de las cadenas definidas sobre algún alfabeto,
que solo las palabras del lenguaje verificarán.

Gramáticas Formales
Reglas de reescritura o producciones
Para un alfabeto Σ dado, diremos que una producción o regla de reescritura es un par ordenado de
palabras (α, β) definidas sobre Σ. Escribiremos las producciones utilizando una notación similar a la
denominada BNF² de la siguiente forma:
𝛼: = 𝛽
y diremos que la cadena α es el lado izquierdo de la producción, := el símbolo de producción, la
cadena β su lado derecho y la leeremos alfa produce beta.
Se llama derivación directa a la operación que aplica una sola producción a una palabra
obteniendo una nueva palabra y se simboliza:
𝛿→𝜑
Se dice que 𝛿 se deriva directamente en 𝜑, o que 𝜑 se obtiene por derivación directa desde por la
aplicación de una producción.

16

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Gramática formal
Una gramática formal G es una cuádrupla (ΣT , ΣN , S,P) donde sus componentes representan:
• Σ es el alfabeto de símbolos que formarán las cadenas del lenguaje que se está
describiendo y es denominado alfabeto de símbolos terminales
• Σ es un conjunto de variables o símbolos auxiliares llamado alfabeto de símbolos no
terminales
• 𝑆 ∈ Σ es un símbolo no terminal distinguido denominado axioma o símbolo inicial de la
gramática
• P es un conjunto de producciones de la forma α:=β donde ambas palabras están
compuestas de símbolos terminales y símbolos no terminales, pero en α al menos debe
encontrarse un símbolo no terminal.
El alfabeto de símbolos terminales es fundamental ya que todas las cadenas descriptas por la
gramática estarán construidas con estos símbolos. Los símbolos no terminales también son
llamados auxiliares ya que sirven para armar las producciones, pero nunca aparecerán en las
cadenas del lenguaje definido por la gramática. Por ello se exige que el alfabeto de símbolos no
terminales sea disjunto con el de terminales:

𝛴 ∩𝛴 =∅

Para un mismo lenguaje puede existir más de una gramática con distintos símbolos no terminales,
axioma y/o producciones, pero todas estas descripciones tendrán exactamente los mismos
símbolos terminales.

Lenguaje generado
Dada una gramática formal G=(ΣT ,ΣN ,S, P), se llama lenguaje formal generado por G al conjunto de
todas las cadenas de símbolos terminales que pueden derivarse desde el axioma S utilizando las
reglas de producción de P. En símbolos:
𝐿(𝐺 ) = {𝛼 ∈ Σ ∗ ⁄𝑆 →∗ 𝛼}
Se denomina forma sentencial o metapalabra a una cadena de terminales y no terminales
𝛼 ∈ (Σ ∪ Σ )∗ que puede derivarse desde el axioma de la gramática. La cadena final de
terminales a la que se arriba con la derivación desde el axioma pertenece al lenguaje generado
por la gramática y recibe también el nombre de sentencia o palabra generada por la gramática.

Equivalencia de gramáticas
Dos gramáticas son equivalentes si y solo si generan exactamente el mismo lenguaje:

𝐺 ≡ 𝐺 ⇔ 𝐿( 𝐺 ) = 𝐿 ( 𝐺 )
Para que esto ocurra, los alfabetos de símbolos terminales deben ser iguales. Nótese que basada
en la igualdad de lenguajes, la equivalencia de gramáticas es reflexiva, simétrica y transitiva, una
relación de equivalencia bien definida.
17

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Jerarquía de Chomsky

Tipo 0: Lenguajes estructurados por frases:

También llamados recursivamente enumerables. Las producciones pueden contener cualquier
cadena de terminales y no terminales tanto en el lado izquierdo como en el lado derecho, con al
menos un símbolo no terminal en el lado izquierdo.

𝛼𝐴𝛽 ∶= 𝛾 𝛼, 𝛽, 𝛾 ∈ (Σ ∪ Σ )∗ , 𝐴 ∈ Σ

Tipo 1: Lenguajes dependientes del contexto:

O sensibles al contexto, son lenguajes que permiten el reemplazo contextual de símbolos no
terminales. Sus producciones tienen la forma:

𝑆 ∶= 𝜆 ó 𝛼𝐴𝛽 ≔ 𝛼𝛾𝛽 𝛼, 𝛽 ∈ (Σ ∪ Σ )∗ , 𝐴 ∈ Σ , 𝛾 ∈ (Σ ∪ Σ )

Esto dice que el símbolo no terminal A, solo puede ser reemplazado por la cadena γ de terminales
y no terminales si se encuentra flanqueada por α a la izquierda y por β a la derecha, es decir, en el
contexto alfa-beta. Debe notarse que la cadena γ debe por lo menos tener largo unitario, por lo
cual en estas reglas siempre la cadena del lado derecho es de largo igual o menor que la cadena
del lado derecho (reglas no compresoras), sin embargo, el lenguaje podría contener como palabra
la cadena vacía, por lo cual ésta debe poder ser generada por la gramática como única regla
compresora permitida.

Tipo 2: Lenguajes independientes del contexto:

O de contexto libre, la mayoría de los lenguajes de programación se describe con gramáticas
independientes del contexto:

𝑆 ∶= 𝜆 ó 𝐴 ∶= 𝛼 𝐴 ∈ Σ , 𝛼 ∈ (Σ ∪ Σ )

Puede verse que el símbolo no terminal A, puede ser reemplazado por la cadena α de terminales y
no terminales en cualquier lugar donde aparezca durante el proceso de derivación, sin tener en
cuenta el contexto donde se encuentra. Nótese que estas reglas también son compresoras, salvo
la regla de lambda que tiene idéntica justificación que en el tipo 1.

Tipo 3: Lenguajes regulares o lineales:

Las producciones de las gramáticas que generan estos lenguajes tienen un solo símbolo no
terminal del lado izquierdo, pero su lado derecho está compuesto por un solo símbolo terminal, o
por un solo símbolo terminal y un símbolo no terminal, aparte de poder tener la regla lambda:

Regular por derecha: 𝑆 ∶= 𝜆 ó 𝐴 ∶= 𝑎𝐵 ó 𝐴 ∶= 𝑎 𝐴, 𝐵 ∈ Σ , 𝑎 ∈ Σ

18

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Regular por izquierda: 𝑆 ∶= 𝜆 ó 𝐴 ∶= 𝐵𝑎 ó 𝐴 ∶= 𝑎 𝐴, 𝐵 ∈ Σ , 𝑎 ∈ Σ

Jerarquía inclusiva:
Las gramáticas de Chomsky se diferencian unas de otras solo por el formato de sus producciones.
𝐿 ⊂𝐿 ⊂𝐿 ⊂𝐿

Lenguajes regulares
Admiten la siguiente definición recursiva:
1. Cualquier lenguaje finito 𝐿 definido sobre algún alfabeto Σ, es regular.

2. Si 𝐿 y 𝐿 son lenguajes regulares, entonces también lo son su unión 𝐿 ∪ 𝐿 y su

concatenación 𝐿 . 𝐿 .

3. Si 𝐿 es un lenguaje regular entonces su estrella de Kleene 𝐿∗ también es un lenguaje

regular.

4. Solo son lenguajes regulares los construidos con 1, 2 y 3.

Expresiones regulares en forma recursivas

Es una forma más compacta de especificar lenguajes regulares que las gramáticas tipo 3 de
Chomsky ya citadas. Se definen las expresiones regulares recursivamente como sigue:
Base de recursión: Sea Σ un alfabeto; entonces:
a) Ø es una expresión regular que denota al lenguaje vacío: 𝐿(∅) = ∅
b) λ es una expresión regular que denota al lenguaje cuyo único elemento es la cadena vacía
𝐿(𝜆) = {𝜆}
c) Cualquier símbolo 𝒂 del alfabeto Σ es una expresión regular que denota al lenguaje cuya
única palabra es la de largo unitario formada por ese símbolo 𝐿(𝑎) = {𝑎}.
Paso recursivo: Si E y F son expresiones regulares entonces
d) 𝐸 + 𝐹 es una expresión regular que denota al lenguaje unión de los lenguajes denotados
por E y por F : 𝐿 (𝐸 + 𝐹 ) = 𝐿( 𝐸 ) ∪ 𝐿 (𝐹 )
e) 𝐸. 𝐹 es una expresión regular que denota al lenguaje concatenación de los lenguajes
denotados por E y por F: 𝐿 (𝐸. 𝐹 ) = 𝐿 (𝐸 ). 𝐿( 𝐹 )
f) 𝐸 ∗ es una expresión regular que denota al lenguaje formado por la estrella de Kleene del
lenguaje denotado por E: 𝐿 (𝐸 ∗ ) = [𝐿(𝐸)]∗
g) (𝐸) es una expresión regular que denota al mismo lenguaje denotado por E: 𝐿 (( 𝐸 )) =
𝐿 ( 𝐸)
h) Solo son expresiones regulares las construidas con los pasos a) y g).

19

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Lenguajes independientes del contexto

Gramática limpia
Para llegar a una gramática limpia se verifica que no haya:
• Reglas innecesarias: es una regla de tipo A:=A.
• Símbolos inaccesibles: símbolo que no puede ser alcanzado desde el axioma por ninguna
derivación válida.
• Símbolos superfluos: símbolo no terminal que no permite generar desde él al menos
cadena vacía o de solo símbolos terminales

Gramática bien formada

Sea la regla A:=λ no siendo A el axioma, es una regla compresora (no pueden existir reglas
compresoras en gramáticas independientes del contexto). Para quitar una regla no generativa:
a) Para cada producción X :=α A β que contenga el no terminal A en el lado derecho, agregar
la regla de reescritura X :=α β que se obtiene de reemplazar A por la cadena vacía.
b) Luego eliminar del conjunto de producciones A:=λ, ya que todos los efectos que produciría
la misma, han sido incluidos explícitamente como producciones en el paso anterior.
Si tenemos producciones del tipo A:=B donde A y B son símbolos no terminales, esta producción,
llamada regla de redenominación dice que el no terminal A puede ser reescrito como B en
cualquier contexto donde se encuentre. Para eliminar estas reglas:
a) Por cada regla B:=αexistente en la gramática, agregar una regla 𝐴: = 𝛼 lo cual hace
explícita como producción la posible derivación en dos pasos 𝐴 → 𝐵 → 𝛼
b) Luego puede eliminarse A:=B del conjunto de producciones y la gramática obtenida será
equivalente a la original.

Análisis sintáctico
¿𝜶 ∈ 𝑳(𝑮)?
La forma que conocemos para lidiar con esa pregunta es encontrar una derivación 𝑆 →∗ 𝑎 que,
aplicando una cantidad finita de producciones de la gramática, logre transformar el axioma de la
misma en la cadena de terminales bajo análisis.
Se llama análisis sintáctico de la cadena α al proceso de búsqueda de esta derivación.

Árbol de derivación
Un árbol de análisis sintáctico tendrá:
• El axioma S de la gramática como raíz.

• Símbolos no terminales de ΣN como nodos internos.

20

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

• Para el nodo interno del no terminal A, si 𝐴: = 𝑎 𝑎 … 𝑎 es la producción usada, se

tendrán k nodos hijos etiquetados con los símbolos del lado derecho en el orden en el que
aparecen.

• Símbolos terminales de ΣT como hojas.

Ambigüedad
Se dice que una cadena es ambigua si puede ser generada por derivaciones que admiten distintos
árboles de análisis sintáctico.
Recursión
Una producción de una gramática independiente del contexto se dice que es recursiva si el no
terminal de su lado izquierdo se encuentra también del lado derecho 𝐴: = 𝛼𝐴𝛽
Una gramática que tiene una regla de reescritura recursiva, se dice que tiene recursión en un
paso. En el caso en el que un no terminal del lado izquierdo de una producción pueda derivarse en
una cadena que lo contenga en varios pasos: 𝐴 → 𝛿1 → 𝛿 → ⋯ → 𝛼𝐴𝛽 se dice que existe en la
gramática recursión en más de un paso.
Si en la regla recursiva 𝐴 = 𝛼𝐴𝛽 la cadena 𝛼 es vacía, esto es 𝐴: = 𝐴𝛽, se dice que la regla es
recursiva por izquierda y que la gramática tiene recursión izquierda. Si en cambio es 𝛽 la cadena
vacía 𝐴 ∶= 𝛼𝐴 se dice que la regla es recursiva por derecha y que la gramática tiene recursión
derecha.
Es menester eliminar la recursión izquierda modificando la gramática, pero haciendo que siga
generando el mismo lenguaje.
Eliminación de la recursión por izquierda en un paso:
Siendo 𝐴 ∶= 𝐴𝛼 |𝐴𝛼 | … |𝐴𝛼 |𝛽 |𝛽 | … |𝛽 se puede obtener una gramática equivalente sin
recursión izquierda haciendo lo siguiente:
a) Crear un nuevo símbolo no terminal X y agregarlo al alfabeto de símbolos no terminales:
Σ = Σ ∪ {𝑋}

b) Eliminar todas las producciones en P para el no terminal A.

c) Agregar al conjunto P las producciones donde se reemplazó X.
Eliminación de recursión izquierda en más de un paso:
a) Asignar un orden cualquiera a los símbolos no terminales, digamos 𝐴 , 𝐴 , … , 𝐴 .

b) Para cada 𝑖 = 1, 2, … 𝑘 hacer:

a. Para cada 𝑗 = 1, 2, … , 𝑘 hacer:

Si 𝑖 ≠ 𝑗, reemplazar cada 𝐴 ∶= 𝐴𝑗 𝛿 en P (eliminarla y agregar) por

𝐴 ≔ 𝛾 𝛿|𝛾 𝛿| … |𝛾 𝛿 donde los 𝛾 son los lados derechos de todas las producciones
de 𝐴 .
b. Eliminar recursión izquierda en un paso de 𝐴 , si la hubiere, aplicando el anterior
teorema.

21

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Factorización por izquierda

Es el caso de dos o más producciones que inicien con una parte común: 𝐴 ∶= 𝛼𝛽 𝑦 𝐴 ∶= 𝛼𝛾
En este caso el proceso de análisis sintáctico no tiene en claro cuál de las dos producciones utilizar
durante una derivación, aun sabiendo que tiene que emparejas una parte de la cadena bajo
análisis con α. Sin embargo, si se crea un nuevo no terminal X y se reemplazan las anteriores
producciones por: 𝐴 ≔ 𝛼𝑋 𝑦 𝑋 ≔ 𝛽 | 𝛾 procedimiento no tiene ahora dudas de lo que debe
utilizar, la primera producción primero, y recién al terminar de emparejar α con la cadena bajo
análisis, deberá decidir con cuál de las producciones de X continúa el análisis de la cadena bajo
estudio.

Forma normal de Chomsky (FNC)

Una gramática se dice que está en FNC si y solo si, todas sus producciones tienen en el lado
derecho dos símbolos no terminales, o un solo símbolo terminal o la cadena vacía:
𝐴: = 𝐵𝐶 ó 𝐴: = 𝑎 ó 𝑆: = 𝜆
Para llevar una gramática a FNC:
a) Transformar G en una gramática bien formada, esto es, limpia y sin reglas no generativas ni
de redenominación.

b) Para cada símbolo terminal 𝑎 ∈ 𝛴𝑇 , crear un nuevo símbolo no terminal 𝑋 y una nueva
producción 𝑋 ∶= 𝑎

c) Para cada producción de la gramática que contenga en su lado derecho tanto símbolos no
terminales como símbolos terminales, reemplazarla por una nueva que tenga en su lugar
del terminal 𝒂 su correspondiente nuevo terminal 𝑋 , es decir 𝐴: = 𝛼𝑎𝛽 → 𝐴: = 𝛼𝑋𝑎 𝛽 . Al
terminar con estos pasos se tendrá una gramática equivalente con producciones que solo
contienen en su lado derecho un solo símbolo terminal (es decir, que es está en FNC) o una
cadena de dos o más símbolos no terminales. Si tiene dos no terminales, entonces ya está
en FNC, caso contrario:
d) Para cada producción con más de dos símbolos no terminales en su lado derecho, digamos
𝐴: = 𝐵𝜂 donde 𝜂 contiene dos o más no terminales, crear un nuevo símbolo no terminal X
y reemplazar la producción por el par 𝐴: = 𝐵𝑋 y 𝑋 ∶= 𝜂.

Forma normal de Greibach (FNG)

Una gramática independiente del contexto está en FNG si y solo si todas sus producciones inician
su lado derecho con un símbolo terminal al que le sigue, opcionalmente, una cadena de símbolos
no terminales de cualquier largo: 𝐴: = 𝑎𝜂 ó 𝑆: = 𝜆
Para llevar una gramática a FNG:
a) Transformar G en una gramática bien formada
b) Quitar la recursividad izquierda de la gramática
c) Asignar un orden cualquiera a los símbolos no terminales de la gramática

22

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

d) Separar las producciones del conjunto P en tres grupos:

a. Grupo 1: todas las producciones que comiencen con un terminal y si existiere en G,
la regla lambda 𝑆: = 𝜆

b. Grupo 2: producciones 𝐴 ∶= 𝐴𝑗 𝛼 y con el símbolo 𝐴 anterior a 𝐴 en el

ordenamiento dado (i < j)

c. Grupo 3: producciones 𝐴 ∶= 𝐴 𝛼 y con el símbolo 𝐴 posterior a 𝐴 en el

ordenamiento dado (i > j)
El caso i = j no puede darse porque se ha eliminado la recursión por izquierda
anteriormente.
e) Para cada producción del tercer grupo 𝐴 ∶= 𝐴𝑗 𝛼 iniciando por aquellas con el subíndice i
más pequeño, reemplazarlas por 𝐴 ∶= 𝛿 𝛼|𝛿 𝛼| … | 𝛿 𝛼 donde los 𝛿 son los lados
derechos de todas las producciones de 𝐴 . Al terminar este proceso, todas las
producciones pertenecerán al grupo 1 o 2.
f) Repetir el proceso anterior para las producciones del segundo grupo. Al terminar, todas las
producciones serán del grupo 1, por lo cual todas iniciarán con un símbolo terminal.

g) Para cada símbolo terminal 𝑎 ∈ Σ que esté en el lado derecho de las producciones
resultantes, pero no al inicio de las mismas, crear un nuevo símbolo no terminal 𝑋 y una
nueva producción 𝑋 ∶= 𝑎.

h) Para cada producción de la gramática que contenga en su lado derecho, luego del primer
símbolo terminal, tanto símbolos no terminales como símbolos terminales, reemplazarla
por una nueva que tenga en lugar del terminal no inicial 𝒂 su correspondiente no terminal
𝑋 .

Unidad n°3: Máquinas secuenciales y autómatas finitos

deterministas

Autómata finito
En su forma más general, el autómata finito es también traductor, generará una cadena de salida,
y al completar la lectura de la cadena de entrada arribará a algún estado final. Es por este motivo
que en su operación el autómata finito determina un procedimiento afectivo o algorítmico.
Máquinas secuenciales
Para las máquinas abstractas más simples, se reserva la denominación de máquinas
secuenciales. Las principales son la máquina de Mealy y de Moore.

23

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Máquina de Mealy
Tiene 5 componentes y es definida así: 𝑀𝐸 = (𝛴𝐸 , 𝛴𝑆 , 𝑄, 𝑓 , 𝑔) donde:
• ΣE alfabeto de símbolos de entradas

• ΣS alfabeto de símbolos de salida

• Q Conjunto finito y no vacío de estados posibles

• f Función de transición: 𝑓 ∶ 𝑄𝑥 𝛴𝐸 → 𝑄

• g Función de salida 𝑔: 𝑄𝑥𝛴𝐸 → 𝛴𝑆

La función de transición f tiene la finalidad de definir el próximo estado que adoptará la máquina a
partir de su estado actual y cada uno de los posibles símbolos de entrada. De igual forma, la
función de salida g define la salida de la máquina a partir de los mismos argumentos.
La máquina de Mealy es traductora, lo que significa que establece una relación entre una cadena
de entrada y la cadena de salida.

Máquina de Moore
se diferencia de la máquina de Mealy únicamente en su función de salida, ya que ésta solo
depende del estado actual y no de la entrada en ese instante, es decir:

𝑀𝑂 = (𝛴 , 𝛴𝑆 , 𝑄, 𝑓 , 𝑔)
donde la función de transición f no cambia y en g hay una relación directa entre el estado en cada
intervalo de tiempo y el símbolo de salida: 𝑓 ∶ 𝑄𝑥 𝛴𝐸 → 𝑄 𝑔: 𝑄 → 𝛴𝑆

Debe recordarse que la máquina de Moore incorpora un retardo entre la entrada y la salida, si en
un instante de tiempo t el autómata se encuentra en un estado 𝑞 ∈ 𝑄 es:

𝑠 = 𝑔(𝑞 )

Y como este último estado fue a su vez alcanzado en una transición anterior:

𝑞 = 𝑓(𝑞 ,𝑒 )

Se puede apreciar la relación directa entre la salida actual y la anterior, que es:

𝑠 = 𝑔(𝑓(𝑞 ,𝑒 ))

Puede demostrarse que para toda máquina de Moore hay una máquina de Mealy capaz de tener
el mismo desempeño y recíprocamente. Lo primero es obvio, ya que solo basta plantear una
máquina de Mealy que en cada estado prevea la misma salida para todos los símbolos de entrada.
Lo opuesto, obtener una máquina de Moore a partir de una de Mealy, no es tan obvio y requiere
mayor esfuerzo.

24

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Autómata finito determinista (AFD)

Definición: Si a la máquina de Mealy se le incorpora un estado inicial y un conjunto de estados de

aceptación estamos en presencia de un AFD. Comienza a operar a partir de un estado inicial, tiene
una conducta traductora ya que transforma las cadenas de entrada en cadenas de salida y
completa su operación al terminar de leer su entrada arribando a un estado que podrá ser de
aceptación o no.

𝐴𝐹𝐷𝑇 = (𝛴𝐸 , 𝛴𝑆 , 𝑄, 𝑞0 , 𝐴 , 𝑓 , 𝑔)
donde:

• 𝑞 estado inicial 𝑞 ∈ 𝑄

• 𝐴 conjunto de estados de aceptación 𝐴 ⊆ 𝑄

Nótese que por tener un estado inicial y ser la cadena de entrada finita, el 𝐴𝐹𝐷 siempre
completa su operación, en una cantidad finita de tiempo, por lo tanto, determina un algoritmo.

Si el 𝐴𝐹𝐷 se limita a reconocer o validar cadenas, resultan innecesarios su alfabeto de salida y

su correspondiente función de salida, por lo que ambas pueden ser eliminadas, dando lugar al
Autómata finito reconocedor (AFDR):
𝐴𝐹𝐷𝑅 = (𝛴𝐸 , 𝑄, 𝑞0 , 𝐴, 𝑓 )
Un caso particular de aceptación ocurre cuando la cadena de entrada es la palabra vacía 𝜆, el AFD
la aceptará si su estado inicial es también un estado de aceptación 𝑞 ∈ 𝐴.

Una característica importante del componente f del AFD es que se trata de una función y esto es
lo que lleva a definir al autómata como determinista. Debe recordarse que la función es un caso
particular de relación entre dos conjuntos, en la cual se asocian elementos del primero (alcance)
con elementos únicos del segundo (rango):
𝑓 ∶ 𝑄𝑥 𝛴𝐸 → 𝑄
Formas en las que una máquina “real” reconoce haber leído completamente una cadena:
1. se conoce anticipadamente los largos de las cadenas a ser leídas.
2. Los caracteres son recibidos con una periodicidad regular
3. El mensaje termina con un carácter especial.

Configuración o descripción instantánea

Se define como configuración o descripción instantánea 𝑘 de un autómata finito en un intervalo
de tiempo t al par ordenado:

𝐾 = (𝑞, 𝛽) 𝑐𝑜𝑛: 𝑞 ∈ 𝑄, 𝛽 ∈ Σ∗𝐸

25

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

donde q representa el estado en el que se encuentra y β el sufijo o subcadena de entrada que está
pendiente de ser leída.

Se puede reconocer la configuración inicial como 𝐾 = (𝑞 , 𝛼)

La configuración de aceptación se define como: 𝐾 = (𝑞 , 𝜆)

Movimiento
El tránsito de una configuración a otra es denominado movimiento, es decir que si existe la
transición 𝑞 = 𝑓(𝑝, 𝑎 ), el movimiento del estado p al q, leyendo el símbolo de entrada a, puede
representarse:
(𝑝, 𝑎𝛽) ⊢ (𝑞, 𝛽)
El movimiento desde la configuración inicial a la final es representado:

𝑞0 𝛼 ⊢∗ (𝑞𝑛 , 𝜆)

donde ⊢∗ equivale a una cantidad finita de movimiento que es igual al largo |α| de la cadena de
entrada.
Extensión al tratamiento de palabras
La función de transición f puede ser extendida para describir lo que ocurre a partir de cada estado
si en lugar de recibir símbolos aislados se recibe una secuencia concatenada de los símbolos de
entrada.

𝑓 ∶ 𝑄𝑥 𝛴 ∗ → 𝑄

Considerando que la cadena 𝛼 = 𝑎𝑏𝑐𝑑𝑒 puede ser expresada como 𝛼 = 𝑎𝛽 con 𝛽 = 𝑏𝑐𝑑𝑒:

𝑓 (𝑞, 𝛼 ) = 𝑓 (𝑞, 𝑎𝛽 ) = 𝑓 (𝑓 (𝑞, 𝑎), 𝛽)

Se obtiene un proceso recursivo que finaliza al completarse la lectura de α, situación donde
ocurre 𝑓 (𝑞, 𝜆) = 𝑞.

Este concepto también puede aplicarse para extender la función de salida de las máquinas
secuenciales de Mealy o Moore y del autómata finito traductor.
Aceptación de palabras y lenguajes
Si en el movimiento desde la configuración inicial hasta la final, representada por
𝑞0 , 𝛼 ⊢∗ (𝑞𝑛 , 𝜆) se verifica que 𝑞 ∈ 𝐴 se dice que la cadena α ha sido reconocida o aceptada.
El AFD reconocedor llega a la conclusión de aceptar o rechazar la cadena de entrada luego de
efectuar un número finito de transiciones o movimientos a partir de su configuración inicial. Es
decir que la aceptación de una cadena por parte de un AFD requiere la completa lectura de la
cadena de entrada y el arribo a un estado de aceptación.
Se dice que un lenguaje L es aceptado por un autómata finito si todas las palaras que lo componen
conducen a estados de aceptación.

26

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Accesibilidad entre estados

En un AFD, se dice que un estado p es accesible desde otro estado q y se representa pAq si existe
una palabra de símbolos de entrada que haga transitar el autómata desde el estado q hasta el p.
𝑝𝐴𝑞 ↔ ∃𝛼 ∈ Σ ∗ ⁄𝑓 (𝑞, 𝛼) = 𝑝, 𝑐𝑜𝑛 𝑝, 𝑞 ∈ 𝑄
Autómatas conexos
Si todos los estados de un autómata son accesibles desde su estado inicial se dice que el mismo es
conexo.
Equivalencia entre estados
Dos estados p y q de un AFD se dicen que son equivalentes pEq si desde cualquiera de ellos se
aceptan y rechazan exactamente las mismas cadenas de símbolos de entrada:

𝑝𝐸𝑞 ⇔ [∀𝛼 ∈ Σ∗ : 𝑓 (𝒑, 𝛼) ∈ 𝐴 ↔ 𝑓 (𝒒, 𝛼) ∈ 𝐴]

Esta relación de equivalencia satisface las propiedades reflexiva, simétrica y transitiva en Q.

Es imposible distinguir entre dos estados equivalentes, lo que lleva a denominarlos indistinguibles.
Equivalencia de longitud “k” entre estados
Dos estados p y q de un AFD son equivalentes de longitud k, lo que se representa 𝑝𝐸𝑘 𝑞 si son
equivalentes para todas las cadenas de largo menor o igual a k.
Equivalencia entre autómatas
Dos AFD denominados 𝐴 y 𝐴 se dice que son equivalentes y se representa 𝐴 𝐸𝐴 si ambos
aceptas las mismas palabras o sentencias. Se deduce que dos AFD son equivalentes si lo son sus
estados iniciales, que son equivalentes si y solo si aceptan el mismo lenguaje: 𝐴 𝐸𝐴 ⇔
𝐿(𝐴 ) = 𝐿 (𝐴 ).
Conjunto cociente
Conjunto que tiene por elementos a todas las clases de equivalencia o subconjuntos de estados
equivalentes entre sí que puedan distinguirse en el conjunto de estados Q. Por ser la base de este
agrupamiento la relación de equivalencia entre estados E, el conjunto cociente se denota Q/E. La
definición de equivalencia entre dos estados no proporciona un procedimiento para saber si dos
estados p y q son equivalentes, ya que hay infinitas sentencias
𝛼 ∈ Σ∗ . Para superar esta dificultad, se recurre a un procedimiento práctico incremental que
comienza con un particionamiento Q que es sucesivamente revisado con cadenas
progresivamente más largas. Así, el conjunto de cociente inicial tiene dos elementos, un
subconjunto que contiene a los estados de aceptación 𝑃 y otro subconjunto con los estados
restantes 𝑃 . Los siguientes conjuntos cocientes 𝑄⁄𝐸 se definen dividiendo las clases 𝑃 de
𝑄 ∕ 𝐸 las veces que sea necesario hasta que, para todo símbolo 𝑎 ∈ Σ y para todo par de
estados p, q de las clases 𝑃 queden definidos movimientos que conduzcan a elementos de las
mismas clases 𝑄/𝐸 . Esto se repite hasta obtener 𝑄/𝐸𝑘+1 = 𝑄/𝐸 .

27

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Minimización de autómatas:

Autómata mínimo
Autómata que cumple correctamente su función con la menor cantidad posible de estados. Para
minimizar un autómata se recurre al concepto de conjunto cociente visto con anterioridad, es
decir, a la partición del conjunto de estados Q producida por la relación de equivalencia E, que
tiene por elementos a las clases de equivalencia, donde se agrupan todos los estados equivalentes
o indistinguibles entre sí.
El autómata mínimo equivalente a uno dado tendrá como estados a cada una de las partes o
clases de estados equivalentes del autómata original (es decir, su conjunto de estados será Q/E),
aquella clase que contenga el estado inicial original será su estado inicial, las que contengan algún
estado de aceptación del autómata original serán sus estados de aceptación; su función de
transición se construirá en base a la del autómata original.

Autómatas finitos bidireccionales

Aspectos generales: Otorgando al AFD la capacidad de decidir el sentido del movimiento del
cabezal en cada intervalo de tiempo queda conceptualmente definido el AFDB. En la definición del
autómata se debe incorporar una función de movimiento. Se incorporan además, dos símbolos
especiales que identifican el inicio y el final del intervalo de cinta de entrada a ser analizado.
Esto da como resultado las siguientes características:
• Cada símbolo de entrada puede ser leído varias veces
• No hay ninguna condición que identifique el fin de la lectura de la cadena
• No es posible anticipar la cantidad de intervalos de tiempo requeridos para evaluar la
cadena
• El concepto de cadena que resta de ser leída desaparece
Una consecuencia puede ser que ocurra que ciertas cadenas de entrada lleven al AFDB a un ciclo
cerrado que no conduzca a nada, es decir, un ciclo infinito.
Se definen entonces:
𝐴𝐹𝐵𝐷 = (Σ , Γ, 𝑄, 𝑞 , 𝐴, 𝑓)

Donde:

• Γ Alfabeto de cinta Γ = Σ ⋃{⊢, ⊣}

• 𝑓 Función de transición 𝑓: 𝑄𝑥Γ → 𝑄𝑥{𝐼, 𝑁, 𝐷}

Sobre la definición de AFDB nótese que:

28

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

1) El alfabeto de cinta 𝛤 se forma con el alfabeto de entrada y dos símbolos auxiliares

destinados a marcar el inicio y fin de la cinta de entrada, normalmente denominados BOT
(Beginning of tape ├) y EOT (End of tape ┤) estos símbolos nunca son de entrada.
2) El AFDB tiene normalmente un único estado de aceptación ya que al poder ser releída la
cadena siempre podrá ser definido con uno solo de estos estados.
3) La función de transición es definida usando el alfabeto ampliado 𝛤 ya que el autómata
debe reconocer todos los símbolos que pueda contener la cinta de entrada y tomar
decisiones a partir de ellos.
4) La función de transición 𝑓 reúne dos funciones, la de transición de estado a estado
𝑡: 𝑄𝑥 𝛤 → 𝑄 y la del sentido del próximo movimiento del cabezal de entrada
𝑚: 𝑄𝑥Γ → {𝐼, 𝑁, 𝐷}
5) El alfabeto de movimientos del cabezal contiene tres símbolos, izquierda (I), neutro (N) y
derecha (D).
Aceptación de cadenas
Una cadena es aceptada por el AFDB cuando éste ha alcanzado un estado de aceptación y la
cadena ha sido leída por lo menos una vez. Esto último significa que la cantidad de intervalos de
tiempo demandados por la aceptación será igual o mayor al largo de la cadena en cinta.
Configuración
Para la completa definición de la condición en la que se encuentra un AFDB en un instante dado se
requieren 3 componentes:
1. El estado actual
2. El contenido de la cinta de entrada
3. la posición del cabezal
Se adopta además la convención de que el símbolo de inicio de cinta (BOT) está en la posición 0 y
el contador se incrementa hacia la derecha.

La configuración 𝑘 de un AFDB que opera sobre cierta cadena de entrada α que en el instante de
tiempo t está en el estado q y con el cabezal en la posición k es:

𝐾 = (𝑞, ⊢ 𝛼 ⊣, 𝑘 )

Entonces, la configuración inicial será: 𝐾 = (𝑘 , ⊢ 𝛼 ⊣ ,0)

y la configuración final: 𝐾 = (𝑞 , ⊢ 𝛼 ⊣, 𝑛) 𝑑𝑜𝑛𝑑𝑒: 𝑞𝐴 ∈ 𝐴 𝑦 𝑛 = |𝛼| + 1.

Lenguaje reconocido por el AFDB

El lenguaje L que es aceptado por un autómata finito bidireccional M puede definirse en símbolos
como:

𝐿(𝑀) = {𝛼⁄𝛼 ∈ Σ∗ 𝑦 𝑞 𝛼 ⊢∗ 𝛼𝑞 , 𝑞 ∈ 𝐴}

29

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Conceptos de compiladores e intérpretes

Conceptos relacionados:
• Editor de programas
• Compilación: Se refiere al proceso de convertir un programa fuente en un programa objeto
• Intérprete: Se denomina así a una herramienta o módulo que interpreta y ejecuta las
sentencias de un programa fuente una tras otra, sin generar un programa objeto
• Preprocesador: Es un módulo que tiene la finalidad de modificar o completar al programa
fuente previo a ser leído por el compilador
• Conversor Fuente-Fuente: Tiene por finalidad la conversión de un programa fuente desde
un lenguaje de alto nivel a otro
• Ensamblador: Se denomina así a un compilador que tiene por lenguaje fuente a uno de 2 da
generación
• Administrador de librerías: Es una herramienta que permite gestionar en una librería las
partes de un sistema que han sido compiladas por separado y que están destinadas a
integrar una aplicación
• Depurador: Es un módulo usado para facilitar las pruebas y eliminar errores de los
programas
• Enlazador: Tiene la misión de construir el programa ejecutable a partir del programa objeto
• Librería de enlace dinámico: Se trata de librerías que en lugar de ser incorporadas al
programa ejecutable por el enlazador son incorporadas a la aplicación en tiempo de
ejecución cuando son necesarias.
Tipos de compiladores:
• Compilador cruzado: Es el compilador que genera programas objeto que están destinados
a ser ejecutados en computadoras diferentes de aquel en el que se lo ha compilado
• Autocompilador: Es un compilador en que su propio programa fuente está escrito en el
mismo lenguaje que el de los programas fuentes que admite
• Metacompilador: Se trata de un compilador capaz de admitir programas fuentes escritos
en diversos lenguajes.
• Decompilador: Tiene como misión convertir programas escritos en lenguaje máquina a
programas fuentes de lenguajes de alto nivel
• Compilador optimizador: Los objetivos principales son la reducción de tamaño del
programa, reducción de la demanda de memoria y la rapidez de operación.
• Compilador intérprete: Se trata de compiladores que generan los programas objeto en un
lenguaje intermedio, que luego son interpretados en el momento de la ejecución.

30

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

• Ambiente integrado de desarrollo (IDE): Son sistemas interactivos que incorporan al

compilador servicios complementarios.
Contexto del compilador:

31

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Estructura y componentes del compilador:

Análisis léxico
También se denomina análisis lineal o de exploración y el módulo destinado a esta tarea es
denominado analizador lexicográfico o scanner. En esta fase, la cadena de caracteres que
constituye el programa fuente es leída carácter a carácter, para identificar y agrupar sus
componentes léxicos. Éstos, son secuencias de caracteres que tienen un significado colectivo
denominados tokens. Luego, una cadena de caracteres específica que se ajuste al patrón léxico de
un cierto tipo de token es denominada lexema.
Análisis sintáctico
Se reciben las secuencias de componentes léxicos que fueron identificadas en la fase anterior para
comprobar que las sentencias sean sintácticamente correctas. Es decir, se debe verificar que todas
las sentencias pueden haber sido generadas por la gramática del lenguaje fuente. Los lenguajes de
programación son generados por gramáticas libres de contexto, y éstos son reconocidos por los
autómatas con pila, por ende, todo analizador sintáctico tiene una capacidad computacional
equivalente a la de un autómata con pila.

32

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Análisis semántico
Se revisa al programa fuente, para reunir información sobre los tipos de las variables que será
utilizada en la fase posterior de generación de código intermedio. Incluyen la detección y
comunicación de numerosos errores que corresponden a comprobación de tipos, coherencia en
los argumentos, potenciales errores en tiempo de ejecución, etc.
Generación de código intermedio
Prepara al programa fuente para ser convertido en un nuevo programa escrito en un lenguaje
elemental que es normalmente denominado lenguaje intermedio. La tendencia fue adoptar un
lenguaje universal denominado Uncol (Universal Compiler Oriented Language).
Optimización de código
Esta fase realiza una mejora en la calidad y eficiencia del código intermedio, pero difícilmente
permita alcanzar un código óptimo. Las mejoras refieren a la calidad de la implementación del
programa desde un punto de vista lógico, mejoras particulares para el mejor aprovechamiento
global de cierta máquina, direccionamientos, etc.
Generación del programa objeto
Se toma como entrada a la representación intermedia y se produce un programa objeto
equivalente que debe ser correcto, eficiente, apropiado a la máquina en la que se va a operar y
apto para dar lugar a un ejecutable compatible con el entorno (SO). Se encarga de la selección de
instrucciones de máquina de destino, asignación de registros de memoria y otros recursos,
administración de la memoria para datos y programa.
Gestor de la tabla de símbolos
Es en realidad un administrador de una base de datos que contiene los identificadores del
programa fuente y sus atributos.
Identificación y gestión de errores
El gestor de errores, activo en las fases de análisis, detecta los errores, los asocia a determinada
línea del programa fuente e intenta su recuperación con la finalidad de proseguir con la terea de
compilación. Para esta última tarea, el registrador dispone de un corrector lexicográfico, un
corrector sintáctico, y un corrector semántico que operan según la fase en la que fue reportada la
irregularidad.

Errores de programación
Se clasifican en lexicográficos, sintácticos, semánticos, por falla del compilador y de ejecución.
Las primeras tres clases de errores están al alcance de ser identificadas por las fases
correspondientes de la etapa de análisis del compilador, formando parte de lo que se denomina
evaluación estática. La última clase requiere la ejecución del programa y será más efectiva en la
medida en que estén mejor planeados los casos de prueba, ya que deberían procurarse recrear
todas las secuencias lógicas presentes. Esto se llama evaluación dinámica.

33

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

La verificación dinámica permite identificar la presencia de errores, pero nunca asegurar la

ausencia de ellos.
Las posibles reacciones del compilador frente a la detección de un error en el código fuente
depende del tipo de compilador:
a) Genera el programa objeto sin advertir el error
b) Detecta el primer error, lo señala y suspende la operación
c) Detecta un error e intenta sin éxito su recuperación, para ingresar en un lazo infinito o
terminar el proceso anticipadamente
d) A partir del primer error, suspende la generación del código objeto, pero continúa el
análisis y la búsqueda de otros posibles errores
e) Detecta un error y lo recupera con éxito, para seguir la compilación y procurar completar
normalmente la generación del programa objeto
Errores lexicográficos
Identificados en la fase de análisis lexicográfico:
a) Presencia de un símbolo terminal pero que no puede formar parte de la cadena que está
siendo reconocida.
b) Comentarios incorrectamente delimitados.
c) Errores en palabras reservadas por omisión o ubicación incorrecta de caracteres.
d) Componente léxico truncado.
Errores sintácticos
Se originan por el incumplimiento de las reglas de producción de la gramática:
a) Cadenas de paréntesis o corchetes que no están balanceados o están incorrectamente
ubicados
b) Cadenas no permitidas en estructuras sintácticas como consecuencia de la ausencia de
operadores u operandos
c) Estructuras sintácticas alteradas por exceso o ausencia de delimitadores o separadores
d) Palabras reservadas mal formadas o usadas indebidamente
e) Bloques indebidamente delimitados por estar mal balanceados
Errores semánticos
Detectados en la fase de análisis semántico:
a) Identificadores no declarados
b) Declaraciones múltiples de un mismo identificador
c) Incompatibilidad de tipos de operadores y operandos

34

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

d) Incompatibilidad de tipos entre argumentos formales y reales en subprogramas

e) Límites inválidos en instrucciones de control de flujo
f) Errores potenciales en tiempo de ejecución
Fallas en el compilador
Se trata de errores que se presentan en tiempo de compilación, pero no tienen que ver con los
defectos del programa fuente sino con haber excedido ciertos límites referidos a la capacidad del
compilador:
a) Tamaño máximo de la tabla de símbolos
b) Límite de cantidad de bloques en un programa
c) Límite en el número de anidamientos en ejecuciones repetidas
d) Encadenamiento de llamadas a funciones
e) Límite en el tamaño de las pilas en el análisis sintáctico o semánticos
Errores de ejecución
Los errores de ejecución tienen su origen en acciones equivocadas u omisiones del programador al
momento de escribir el programa fuente y responden a alguna de las siguientes causas:
a) Error de lógica (por ejemplo, ingresar a un bucle infinito)
b) Inaccesibilidad de periféricos de E/S (por ejemplo, intentar accesar a archivos protegidos)
c) Errores en el código (por ejemplo, nombre de variables cambiadas)
d) Imprevisiones (por ejemplo, ausencia de verificaciones de datos a ingresar)

35

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Unidad 4: Autómatas finitos no deterministas

AFND
Los AFND quedan definidos como una quíntupla:
AFND = (Σ , Q, q , A, f)
Y su característica distintiva está en la definición de las transiciones, que aquí no es más una
función de estado a estado, sino una relación de transición, tomando la forma:
f: QxΣ → P(Q)
Donde P(Q) es el conjunto de todos los subconjuntos que se pueden formar con los elementos del
conjunto Q (conjunto potencia de Q).
Esta indeterminación, no significa incertidumbre o aleatoriedad en el desempeño final del
autómata. Más bien significa incertidumbre en cuanto al esfuerzo requerido al evaluar una cierta
cadena. Esto es así porque la operación del autómata implica una búsqueda exhaustiva en un
árbol de posibilidades que será más frondoso según sea mayor la cantidad de próximos estados
posibles en cada transición, llamada factor de ramificación F , donde F = |f(q, e)| donde
q ∈ Q, e ∈ Σ . El tiempo para resolver este tipo de problemas es exponencial.
La flexibilidad que ofrece el no determinismo es de gran ayuda en el diseño de autómatas
destinados a reconocer lenguajes complejos. Se obtienen diseños más simples a costa de
algoritmos menos eficientes.

Transiciones 𝛌
La definición de los AFND puede ampliarse para incluir transiciones de un estado a otro que no
dependan de ninguna entrada, las que son denominadas transiciones λ.
Para contemplarlas se incorpora una columna adicional a la relación f a fin de considerar los pares
(q,λ) y se asume además que cada estado tiene su propia transición λ que cicla sobre sí mismo.
Luego la expresión de f debe ser reescrita de manera de adicionar λ a los símbolos del alfabeto de
entrada:
f: Qx(Σ ∪ λ) → P(Q)
A todos los pares de estados que están vinculados por una transición λ es conveniente reunirlos en
un conjunto T denominado relación de transición λ. Por lo ya anticipado, en esta relación, se
incluyen además las transiciones de los estados con ellos mismos, reconociéndose el carácter
reflexivo de T:
T = (p, q)/q ∈ f(q, λ) ∪ (q, q)/q ∈ Q

Luego se incorpora al conjunto T nuevos pares ordenados, que se originan en la aplicación de la

propiedad transitiva a los pares anteriores:

36

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

T ∗ = T ∪ {(p, q)/pTr ∧ rTq}

Extensión al tratamiento de palabras

Si en vez de recibir símbolos aislados recibimos una secuencia concatenada la función de
transición puede ser extendida a:
𝑓 = 𝑄𝑥 (Σ ∪ {𝜆})∗ → 𝑃(𝑄)

Equivalencia con autómatas finitos deterministas

Teorema 1:
Todo AFND- 𝜆 puede ser redefinido como un AFND equivalente y para ellos se deben eliminar sus
transiciones 𝜆. Se procede a redefinir el conjunto de estados de aceptación A’ y la función de
transición a f’, mediante los siguientes pasos:
a. Para todo par de estados distintos relacionados por transiciones 𝜆
(𝑝𝑇 ∗ 𝑞, 𝑝 ≠ 𝑞) y para cada transicón 𝑟 = 𝑓(𝑞, 𝑒) donde 𝑒 ≠ 𝜆, es decir,
𝑟 = 𝑓(𝑓 (𝑝, 𝜆∗ ), 𝑒) se define una nueva transición 𝑟 = 𝑓(𝑝, 𝑒). Se incorporan las nuevas
transiciones a f.
b. Para todo par de estados distintos relacionados por transiciones 𝜆 (𝑞𝑇 ∗ 𝑟, 𝑞 ≠ 𝑟) y para
cada 𝑞 = 𝑓(𝑝, 𝑒) donde 𝑒 ≠ 𝜆, es decir 𝑟 = 𝑓(𝑓(𝑝, 𝑒), 𝜆∗ ), se define la nueva transición
𝑟 = 𝑓(𝑝, 𝑒). Se incorporan las nuevas transiciones en f.
c. En caso de existir una transición lambda desde el estado inicial a un estado de aceptación
(𝑞 𝑇 ∗ 𝑟, 𝑟 ∈ 𝐴) hacer 𝑞 ∈ 𝐴.
d. Eliminar todas las transiciones 𝜆, lo que implica eliminar la columna 𝜆 de la tabla de f.
Teorema 2:
Por cada AFND siempre existe un AFD que acepta el mismo lenguaje y estos dos autómatas se dice
que son equivalentes.
a. Reconocer el estado inicial 𝐶 = {𝑞 }
b. Definir los nuevos estados 𝐶 = 𝑓 (𝐶 , 𝑒) para todo 𝑒 ∈ Σ 𝑦 𝑘 < 𝑖.
c. Para todos los casos en que 𝐶 = { … , 𝑞 , … } 𝑦 𝑞 ∈ 𝐴 se reconoce que 𝐶 ∈ 𝐴 .

37

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Gramáticas regulares y autómatas finitos

Definición de gramática regular a partir de AFD
El autómata debe ser un AFD, y la gramática debe ser bien formada y regular por derecha.
Dado 𝐴𝐹𝐷 = (Σ , 𝑄, 𝑞 , 𝐴, 𝑓)
𝐺𝑅 = (Σ, 𝑄, 𝑆, 𝑃)
𝐹 = 𝑃 = { 𝑋 ≔ 𝑎𝑌 ⁄𝑓 (𝑋, 𝑎) = 𝑌} ∪ { 𝑋 ≔ 𝑎⁄𝑓(𝑋, 𝑎) = 𝑌, 𝑌 ∈ 𝐴}
Y se agrega 𝑞 ∶= 𝜆 𝑠𝑖 𝑞 ∈ 𝐴 ; 𝑋, 𝑌, 𝑞 ∈ 𝑄, 𝑎 ∈ Σ, 𝐴 ⊆ 𝑄 .

Definición de autómatas a partir de gramáticas regulares

Dado: 𝐺 = (Σ , Σ , 𝑆, 𝑃)
𝐴𝐹 = (Σ , Σ ∪ {𝐴}, 𝑆, {𝐴}, 𝑓)
Donde A es un nuevo símbolo que no estaba en Σ y 𝑓 (𝑋, 𝑎) = 𝑌 𝑠𝑖 𝑋 ≔ 𝑎𝑌 está en P y
𝑓(𝑋, 𝑎) = 𝐴 𝑠𝑖 𝑋 ≔ 𝑎 está en P, con𝑋, 𝑌, 𝑆 ∈ Σ 𝑎 ∈ Σ .
La regla de producción 𝑆 ≔ 𝜆 incorpora la transición 𝑓(𝑆, 𝜆) = 𝐴.

Conversión de gramática lineal por izquierda a lineal por derecha

Paso 1: Convertir la gramática dada a otra equivalente que no sea recursiva en el axioma. Para
ello, se debe incorporar un nuevo símbolo no terminal B y modificar las reglas de producción
según se describe:
 Por cada regla 𝑆 ≔ 𝛼, se crea una nueva regla 𝐵 ≔ 𝛼.
 Cada regla de la forma 𝐴 ≔ 𝑆𝑎 debe ser reemplazada por 𝐴 ≔ 𝐵𝑎 donde 𝑆, 𝐴, 𝐵 ∈ Σ , 𝑎 ∈
Σ 𝑦 𝛼 es una cadena válida.
Paso 2: Se debe construir un grafo con las siguientes instrucciones:
 Los nodos del grafo se identifican con los símbolos no terminales de la gramática y se incluye
un nodo adicional identificado con 𝜆.
 Por cada regla de la forma 𝐴 ≔ 𝐵𝑎 se dibuja un arco desde el nodo A al nodo B que es
identificado con la etiqueta 𝑎.
 Por cada regla de la forma 𝐴 ≔ 𝑎, se incluye un arco desde el nodo A al nodo 𝜆 identificado
con 𝑎.
 Para la regla 𝑆 ≔ 𝜆 se incorpora un arco sin etiqueta desde el nodo S al nodo 𝜆.
Paso 3: Se construye un nuevo grafo a partir del grafo anterior según se indica:
 Se intercambian los identificadores de los nodos S y 𝜆
 Se cambia el sentido de todos los arcos

38

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Paso 4: A partir del nuevo grafo, se obtiene la gramática lineal por derecha siguiendo los siguientes
pasos:
 Los alfabetos de símbolos terminales y no terminales son los mismos de la gramática original
lineal por izquierda
 Por cada arco dirigido etiquetado con 𝑎 desde el nodo B al nodo A, se incorpora a la nueva
gramática la regla de producción 𝐵 ≔ 𝑎𝐴
 Por cada arco dirigido etiquetado con 𝑎 desde el nodo B al nodo 𝜆, se incorpora la regla de
producción 𝐵 ≔ 𝑎
 En caso de un arco sin etiqueta desde el nodo S al nodo 𝜆, se incorpora a la gramática la regla
𝑆≔𝜆

Expresiones regulares y autómatas finitos

Método o algoritmo de Thompson:

El método que se presenta traduce cada parte de la definición de una expresión regular en un
autómata que acepta el mismo lenguaje denotado por ella, de tal forma que el autómata finito
quede definido al analizar la expresión parte por parte.
a. Para ∅ :

b. Para 𝜆:

c. Para 𝑎 ∈ Σ :

d. El lenguaje unión L€ y L(F) denotado por la expresión regular E+F, será reconocido por el
autómata construido de la siguiente forma:
- Quitar la característica de inicial de los estados iniciales de 𝐴𝐹 𝑦 𝐴𝐹
- Crear un nuevo estado inicial 𝑞 y relacionarlo mediante transiciones 𝜆 con antiguos
estados iniciales 𝐴𝐹 y 𝐴𝐹
- Quitar característica de aceptación.
- Crear nuevo estado de aceptación 𝑞 y agregar desde cada antiguo estado de
aceptación de 𝐴𝐹 𝑦 𝐴𝐹 una transición 𝜆 hacia él.

39

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

e. De forma análoga (pero en vez de paralelo, en serie) podemos reconocer E.F:

f. Finalmente, para la estrella de Kleene de una expresión regular 𝐸 ∗ , que representa al

lenguaje [𝐿(𝐸)]∗ , se construye el siguiente autómata finito.

40

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Unidad 5: Autómatas con pila

Definición del AP

El AP queda definido como la séptupla:

𝐴𝑃 = (Σ , Γ, 𝑄, 𝑞 , #, 𝐴, 𝑓)
Donde:
Γ: es el alfabeto de símbolos de pila
#: Símbolo de referencia de pila, # ∈ Γ, # ∉ Σ

En el caso de un AP no determinista (APND):

𝑓: 𝑄𝑥(Σ ∪ {𝜆})𝑥 Γ → 𝑃(𝑄𝑥Γ ∗ )
Para AP deterministas se presentan dos posibles funciones de transición:
𝑓: 𝑄 𝑥 Σ 𝑥 Γ → 𝑄 𝑥 Γ ∗
𝑓: 𝑄 𝑥 (Σ ∪ {𝜆})𝑥 Γ → 𝑄 𝑥 Γ ∗

Concepto de configuración o descripción instantánea

𝑘 = (𝑞, 𝛽, 𝛿)
Donde q representa el estado en el que se encuentra, 𝛽 la subcadena de entrada pendiente de ser
leída y 𝛿 el contenido de la pila.
Configuración inicial: 𝑘 = (𝑞 , 𝛼, #)
Configuración final: 𝑘 = (𝑞, 𝜆, 𝛿)
El tránsito de una configuración a otra es también aquí denominado movimiento:
(𝑝, 𝑎𝛽, 𝛿𝑏 ) ⊢ (𝑞, 𝛽, 𝛿𝑏𝑏)
El movimiento de configuración inicial a la final es:
(𝑞 , 𝛼, #) ⊢∗ (𝑞, 𝜆, 𝛿)

Aceptación de lenguajes
a. Aceptación por vaciado de pila:
𝐿 = {𝛼⁄(𝑞 , 𝛼, #) ⊢∗ (𝑞, 𝜆, #) 𝑐𝑜𝑛 𝑞 , 𝑞 ∈ 𝑄, 𝛼 ∈ Σ∗ , # ∈ Γ}
b. Aceptación por estado final:

41

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

𝐿 = {𝛼⁄(𝑞 , 𝛼, #) ⊢∗ (𝑞, 𝜆, 𝛿) 𝑐𝑜𝑛 𝑞 ∈ 𝑄, 𝑞 ∈ 𝐴, 𝛼 ∈ Σ∗ , 𝛿 ∈ Γ , # ∈ Γ}

c. Aceptación por vaciado de pila y estado final:

𝐿 = {𝛼⁄(𝑞 , 𝛼, #) ⊢∗ (𝑞, 𝜆, #) 𝑐𝑜𝑛 𝑞 , 𝑞 ∈ 𝑄, 𝑞 ∈ 𝐴, 𝛼 ∈ Σ ∗ , # ∈ Γ}

No equivalencia entre los APD y APND

Los autómatas con pila no deterministas no tienen necesariamente autómatas con pila
deterministas equivalentes que acepten los mismos lenguajes. Esta falta de equivalencia no
significa que no pueda existir un autómata con pila determinista que acepte una cadena específica
del lenguaje, pero se trataría de una equivalencia muy restringida que carecería de generalidad.

AP deterministas y transiciones 𝝀
Una vez que el AP ha completado la lectura de una sentencia, debe verificarse que la pila se
encuentra vacía y la única forma es leerla y comprobar que el símbolo leído es precisamente la
marca de fondo de pila (#). Por esta razón, cuando los autómatas han completado la lectura de la
cadena de entrada, realizan un movimiento adicional que está destinado a verificar la condición de
la pila, y en caso de estar vacía, transitar al estado de aceptación. Aquí la cadena de entrada ya ha
sido leída y esta lectura adicional de la pila se representa como una transición 𝜆.
Es importante advertir que, pese a la transición 𝜆, esto por sí solo no define al AP como no
determinista. En efecto, si se completó la lectura de la sentencia de entrada con el autómata en
un cierto estado q, el AP será determinista siempre que:
| 𝑓(𝑞, 𝜆, #)| = 1 𝑦 𝑓(𝑞, 𝑎, #) = ∅ para todo símbolo 𝑎 ∈ Σ
Y será considerado no determinista cuando:
𝑓(𝑞, 𝜆, #) ≠ ∅ 𝑦 𝑓(𝑞, 𝑎, #) ≠ ∅ para algún símbolo 𝑎 ∈ Σ

Autómatas con pila asociados a una gramática

En el caso de las gramáticas independientes del contexto, estos autómatas llevan el nombre de
analizadores sintácticos.
La denominación de “compiler-compiler” proviene del hecho que los generadores de analizadores
tienen por finalidad la construcción de analizadores sintácticos, los que a su vez forman parte de la
etapa de análisis de los compiladores. Esta etapa incluye las fases de análisis léxico, destinado a
identificar los componentes del lenguaje, análisis sintáctico, que verifica que la estructura
corresponda a las reglas de reescritura de la gramática, y finalmente la fase de análisis semántico
que se ocupa del sentido y contenido lógico de las sentencias.
(Ampliar con lectura del libro)

42

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Analizadores sintácticos descendentes (ASD)

Dada la gramática 𝐺 = (Σ , Σ , 𝑆, 𝑃), el autómata con pila no determinista se define como:
𝐴𝑃 = (Σ , Σ ∪ Σ ∪ {#}, {𝑝, 𝑞, 𝑟}, 𝑝, #, {𝑟}, 𝑓)
Características:
a. En inglés Top-Down Parser.
b. LL (left – left).
c. Lee la cadena de izquierda a derecha.
d. Deriva por izquierda.
e. APND: se parte desde el axioma, se aplican las reglas de producción, se desapilan los
terminales.

Analizadores sintácticos ascendentes

Dada la gramática 𝐺 = (Σ , Σ , 𝑆, 𝑃), el autómata con pila no determinista se define como:
𝐴𝑃 = (Σ , Σ ∪ Σ ∪ {#}, {𝑝, 𝑞}, 𝑝, #, {𝑞}, 𝑓 )
Características:
a. En inglés Bottom-Up Parser.
b. LR (Left - Right).
c. Lee de izquierda a derecha.
d. Derivo por derecha.
e. APND: se apilan los terminales, se desapilan las reglas de producción, terminando por
desapilar el axioma.

43

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Analizadores sintácticos con preanálisis

Sabemos que un árbol con elevado factor de ramificación impacta en la eficiencia del proceso.
Para superar esta limitación se utiliza la técnica llamada preanálisis, que implica conocer
anticipadamente los próximos k símbolos a ser leídos por el autómata. En base a este
conocimiento, el AP selecciona su próximo movimiento, pudiendo predecir cuál de todas las
posibles producciones aplicables es la que conducirá a la aceptación. Se da lugar a los analizadores
sintácticos predictivos, de los cuales los más conocidos son los siguientes:
a. ASD LLK
Proceso de descenso recursivo (AF).
La gramática debe ser: - No ambigua
- Sin recursión por izquierda
- Factorizado por izquierda
b. ASA LRK
Los más importantes son:
LR(0): No utiliza preanálisis. Fácil de implementar. Menor poder de reconocimiento.
SLR(1): Utiliza un solo símbolo de preanálisis.
LR(1): ASA LR clásico que utiliza un símbolo de preanálisis.
LALR(1): Combina el LR(1) con SLR(1).

44

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Unidad 6: Autómata linealmente acotado y máquina de Turing

Definiciones
El autómata linealmente acotado (ALA) queda definido como:
𝐴𝐿𝐴 = (Σ , Γ, 𝑄, 𝑞 , 𝐴, 𝑓)
Donde:
Γ: Alfabeto de cinta Γ = Σ ∪ {⊢, ⊣} ∪ Ω
𝑓: Función de transición, 𝑓: 𝑄𝑥 Γ → 𝑄 𝑥 Γ 𝑥 {𝐼, 𝑁, 𝐷, 𝑃}
El alfabeto de cinta Γ fue ampliado con símbolos auxiliares Ω y la otra variante está en la función
de transición, que debe incorporar las previsiones para efectuar la grabación de un símbolo sobre
la cinta en cada intervalo de tiempo. Nótese que no se trata más de una cinta de entrada sino más
bien de una cinta de trabajo o medio de entrada/salida, de largo igual al de la cadena a ser
procesada.
Esto significa que la llamada función de transición encierra ahora en realidad tres funciones: la de
transiciones entre estados (𝑓 ), la de movimientos del cabezal (𝑓 ) y una nueva que es la función
de salida (𝑓 ):
𝑝 = 𝑓 (𝑞, 𝑎)
𝑚 = 𝑓 (𝑞, 𝑎)
𝑏 = 𝑓 (𝑞, 𝑎)
𝑠𝑖𝑒𝑛𝑑𝑜 𝑝, 𝑞 ∈ 𝑄, 𝑎, 𝑏 ∈ Γ, 𝑚 ∈ {𝐼, 𝑁, 𝐷, 𝑃}
Ahora bien, si se permite a la cinta extenderse más allá de la cadena a ser procesada, es necesario
eliminar las marcas que la limitan. En este caso, se debe definir un símbolo que por defecto
ocupará el resto del medio de entrada/salida y usualmente se utiliza para este fin el b (blanco). La
ausencia de límites implica que este medio se extiende ahora hasta el infinito, conformando una
enorme área de trabajo o memoria auxiliar. Con esta muy importante variante, el autómata
linealmente acotado se convierte en una Máquina de Turing:
𝑀𝑇 = (Σ , Γ, 𝑄, 𝑞 , 𝐴, 𝑓, b)
En la máquina de Turing se incluye el símbolo b, que por defecto ocupa el resto de la cinta no
utilizada. El alfabeto de cinta de la MT es entonces:
Γ = Σ ∪ Ω ∪ {b}
La función de transición de la MT será igual a la del ALA:
𝑓: 𝑄𝑥 Γ → 𝑄 𝑥 Γ 𝑥 {𝐼, 𝑁, 𝐷, 𝑃}

45

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Configuración instantánea de ALA y MT

La configuración o descripción instantánea del ALA y de MT tienen los mismos componentes, con
la salvedad de que, al poder grabar sobre la cinta, alteran progresivamente la cadena de entrada
en cada transición, convirtiéndola en sucesivas cadenas 𝛽 . En el caso del ALA, las cadenas 𝛽
mantienen la misma longitud y su configuración queda definida como:
𝑘 = (𝑞, ⊢ 𝛽 ⊣, 𝑘) ; |𝛽 | = 𝑐𝑡𝑒.
Y en el caso de la MT:
𝑘 = (𝑞, 𝛽 , 𝑘) ; 𝛽 ≠ 𝑐𝑡𝑒.

Interpretaciones del ALA y MT

Máquina reconocedora de lenguajes
Un lenguaje L definido sobre el alfabeto Σ , es reconocido por un ALA o MT si:
𝐿 = {𝛼 ⁄(𝑞 , 𝛼, 1) ⊢∗ (𝑞 , 𝛽, 𝑘), 𝑞 ∈ 𝑄, 𝑞 ∈ 𝐴, 𝛼 ∈ Σ∗ , 𝛽 ∈ Γ }
Si el estado final alcanzado al detenerse no es de aceptación, es decir 𝑞 ∉ 𝐴, significa que la
máquina M ha rechazado la cadena 𝛼. Puede también darse el caso que la máquina no se detenga
con 𝛼, entonces se dirá que M es indiferente a 𝛼, ya que ni la acepta ni la rechaza. En esta última
condición, la acción de M no determina un algoritmo.

Máquina ejecutora de procedimientos

A partir de una cantidad finita de movimientos, convertirán la cadena inicial 𝛼 en otra cadena final
𝛽 que cumplirá ciertas condiciones. Se trata de máquinas que pueden caracterizarse como
traductoras, por establecer una relación entre entrada y salida. Para una MT:
(𝑞 , 𝛼, 1) ⊢∗ 𝑞 , 𝛽, 𝑘 𝑑𝑜𝑛𝑑𝑒 𝑞 , 𝑞 ∈ 𝑄, 𝛼 ∈ Σ ∗ , 𝛽 ∈ Γ

Hay situaciones en las que el objetivo es el propio proceso y no una cierta cadena final 𝛽,
tratándose muchas veces de casos en que la máquina cumple infinitas veces un mismo ciclo. En
estos casos, interesa la sucesión de estados que recorre reiteradamente el autómata, ya que los
mismos suelen estar asociados a condiciones de control. Es decir que la salida del autómata no
está representada por la cadena final 𝛽 sino por la sucesión de los estados alcanzados en un cierto
orden:
(𝑝, 𝛼, 1) ⊢ … [𝑝, 𝑞, 𝑟, 𝑠, 𝑡] 𝑑𝑜𝑛𝑑𝑒 𝑝, 𝑞, 𝑟, 𝑠, 𝑡 ∈ 𝑄, 𝛼 ∈ Σ∗

46

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Máquina de Turing modular

El concepto de máquina modular se refiere a la construcción de autómatas mayores a partir de
aislar y asignar sus funciones principales a máquinas individuales específicas, que luego son
incorporadas a la principal. Esto es, en especial, aplicable a la máquina de Turing ya que se ve
facilitado por la disponibilidad de una cinta de E/S infinita.

Máquina de Turing no determinista

En el caso que exista para al menos un par (estado, símbolo leído) más de una terna (próximo
estado, símbolo grabado, movimiento del cabezal), se está ante una MTND. En este caso, la
relación de transición es definida:
𝑓: 𝑄 𝑥 Γ → 𝑃(𝑄 𝑥 Γ 𝑥 {𝐼, 𝑁, 𝐷, 𝑃})
Toda MTND podrá ser representada por una MT determinista equivalente, mientras que una MT
determinista debe explorar un árbol de opciones computacionales para alcanzar el mismo fin. En
no determinismo puede quedar justificado en la necesidad de simplificar y facilitar la
interpretación de la máquina.

Variantes de la Máquina de Turing

Combinación de máquinas de Turing

Se trata de plantear máquinas independientes que compartan una misma cinta con el fin de
operar en forma sucesiva sobre la misma cadena. Cada MT tiene un fin específico y opera a partir
de la cadena dejada por la máquina que trabajó con anterioridad, hasta que la última MT en la
secuencia alcance su estado de aceptación.

Máquina Universal de Turing

Se denomina así a una MT que recibe en su cinta una descripción codificada de otra máquina de
Turing y produce como resultado de su ejecución, el mismo resultado que produciría la MT
descripta en la cinta.
Esta máquina recibe el nombre de universal por ser capaz de simular el comportamiento de
cualquier otra máquina de Turing y fue propuesta por el mismo Alan Turing en 1936.

Máquina de Turing generalizada

Para generalizar la MT, se incorpora más “hardware” a su versión original. En particular, se diseña
esta nueva máquina con un número arbitrario (pero finito) de cintas de entrada/salida que, a su
vez, pueden tener múltiples cabezales de lectura/escritura.

47

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Complejidad de la MT
Concepto
Se asocia el concepto de complejidad con los recursos de cómputo requeridos para resolver un
problema.
El foco de la teoría de la computabilidad (TC) está en la existencia o no de procedimientos que
permitan resolver cierto problema.
La teoría de la complejidad computacional (TCC) es la que se ocupa del esfuerzo asociado para
completar ese cómputo.
El concepto de complejidad no parece ser cuantificable o medible, sino más bien subjetivo.
Medidas de la complejidad
Una de las primeras medidas de complejidad para MT fue la propuesta por Shannon:
Teorema 1 de Shannon: Cualquier MT con “m” símbolos y “n” estados puede ser simulada por otra
MT con 2 estados y 4mn+m símbolos. En particular existe una MT universal de solo dos estados.
Además, toda MT universal necesita al menos dos estados.
Teorema 2 de Shannon: Cualquier MT con “m” símbolos y “n” estados puede ser simulada por otra
MT con exactamente dos símbolos y menos de 8mn estados.

La complejidad estructural propuesta por Shannon no conduce a la determinación de la

complejidad operativa de la máquina, por lo cual se propuso como alternativa el tiempo y el
espacio como los indicadores más representativos de la complejidad de los problemas.
El indicador tiempo es el tiempo que se demanda en completar una computación. Es definido
como “complejidad temporal T(n)”.
El indicador espacio, es la cantidad de espacio de almacenamiento requerido para resolver el
cómputo. Se define como “complejidad espacial E(n)”.
Las expresiones que relacionan las complejidades temporales y espaciales de las soluciones con el
tamaño de los datos n, son:
a. Expresión polinomial: 𝐴𝑛 + 𝐵𝑛 + 𝐶𝑛 + 𝐷𝑛 + 𝐸 = 𝑂(𝑛 )
b. Expresión exponencial: 𝐴2 + 𝐵 = 𝑂(2 )
c. Expresión logarítmica: 𝐴 log(𝑛) + 𝐵 = 𝑂(log 𝑛 )

Clases de problemas
Clase P: Incluye los problemas que pueden ser resueltos en tiempo polinómico por una MTD. Los
problemas de complejidad temporal polinómica sin denominados tratables.
Clase NP: Incluye los problemas que pueden ser resueltos por una MTND en tiempo polinómico, lo
que en la práctica conduce en general a una complejidad exponencial. Estos problemas son
denominados intratables.

48

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Unidad 7: Simuladores de máquinas abstractas

Especificación de requerimientos de un SMA

Requerimientos funcionales de un SMA
1) Definir los dominios de operación, representados por el alfabeto de entrada, alfabeto de cinta,
alfabeto de pila y alfabeto de estados según sea el tipo de máquina.
2) Editar, almacenar y recuperar la función de transición, que será definida como una tabla.
3) Definir las condiciones iniciales de operación, que incluyen la cadena de entrada, el estado
inicial, los estados finales y las posiciones de cabezales de lectura/escritura en caso de que
correspondan.
4) Verificar la consistencia entre los dominios de operación, la función de transición y las
condiciones iniciales de operación.
5) Ejecutar, a partir de la configuración inicial, los movimientos necesarios hasta alcanzar una
configuración final, que podrá ser de aceptación o rechazo.
6) Admitir dos modos de operación: 1. Completa: que cumplirá todos los movimientos necesarios
desde la configuración inicial a la final; 2. Paso a paso: donde cada paso implica la ejecución de un
solo movimiento y es activado mediante un comando del sistema.
7) Determinar métricas o indicadores de operación, complejidad y/o eficiencia con el fin de
facilitar la evaluación del desempeño de las máquinas y las comparaciones entre ellas.

Requerimientos no funcionales de un SMA

1) Portabilidad: El programa debe ser cross-plataform.
2) Facilidad de uso: La operación del SMA debe ser simple, amigable y natural. En lo posible con
una ventana de ayuda.
3) Robustez: El SMA debe estar preparado para reconocer el ingreso de datos incorrectos, lo cual
dará lugar a advertencias del caso y la no autorización del inicio del proceso de simulación. Se
debe asegurar que estos errores no serán nunca causa de fallo. También se debe detectar la
eventualidad de la repetición de una misma configuración, que sería un indicador de haber
entrado en un ciclo infinito.
4) Eficiencia: Se trata de un requerimiento esencial de los procesos de simulación que involucran
cálculo numérico intensivo, lo cual no es el caso de los SMA, sin embargo, la eficiencia debe ser
considerada en el caso de la simulación de autómatas no deterministas con elevado factor de
ramificación en sus árboles de descripciones instantáneas. La eficiencia también abarca a las
actividades auxiliares como son la definición de los dominios y condiciones de operación.

49

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Interfaz gráfica (GUI)

1) Facilidad para la edición de dominios, función de transición y condiciones iniciales de operación.
2) Representación de los componentes formales del autómata a lo largo de todo el proceso de
simulación.
3) Representación de la configuración del autómata en cada intervalo de tiempo.
4) Opción de Debugging que permita alterar el contenido de la cinta de entrada o entrada/salida
según el caso durante la operación del autómata.
5) Representación de un histórico de los sucesivos movimientos desde la configuración inicial a la
final.
6) Representación gráfica del árbol de configuraciones o descripciones instantáneas.
7) Opción para la visualización de los indicadores de operación

Arquitectura de los simuladores

Editor
Está destinado a la carga y actualización de dominios, función de transición y condiciones iniciales
de operación (requerimientos funcionales a, b, c, y d; requerimientos no funcionales a, b, c, y d;
finalmente requerimientos de interfaz gráfica a).
Generador de movimientos
Representa el núcleo operativo del sistema, su misión es ejecutar los movimientos de las
máquinas de estados y hacer las actualizaciones en la configuración según corresponda a cada tipo
de autómata (requerimientos funcionales e, f, y g; requerimientos no funcionales a, c, y d).
Gestor de representación
Tiene a cargo la interfaz gráfica con el usuario durante la operación de la máquina abstracta,
mostrar su evolución y poner a su disposición los comandos que puedan corresponder en cada
caso (requerimientos no funcionales a y b; requerimientos de interfaz gráfica b, c, d, e, f y g).

50

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Unidad 8: Introducción a la semántica de lenguajes

Aspectos generales
La gramática se ocupa del análisis de las estructuras de las frases, y dentro de la gramática, la
morfología analiza las formas que toman las palabras, la sintaxis se ocupa de cómo combinar las
palabras para formar frases correctas y la fonética trata al lenguaje hablado.
Por su parte, la semántica se ocupa del estudio del significado que es atribuible a expresiones
sintácticamente bien formadas.

Conceptos de semántica de lenguajes

Se entiende por semántica de un lenguaje, al conjunto de reglas que especifican el significado de
toda sentencia sintácticamente correcta, escrita en el mismo. En el caso de los lenguajes de
programación, existen dos formas básicas que permiten describir sus contenidos semánticos: la
especificación natural y la especificación formal.
La especificación natural se basa precisamente en utilizar el lenguaje natural para definir las
características semánticas que no sean deducibles de la gramática que describe sintácticamente el
lenguaje.
Por su parte, las especificaciones formales de la semántica de los lenguajes de programación se
efectúan sobre la base de una formulación matemática rigurosa del significado o comportamiento
esperado de programas.
La descripción del comportamiento de las distintas construcciones de un lenguaje de
programación puede ser abordada desde distintos puntos de vista, distinguiéndose dos grandes
enfoques:
1. Los que utilizan metalenguajes de especificación semántica.
2. Aquellos que usan gramáticas atribuidas o gramáticas con atributos.

51

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Metalenguajes para la especificación semántica de lenguajes

Semántica operacional
La semántica operacional describe cómo interpretar un programa a través de una secuencia de
pasos de cálculo u operaciones. La descripción es muy cercana a su implementación.
Semántica denotacional
La principal idea de la semántica denotacional es que el significado de un programa puede
describirse en términos de la aplicación de entidades matemáticas (funciones) a sus argumentos
(denotación). Se alcanza así un elevado nivel de abstracción. De esta forma, se representan todas
las instrucciones del lenguaje con funciones que producen el efecto de haberlas ejecutado. Se
hace más hincapié en el resultado de la computación que en la forma en la que ésta es llevada a
cabo.
Semántica axiomática
La semántica axiomática descansa sobre una teoría formal, donde un conjunto de axiomas, junto
con una descripción formal del programa, permiten la deducción del resultado de la ejecución del
programa en cualquier ambiente dado.
Semántica algebraica
Este método está enfocado a especificar la semántica de los tipos y de las operaciones entre los
mismos. Se basa en la especificación de tipos de datos abstractos mediante un conjunto de valores
posibles y operaciones efectuadas sobre ellos y se la reconoce como una forma de semántica
axiomática basada en las reglas del álgebra.
Semántica de acciones
Está basado en el concepto de acciones, que son las soportadas por las operaciones
habitualmente previstas en los lenguajes de programación. Con este fin, se definen primitivas para
la asignación y declaración de identificadores y la combinación de instrucciones mediante control
de flujo secuencial, condicional e iterativo.

52

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Gramáticas con atributos

Las gramáticas con atributos (GA) o gramáticas atribuidas deben su nombre a que se apoyan en la
asignación de atributos (propiedades) a las distintas construcciones sintácticas de un lenguaje. Las
gramáticas son de tipo 2 (independientes de contexto) a las que se incorporan atributos a sus
símbolos terminales y no terminales, las reglas para su evaluación y las condiciones que éstas
deben cumplir.

Definición de GA
Una gramática con atributos es una gramática de contexto libre a la que se le ha incorporado un
conjunto de atributos (A), un conjunto de reglas semánticas (R) y un conjunto (C) de condiciones,
donde los elementos de A están relacionados con los símbolos terminales y no terminales,
mientras que los de R y C están asociados a cada una de las reglas de producción de P:
𝐺𝐴 = (Σ , Σ , 𝑆, 𝑃, 𝐴, 𝑅, 𝐶)
a. Los primeros cuatro componentes son los que corresponden a toda gramática formal. Las
reglas de producción deben responder a las condiciones que son propias de una gramática
independiente de contexto y pueden estar expresadas en formas normales, en las que las de
Greinbach y de Chomsky son las más habituales.
b. Denominados Σ = Σ ∪ Σ , el quinto componente de la GA es identificado como 𝐴(Σ),
representando al conjunto de atributos asociados a los símbolos del alfabeto Σ. Cada atributo
se denota con un nombre precedido por un punto y el nombre del símbolo al que está
asociado.
c. A cada regla de producción del conjunto P, se le asocia un número finito de acciones o reglas
semánticas que especifican la forma en que se modifican los atributos con la aplicación de la
regla sintáctica. Al conjunto de todas las reglas semánticas se lo define como R(P), que es el
sexto componente de la GA.
d. El séptimo y último componente de la GA es conjunto C(P) de condiciones asociado a cada una
de las reglas de producción P. Estas condiciones, que deben ser cumplidas por lo valores de los
atributos, describen un sublenguaje del lenguaje definido por la sintaxis de la gramática.

53

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Atributos
Los atributos representan propiedades de los símbolos terminales y no terminales de una
gramática y su naturaleza varía según la información que contienen y la fase de procesamiento en
la que se encuentren.
Por ejemplo, el tipo de una variable, su valor, su dirección asignada en memoria, etc.
Al operarse los símbolos del alfabeto Σ a través de las reglas de producción, las propiedades
representadas por los atributos deben ser evaluadas. Dependiendo de las características que
presenten las gramáticas se dispone para esta evaluación de dos mecanismos, que son la herencia
y la síntesis.
Aquí cabe acotar que cuando es posible evaluar todos los atributos de los símbolos de todas las
sentencias de una gramática, se dice que es una gramática bien definida o no circular.

Atributos sintetizados
Las evaluaciones en cada nodo se realizan a partir de los atributos de sus nodos hijos u hojas del
árbol. Esto significa que se avanza en el árbol desde abajo hacia arriba, hasta alcanzar el axioma, lo
que corresponde a un proceso de reducción de una sentencia.
Al conjunto de atributos sintetizados, se lo denomina 𝐴𝑆(Σ).
Cuando todos los atributos asociados con los símbolos gramaticales son sintetizados se dice que se
trata de una gramática S-Atribuida, y aquí son muy eficaces los analizadores ascendentes ya que
permiten evaluar los atributos al mismo tiempo que se analiza la sentencia.

Atributos heredados
Los atributos en una derivación directa son heredados, si los mismos correspondientes a los
símbolos del consecuente de una regla de producción son evaluados a partir de los atributos del
símbolo del antecedente o de los atributos de los demás símbolos del consecuente, siempre que
esos símbolos aparezcan a la izquierda en la producción. Esto significa que, en el árbol de
derivación sintáctica, los atributos son heredados si se calculan a partir de los atributos del padre
de cada nodo o de los nodos hermanos, donde el orden de evaluación de los atributos se
corresponde con el orden en el que se “crean” los nodos de un árbol de análisis sintáctico.
Al conjunto de atributos heredados, se los denomina 𝐴𝐻(Σ) y las gramáticas que contienen
atributos tanto heredados como sintetizados son denominadas L-atribuidas. Entonces, las
gramáticas S-atribuidas son un subconjunto de las L-atribuidas.

54

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 lOMoARcPSD|2834310

Acciones semánticas
Dependiendo del tipo de instrucción, las acciones semánticas que están incluidas en el conjunto
de reglas R(P) tienen distintas finalidades y pueden agruparse según se presenta en la siguiente
tabla:
TIPO DE INSTRUCCIÓN ACCIONES SEMÁNTICAS
Declaración Obtención de tipos de la tabla de símbolos
Ejecutables Completar la definición de tipos de los símbolos
Funciones y procedimientos Comprobación del número, orden y tipo de argumentos
Identificación de variables Comprobación de identificación previo a su uso
Etiquetas Comprobación de repetición y validación
Constantes Comprobación de intentos de alteración de valores
Conversiones Verificación de equivalencias
Sobrecarga de operadores Identificación y resolución

Condiciones
El conjunto de condiciones que es definido sobre las producciones C(P) regulan la validez y alcance
de las acciones semánticas sobre los atributos, estableciendo límites claros a la aplicación de las
acciones según sea la naturaleza de la regla sintáctica. Estas condiciones están activas tanto en
tiempo de compilación como de ejecución, ya que muchas de ellas pueden verificarse
correctamente en forma estática y no cumplirse dinámicamente por alteración de los valores
asociados a los símbolos. El conjunto de estas condiciones describe un sublenguaje del lenguaje
definido por la sintaxis de la gramática, donde los atributos de una sentencia sintácticamente
correcta deben satisfacer todas las condiciones C que le correspondan, para ser considerada
semánticamente válida.

Espero te haya sido útil este trabajo.

UTN FRC – 2018 – Digitaliza tus resúmenes y compártelos.

55

Descargado por Alvaro Juarez (abadalen@linuxmail.org)

 RESUMEN
DE
PROBABILIDAD Y ESTADISTICA
 Unidad 1: Datos estadísticos y Etapas para su
análisis

¿Qué es la estadística?

Método de la recolección en masa de datos que serán utilizados para la

toma de decisiones frente a la incertidumbre.

La estadística trata de la selección, análisis y uso de datos con el fin de

resolver problemas

Existen dos ramas de la estadística:

Descriptiva: Se encarga de la recopilación, análisis y organización de las

variables (datos) para su posterior interpretación.

¿Cómo?

Mediante tablas, gráficos y también dependiendo de donde se saquen las

variables se lo denominara como parámetro en caso de población o
estadístico en caso de muestra.

Inferencia: Técnica que nos permite obtener una generalización o

conclusión de un parámetro de la población mediante estadígrafos con un
cierto agregado de incertidumbre.

Diferencia entre población y muestra

Población: Es la totalidad de individuos de la cual se desea obtener

información, de los cuales podemos denotar que son infinitos o finitos.

Cuando hacemos una medición completa de cada uno de los elementos se

le dice Censo.

Muestra: Es un subconjunto seleccionado de la población y a la medición

de cada uno de estos elementos se lo denomina Muestreo.

Calderon Jonathan Página 1

Generalmente realizar un censo es costoso por lo cual se suele recurrir a
un muestreo. Hay que tener en cuenta el hecho de que al seleccionar un
muestreo hay que hacerlo mediante “Procedimientos de muestreo” para
así no elegir una muestra no representativa.

Datos Estadísticos

Una información es dato estadístico cuando es un conjunto o conjuntos de

valores factibles que puedan ser comparados, analizados e interpretados.
Por ende los datos aislados carecen de interés.

Las medidas que se toman de la información se les llaman variables y

podemos encontrar las siguientes.

Variable Cuantitativa: Dato de tipo numérico que son el resultado de un

proceso de conteo a lo cual se la conocerá como “variable discreta” o de
medición que se denominara como “variable continua”.

Variable Cualitativa: Dato expresado en palabras ya que es imposible

medirlas solo clasificarse porque representan una categoría.

Unidades estadísticas o de análisis

Son cada uno de los elementos que pertenecen a un conjunto. Por

ejemplo si se quiere analizar la inflación de cada una de las provincias del
país la unidad estadística serian las provincias.

Unidad de relevamiento

Lugar donde se encuentran las unidades estadísticas.

Calderon Jonathan Página 2

Escala de medida

Podemos encontrar cuatro tipos que son:

• Nominal: Consiste en categorías cualitativas en la que se registran

los números de observaciones las cuales son mutuamente
excluyentes ósea que dos proposiciones no pueden ser verdaderas
a la vez y además no incluyen un orden lógico.

• Ordinal: Presenta categorías cualitativas mutuamente excluyentes,

con un orden lógico.

Como se puede observa tanto la ordinal como la nominal trabajan con

categorías las cuales, es necesario recalcar, respetan los siguientes
principios: Mutuamente excluyente, Único principio clasificatorio (No
mezclar variables) y Colectivamente exhaustiva (Que se puedan clasificar
todas las unidades del conjunto).

• De Intervalos: Consiste en datos cuantitativos, se suele utilizar

cuando se toman valores numéricos de algunos elementos y se
pueden establecer los intervalos entre esas medidas. Los intervalos
por regla deben tener la misma distancia y además cada escala
tiene un punto cero definido arbitrariamente.

• De Razón: Consiste en datos cuantitativos, que tiene intervalos con

distancias constantes, tiene un punto cero no arbitrario y además la
razón en los números tiene algún significado.

Operaciones permitidas
Nominal Igualdad
Ordinal Mayor o menor
De Intervalos Suma y resta
De Razón Multiplicación y división

Calderon Jonathan Página 3

Siempre teniendo en cuenta que “De razón” cuenta con las operaciones
anteriores, “De Intervalos” con las anteriores pero no con la “De razón” y
así sucesivamente.

Generalmente se puede descender de una escala a otra, pero nunca subir

en la jerarquía salvo de ordinal a Intervalos.

Las variables según el tipo de unidad de referencia

Podemos encontrar:

• Individuales: Hace referencia a las características de una unidad de

análisis o individuo. Ejemplo: Notas de un alumno.

• Agregadas: Hace referencia a las características del agregado en las

que actúan los individuos la cual es independiente de los mismos.
Ejemplo: Fracaso escolar de individuos en una escuela pública o
privada.

• Mixta: Hace referencia a las características agregadas pero que son

basadas en las características de los individuos. Ejemplo: Un colegio
es de clase media por que sus alumnos son de un estrato
económico medio.

Las variables según el papel que cumplen en la investigación

Podemos encontrar:

• Independientes: Variables toman o ya vienen con valores que

influyen a otras haciendo que estas cambien de valor.
• Dependientes: Variables sujetas a otras.
• Control: Sirven para comprender la relación entre una variable
dependiente e independiente. Esta se aplican en casos como:

Calderon Jonathan Página 4

 1. Para averiguar porque entre dos variables hay
dependencia.
2. Para verificar si la relación es casual o de dependencia
3. Para probar las relaciones en todas las circunstancias o si
solo se manifiesta en situación concretas

Etapas del método científico en el análisis de datos

Es necesario para obtener respuestas congruentes durante el análisis de la

información. Consta de 5 pasos:

1. Formular hipótesis: Formular claramente lo que se quiere estudiar

2. Diseño del experimento: Decidir entre hacer un censo o un

muestreo

3. Recopilación de datos estadísticos: Etapa donde se recogen los

datos de las fuentes. Entre los datos a recopilar encontramos la
siguiente ramificación:

• Datos primarios: Son los que hay que recoger mediante el uso
de técnicas como los grupos de interés, entrevistas Teléfono,
Cuestionario por corre, Puerta en puerta, Abordaje en un
centro comercial, Entrevistas

• Datos secundario: Son los que ya están disponibles por

ejemplo en una biblioteca.

Luego tenemos los métodos de relevamiento que son:

• Estáticos: Los datos son obtenidos a una fecha determinada

Calderon Jonathan Página 5

 • Dinámicos: Los datos corresponden a las operaciones que se
realizan de forma continua atreves del tiempo.

4. Tabulación y descripción de resultados: Se refiere a la organización

y presentación de la información recogida para la interpretación de
los mismos. De los cuales podemos ramificar dos opciones:

• Escrito: Esto es solo para cuando tenemos un número

reducido de datos que presentar

• Distribución de frecuencias: Cuando hay una cantidad de

masiva de datos se utilizan diagramas y gráficos.

5. Generalización o Inferencia Final: Este último paso es cuando se

decidió trabajar con una muestra, ya que el problema formulado
anteriormente siempre va a referirse a una población necesitamos
inferir los datos extraídos de la muestra mediante el uso de la
estadística inferencia.

Calderon Jonathan Página 6

Unidad 2: Organización y presentación de datos
estadísticos

Tablas estadísticas
Podemos encontrar dos tipos:

• Tablas de contingencia: Utilizadas para variables cualitativas dentro

de las cuales podemos encontrar (Diagrama de barras, circulo
radiado, Zonas, Diagrama de pareto)

• Tablas de distribución de frecuencias: Utilizadas para variables

cuantitativas dentro de las cuales podemos encontrar muchas como
para ser descritas en una oración :v

Las partes principales de una tabla son:

• Titulo: Descripción del contenido de la tabla

• Encabezamiento: Titulo de los datos presentados
• Conceptos o Columna Matriz: Clasificaciones que aparecen en las
hileras de las tablas, a la izquierda por lo general.
• Cuerpo: Formado por datos estadísticos
• Notas del encabezamiento: Aclaran ciertos aspectos que no han
sido puestos en el titulo
• Notas al pie: Aclaraciones
• Fuente: Lugares de donde se ha obtenido la información.

Para construir una tabla es necesario tener en cuenta:

• Simplicidad
• Solo un tema por vez en la tabla

Calderon Jonathan Página 7

 • Ordenamiento de las clasificaciones mediante el uso de la
cronología, geografía, cuantitativo y cualitativo.
• Destacar de cifras importantes.
• Redondear cifras cuando no se necesita exceso de detalle
• Agregar anotaciones

Formas de agrupar variables cuantitativas

Antes que nada hay que saber distinguir entre:

• Valores posibles: Son todos los valores que puede asumir

• Valores realmente observados: Son los valores que de entre los
posibles han sido efectivamente obtenidos

Según el comportamiento (Discreto o continuo) y la cantidad de valores

observados podemos agruparlas en base a los siguientes tipos:

Series simples o datos no agrupados

Cuando contamos con una cantidad pequeña de valores y no se repiten

con independencia del tipo de variable.

x1 Primer valor
x2 Segundo valor
x3 Tercer valor
xn Valor enésimo

Cabe aclarar que al ser x minúscula nos estamos refiriendo a que los
valores se obtuvieron de un muestreo, en caso de ser X mayúscula nos
referimos a un censo. Lo mismo para la cantidad de elementos dentro de
la muestra es “n” y para la cantidad de elementos de una población es “N”

Calderon Jonathan Página 8

Datos agrupados o en lista

Cuando la cantidad de datos a analizar es muy grande se hace uso de

tablas que se denominan como distribuciones de frecuencia cuyo objetivo
es compactar y simplificar la información para su mayor entendimiento.

Las distribución de frecuencias pueden ser: Unidimensionales (Solo una

variable), Bidimensionales (relación entre dos variables),
Multidimensionales (relación entre más de dos variables).

Solo utilizaremos las Unidimensionales las cuales pueden ser:

Titulo: En Lista

yi ni hi Ni Hi
y1 n1 h1 n1 h1
y2 n2 h2 n1 + n2 h1 + h2
y3 n3 h3 n1 + n2 + n3 = n h1 + h2 + h3 = 1
m n 1

Los componentes de la tabla son:

• Yi: Es la variable la cual representa los valores observados

• m: Es la cantidad de valores distintos observados en la variable
• Frecuencia absoluta (ni): Cantidad de veces que se presento un
valor observado en la variable los cuales sumados deben ser igual a
n
• n: Es el número de elementos de la población o muestra (En caso de
ser “n” es muestra, “N” es población)
• Frecuencia relativa (hi): Proporción en la que se presenta el valor
obtenido como el cociente entre ni/n y la suma de todos ellos deber
ser igual a 1.
• Frecuencia absoluta acumulada (Ni): Suma sucesiva de las
frecuencias absolutas hasta llegar al número de elementos totales n
• Frecuencia relativa acumulada (Hi): Suma sucesiva de de las
frecuencias relativas hasta llegar a 1.

Calderon Jonathan Página 9

 En Intervalos

Para casos en los cuales el número de observaciones es grande y el

número de valores distintos que asumió la variable es casi tan grande
como el total de observaciones es necesario el uso de clases de intervalos.

Antes de armar la tabla de distribuciones es necesario definir los

intervalos:

1. Definimos el recorrido de la serie “R” utilizando los valores que se

nos dieron como datos: R = Vmax – Vmin
2. Definimos la amplitud del intervalo “C” lo que nos va a dar como
resultado la distancia entre el valor mínimo y el máximo de cada
intervalo:
C = R/ N° de intervalos
• El N° de intervalos es arbitrario y siempre tiene que ser
impar.
• En caso de darnos un número decimal tenemos que
redondearlo para arriba hasta llegar a un numero divisible
por dos y entero.
3. Calcular los limites que aseguren que tanto el valor más chico como
el más grande de la serie estarán dentro de algún intervalo de clase.

• Primero calcular el recorrido Ampliado “R’”: R’ = C * N° de

intervalos
• Hacer la diferencia entre el recorrido ampliado y el recorrido
de la serie: R’ – R = X
• Obtener los limites: Linf= Vmin - X o Lmax= Vmax + X pero solo
uno se puede alterar, el otro limite debe quedar intacto.

Titulo: En Intervalo

y’i-1 – y’i yi ni hi Ni Hi
y’0 – y’1 y1 n1 h1 n1 h1
y’1 – y’ 2 y2 n2 h2 n1+n2 h1+h2
y’ 2 – y’3 y3 n3 h3 n1+n2+n3 = n H1+h2+h3 = 1
n 1

Calderon Jonathan Página 10

Los componentes de la tabla:

• Marca de clase (Yi): Es el punto medio del intervalo y se calcula

como la suma de los extremos divido 2: (y’i-1 + y’i) / 2.
• Frecuencia absoluta (ni): Cantidad de veces que se presentaron
entre esos intervalos.
• n: Es el número de elementos de la población o muestra (En caso de
ser “n” es muestra, “N” es población).
• Frecuencia relativa (hi): Proporción de valores comprendida en cada
intervalo.
• Frecuencia absoluta acumulada (Ni): Suma sucesiva de las
frecuencias absolutas hasta llegar al número de elementos totales n
• Frecuencia relativa acumulada (Hi): Suma sucesiva de de las
frecuencias relativas hasta llegar a 1.

Si se quisiera conocer la frecuencia absoluta podemos usar:

• Hojas de cálculo: Se representa cada unidad dentro de una clase

con una raya diagonal
• Forma de asiento: Las clases se anotan al inicio de cada columna y
debajo de ellas se va poniendo el valor que está comprendido en la
misma. Al final de cada columna se pone las m cantidades dentro de
la misma

Formas de agrupar variables cualitativas

Distribución categórica o tablas de contingencia

Se suelen agrupar en categorías, soliendo variar en el hecho de que haya

subcategorías. Siempre y cuando respetando los principios de la
colectividad exhaustiva y lo de mutuamente excluyente, además es
necesaria la definición específica de cada categoría para evitar la violación
de uno de los principios.

Calderon Jonathan Página 11

Representaciones graficas

Gráficos Lineales (Para variables en lista)

• Bastones: Se trabaja con variables discretas y con el uso de

frecuencias relativas o absolutas. Se hace uso de este tipo de grafico
cuando tenemos un agrupamiento de variables en lista. El eje “X”
representa los valores de la variable y el “Y” los valores de
cualquiera de las dos frecuencias.

• Acumulativo de frecuencias: Se trabaja de la misma manera que el

grafico de bastones, las diferencias que trae es que se utilizan las
variables acumulativas y el grafico queda en forma de escalera.

Gráficos de superficie (Para variables en intervalos)

• Histograma(n,h): Se trabaja con variables continuas y con el uso de

frecuencia absoluta o relativa. Los ejes deben comenzar
obligatoriamente en 0 haciendo a veces necesario el uso de
interrupciones de escala.

• Polígono de frecuencias: Se suele hacer uso del histograma para

trazar este tipo de grafico, ya que se traza una línea desde las
marcas de clase (centro) de cada rectángulo. Es útil cuando se
necesita hacer comparaciones con otros histogramas, el único
defecto es el hecho de que no abarca todas las frecuencias ósea no
son proporcionales.

• Curva suave: Se suele presentar cuando el histograma tiene una

amplitud muy pequeña, este tipo de grafico tiene la característica
de representar la verdadera distribución de la población de la que
se extrae la muestra y son a menudo requeridos en la estadística
inferencial.

Calderon Jonathan Página 12

 • Escalonado(N,H): Trabaja con variables continuas y hace uso de las
frecuencias acumuladas operando de manera similar al histograma

• Ojiva(N,H): Representa las distribuciones acumuladas en forma de

un diagrama de líneas en las cuales encontramos la ojiva menor y la
mayor. La ojiva menor se utilizan los limites superiores de cada clase
y utiliza la columna de la frecuencia absoluta de manera ascendente
mientras que la ojiva mayor utiliza el límite inferior de cada clase y
utiliza la columna de frecuencia absoluta/relativa acumulada de
manera descendente

Gráficos especiales(Para variables categoricas):

• Diagrama de barras horizontales(n,h): Hace uso de variables

cualitativas y trabaja con frecuencias absolutas o relativas siendo
estas representadas por el eje x mientras que las categorías son
representadas por el eje y. El ancho de cada barra es puramente
arbitrario y la orientación de las barras puede también ser vertical

• Circulo radiado: Representa variables categóricas (cualitativas)

utilizando también frecuencias absolutas o relativas pero pasadas a
porcentaje.

• Zonas: Utilizado para comparar varios fenómenos usualmente en un

orden cronológico, geográfico, etc.

• Diagrama de Pareto: es una gráfica para organizar datos de forma

que estos queden en orden descendente, de izquierda a derecha y
separados por barras. Teniendo como objetivo el analizar las causas,
estudiar resultados y planear mejoras continuas

Calderon Jonathan Página 13

Unidad 3: Descripción de datos estadísticos
Medidas descriptivas

Representan el comportamiento de un conjunto de datos dándonos una

idea de las tendencias y la dispersión de los mismos como la medida de
posición, de asimetría, de puntiagudez y de dispersión

Medidas de posición
Son medidas que me dan la tendencia central de la distribución de datos
como:

Media (M(X) o M(x)): Suma aritmética de todos los valores observados

divido la cantidad de lo mismos que indica la localización del centro de la
distribución

Fórmula para cada caso

Serie simple ∑𝑛𝑖=1 𝑥𝑖
𝑛
Variables en lista ∑𝑛𝑖=1 𝑦𝑖 ∗ 𝑛𝑖
𝑛
Variables en intervalos ∑𝑛𝑖=1 𝑦′𝑖 ∗ 𝑛𝑖
𝑛

Propiedades: Siendo “k” una constante y “X” e “Y” variables.

• M(k) = k
• M(k * Y) = k *M(Y)
• M(k ± Y) = k ± M(Y)
• M(X ± Y) = M(X) ± M(Y)

Calderon Jonathan Página 14

Mediana (Me o me): Valor que divide al conjunto de datos en dos, que no
supera a no más de la mitad de las observaciones y es superado por no
más de la mitad de las observaciones.

Las formas para calcular varían en cada caso

• Serie simple: Se ordenan los valores que asumió la variable de

manera ascendente o descendente, en caso de ser par la cantidad
de datos se suman los dos valores centrales y se divide por dos, y en
caso de ser cantidad impar el valor de la mediana queda a la vista ya
que se encuentra en el centro dividiendo la serie de datos en dos.

• Variable en lista: Para buscar la mediana es necesario contar con la

frecuencia absoluta(ni) y la acumulada(Ni) de la misma, luego:

a. Buscar el primer valor que supere el cociente n/2 en la

frecuencia absoluta acumulada, lo llamaremos “Nj”.

b. Una vez establecido “Nj” ver si el valor anterior a ese “Nj-1”

es menor o igual al cociente n/2.

c. En caso de ser menor la mediana es el valor de la variable Yi

que está en la misma fila Nj o en caso de ser igual entonces la
mediana es (Yi +Y𝑖−1) / 2

• Variable en intervalos: Se trabaja de la misma manera que en lista,

solo que se tienen en cuenta un parde cosas mas:

1. En caso de ser Nj-1 < n/2 se utiliza la siguiente formula

𝑛
− (N𝑖−1 )
𝑚𝑒 = (Y𝑖−1 ) + 𝐶 ∗ 2
𝑛𝑗
2. En caso de ser Nj-1 = n/2 la mediana es igual a (Yi-1)

Calderon Jonathan Página 15

Moda (Md o md): Valor de la variable que más se repite

Formulas para cada caso

Serie simple Basta con ordenar los valores y ver
qué valor se repite más veces, en
caso de haber más de uno que se
repite igual cantidad de veces se los
toma a todos ellos como moda o si
no hay valores que se repiten no
hay moda
Variable en lista Es necesario ver la frecuencia
absoluta para determinar qué valor
Yi se repite más veces
Variable en intervalos Se consulta también la frecuencia
absoluta, la clase que tenga un
mayor “ni” será la clase modal y su
marca de clase es la moda.

Medidas de Dispersión
Son medidas que indican la concentración o la dispersión de los datos con
respecto a la promedio de la distribución, estas medidas son a menudo
complemento de las medidas de posición ya que por sí solas no
caracterizan totalmente una distribución o también sirven para hacer
comparaciones entre conjuntos. Por ejemplo si hay mucha dispersión
respecto al promedio la medida de posición no representa un valor
altamente significativo del conjunto

Recorrido: Es la diferencia entre el valor mínimo y el máximo del conjunto

de datos. Esta medida es muy sensible a errores ya que si aparece un valor
fuera de lo común ya sea muy grande o pequeño no es posible usarla
como medida de dispersión ya que no revela nada acerca de la
distribución ordinara de los datos.

Calderon Jonathan Página 16

Varianza: Se define como la media aritmética de los cuadrados de las
desviaciones con respecto a la media aritmética

Formulas para cada caso

Serie siemple ∑𝑛𝑖=1 𝑦𝑖²
− 𝑀(𝑌)²
𝑛
Variable en lista ∑𝑛𝑖=1 𝑦𝑖² ∗ 𝑛𝑖
− 𝑀(𝑌)²
𝑛
Variable en intervalo ∑𝑛𝑖=1 𝑦′𝑖² ∗ 𝑛𝑖
− 𝑀(𝑌)²
𝑛

Nota: En la inferencia estadística se suele usar como denominador n – 1

para corregir una variabilidad.

Propiedades: Siendo k una constante y “Y” e “X” variables

• V(k) = 0
• V(k*Y) = k² * V(Y)
• V(k+Y) = V(Y)
• V(-k+Y) = V(Y)

Desviación Estándar: Es la raíz cuadrada positiva de la varianza y es

utilizada para comparar dos o más conjuntos de datos siempre con
respecto a la media aritmética y respetando la unidad de los elementos

Formas de calculo
Serie simple, v. en lista y en 𝐷𝑠 = √𝑉(𝑌)
intervalo

Propiedades: Siendo k una constante y “Y” e “X” variables

• Ds(Y) >= 0
• Ds(k) = 0

Calderon Jonathan Página 17

 • Ds(k + Y) = Ds(Y)
• Ds(Y - k) = Ds(Y)
• Ds(k*Y) = k * Ds(y)
• Ds(X ± Y) = √𝑉 (𝑌) ± 𝑉(𝑋)

Coeficiente de variación: Es la razón entre la desviación estándar y la

media aritmética la cual nos dará como resultado un porcentaje. Esta
medida de dispersión o variabilidad es muy útil a la hora de comparar dos
o más conjuntos con diferentes dimensionabilidad ósea que ambos
conjuntos tienen diferentes magnitudes o unidades

La forma de cálculo es:

𝐷𝑠
𝐶𝑣 =
𝑀(𝑦)

Apreciación del Coeficiente de variación:

Coeficiente de variación Apreciación

26% o mas Muy heterogéneo
Entre 16% y 26% Heterogéneo
Entre el 11% y el 16% Homogéneo
Entre el 0% y el 11% Muy homogéneo

Si el Cv <= 20% se dice que el promedio es representativo.

Medidas de asimetría
Cuando dos conjuntos de datos coinciden en sus medidas de posición y
dispersión se suele recurrir a las medidas de asimetría que muestran de
manera grafica la tendencia central de cada una de ellas.

• Simetría: Es cuando las medidas de posición son iguales (mediana,

moda, media) lo cual forma un grafico con la campana de Gauss

Calderon Jonathan Página 18

 • Asimetría Negativa o a la izquierda: Es cuando las media es menor a
la mediana y esta menor a la moda (Media < mediana < moda)

• Asimetría positiva o a la derecha: Es cuando la meda es mayor a la

mediana y esta mayor a la moda (Media > Mediana > Moda)

Medidas de puntiagudez
Indica la velocidad con la que sube o baja la curva en una distribución de
datos la cual se calcula con el coeficiente de curtosis de Fisher

La forma de cálculo es:

𝑀(𝑌)4
𝑘= −3
𝑉(𝑌)4

En base al resultado diremos que:

• Mesocurtica (K = 0): Esto presenta que el grado de concentración es

medio alrededor de los valores centrales de la variable.
• Leptocurtica (K > 0): Alto grado de concentración alrededor de los
valores centrales de la variable.
• Platicurtica (K < 0): Grado reducido de concentración alrededor de
los valores centrales de la variable.

Calderon Jonathan Página 19

 Unidad 4: Teoría de probabilidades

Esta teoría como lo indica su nombre se basa en las probabilidades que es

la que nos ayuda a medir los riesgos asociados a la toma de decisiones

Experimento aleatorio

Es aquel que conduce a dos o más resultados posibles. Este puede estar
definido por una sola prueba o por un conjunto de pruebas bajo las
mismas condiciones

Espacio probabilístico o muestral

Conjunto de resultados posibles (elementos o puntos de muestra) de un

experimento aleatorio simbolizado por la letra Ω (Omega).

Los puntos de muestra deben ser Mutuamente excluyentes y

colectivamente exhaustivos es decir por lo menos uno de los eventos
debe ocurrir cuando se realiza un experimento.

Omega también puede ser considerado como el conjunto de productos

cartesianos y estos pueden ser representados por un sistema de
coordenadas cartesianas o un diagrama de árbol.

En la mayoría de los casos el espacio probabilístico está compuesto por un

número finitos de puntos no obstante se pueden presentar casos como:
Infinidad numerable de punto e infinidad no numerables de puntos.

Evento o Hecho

Subconjunto del espacio probabilístico denotado con la letra “E” y los

tipos de eventos son:

• Evento simple o elementales: Cuando está formado solo por un

punto o elemento del espacio probabilístico. En base a esto
Calderon Jonathan Página 20
 podríamos decir que el espacio muestral es un conjunto de eventos
simples.

• Evento compuesto: Cuando está formado por más de un punto o

elemento del espacio.

• Evento cierto: Contiene todos los eventos simples del espacio

probabilístico, es decir, es igual al espacio probabilístico.

• Evento imposible: Contiene el elemento vacio, es decir que no

puede ocurrir nunca.

Y a su vez los eventos se clasifican en

• Eventos mutuamente excluyentes: Dos eventos o más que

pertenecen a un mismo espacio probabilístico son mutuamente
excluyentes si la intersección entre ellos da como resultado el
espacio vacio

• Eventos no mutuamente excluyentes: Dos eventos o más que

pertenecen a un mismo espacio probabilístico no son mutuamente
excluyentes si la intersección entre ellos da como resultado un
conjunto distinto del vacío. Además estos eventos presentan
independencia o dependencia.

1. Independencia: Cuando la ocurrencia o no de un evento en

cualquier prueba no afecta la ocurrencia del evento en las
pruebas siguientes
2. Dependencia: Cuando la ocurrencia o no de un evento en
cualquier prueba afecta a la ocurrencia del evento en las
siguientes pruebas.

• Colectivamente exhaustivos: Dos eventos o más que perteneces a

un mismo espacio probabilístico son C.E si la unión entre ellos da
como resultado el espacio muestral en sí.

Calderon Jonathan Página 21

Nota: Un evento ha ocurrido si al menos uno de sus elementos se ha
presentado.

Teoría de probabilidades
Se cuenta con tres tipos de teorías

• Clásica: Se basa en que todos los resultados de un experimento

tienen la misma probabilidad de ser elegidos. Esto presenta un
panorama ideal en el cual por ejemplo una moneda está
perfectamente equilibrada (Que no presenta desbalance alguno) o
que un dado no está modificado para así lograr que un numero
tenga más oportunidad que otro, ante estos casos la teoría clásica
da resultados erróneos

𝐶𝑎𝑠𝑜𝑠 𝑓𝑎𝑣𝑜𝑟𝑎𝑏𝑙𝑒𝑠 𝑎𝑙 𝑒𝑣𝑒𝑛𝑡𝑜

P (E1) =
𝐶𝑎𝑠𝑜𝑠 𝑝𝑜𝑠𝑖𝑏𝑙𝑒𝑠 (𝑛)

• Frecuencia: Se basa en repetir n veces una prueba siendo cada

prueba igual a la anterior, es decir en las mismas condiciones. Por lo
tanto si se repitió un experimento n veces y se obtuvieron “ni”
resultados la razón entre ambos nos dará la probabilidad de que
suceda ese hecho.

𝑛𝑖 𝑉𝑒𝑐𝑒𝑠 𝑞𝑢𝑒 𝑠𝑒 𝑝𝑟𝑒𝑠𝑒𝑛𝑡𝑎

P (E1) = =
𝑛 𝑁𝑢𝑚𝑒𝑟𝑜 𝑡𝑜𝑡𝑎𝑙 𝑑𝑒 𝑝𝑟𝑢𝑒𝑏𝑎𝑠

Por lo tanto también podemos decir que la probabilidad va a estar

siempre entre 0 y 1 (0 <= P (E1) <= 1)

• Subjetiva: Considera la probabilidad como una medida de confianza

personal en una situación particular asignando un peso entre 0 y 1 a
la ocurrencia de un evento según su grado de creencia de que este
sea posible.
Calderon Jonathan Página 22
Axiomas y propiedades para la familia de eventos (F)

• Axioma F1: Si “X” es el evento imposible y “Z” el evento cierto,

ambos pertenecen a la familia de eventos (F).
• Axioma F2: Dado un conjunto numerable de eventos A1,A2,A3…
entonces la intersección entre ellos da como resultado un evento
que pertenece a F.
• Axioma F3: Si A es un evento y ~A es su complemento, entonces ~A
es un evento y pertenece a F
• Axioma F4: Si A y B son eventos, entonces la diferencia entre ellos
también lo será y pertenecerá a F.

Axioma de los eventos y sus propiedades

• Axioma P1: Si A es un evento entonces este tiene asociada una

probabilidad.
• Axioma P2: Conocida como la ley de la no negatividad, la
probabilidad de un evento no es negativa P(A) >= 0.
• Axioma P3: La probabilidad de todo espacio muestral es 1.
• Axioma P4: Sea un conjunto de eventos numerables finitos o
infinitos que sean mutuamente excluyentes, entonces la
probabilidad de la unión de dichos conjuntos es igual a la suma de
sus probabilidades.
• Propiedad P5: Si A y B e F / A C B → P(B - A) = P(B) – P(A)
• Propiedad P6: Si A e F → P(~A) = 1 – P(A)
• Propiedad P7: Si X es cualquier espacio muestral y P es cualquier
función de probabilidad definida sobre X, entonces P(Ø) = 0 siendo
Ø es evento imposible.
• Propiedad P8: La probabilidad de un evento es un número que va
desde 0 a 1.
• Propiedad P9: Si A y B e F / A C B → P(A) < P(B)

Calderon Jonathan Página 23

 • Propiedad P10: Sea un conjunto de eventos numerables finitos o
infinitos que no sean necesariamente mutuamente excluyentes,
entonces la probabilidad de la unión de dichos conjuntos es menor
o igual a la suma de sus probabilidades.

Cálculo de probabilidades

Probabilidad Total (∪)

Es la probabilidad de la unión de eventos en los siguientes casos:

• Mutuamente Excluyentes: P(A ∪ B) = P(A) + P(B)

• No mutuamente excluyentes: P(A U B) = P(A) + P(B) – P(A ∩ B)

Probabilidad Condicional (A/B)

La probabilidad de que ocurra un hecho A, dado que otro hecho B ha

ocurrido la cual se define como:

𝑃(𝐴∩B)
P(A/B) =
𝑃(𝐵)

Cabe aclarar que P (A/B) ≠ P (B/A)

Probabilidad Compuesta (A∩B)

Se presenta cuando se da la ocurrencia de eventos a la vez la cual se

define como

P (A∩B) = P (B) * P (A/B)

Probabilidad Marginal

Es la suma de las probabilidades conjuntas la cual se define como

P(A) = P (A∩B) + P (A∩D)

Calderon Jonathan Página 24

Independencia y Dependencia Estadística

La dependencia e independencia se da por las formas en la que se encara

un proceso aleatorio de selección de elementos que puede alterar o no el
número de componentes del espacio probabilístico. En caso de ser con
reposición todos los eventos serian independientes unos con otros, pero si
es sin reposición se genera eventos dependientes.

Teorema de Bayes

Es una fórmula que sirve para calcular probabilidades condicionales,

estableciendo una relación entre probabilidades condicionales alternas, es
decir se sabe que P (A/B) ≠ P (B/A) pero con el teorema de Bayes es
posible llegar a una relación entre ambas estableciéndola de la siguiente
manera.

𝑃(𝐴)∗𝑃(𝐵/𝐴)
P (A/B) =
𝑃(𝐵)

Desarrollo:

Supongamos lo siguiente

𝑃(𝐴∩B)
• P(A/B) = ---> P(𝐴 ∩ B) = P(A/B) * P(B)
𝑃(𝐵)
P (𝐴 ∩ B) = P (𝐵 ∩ A)
𝑃(𝐵∩A)
• P(B/A) = ---> P(𝐵 ∩ A) = P(B/A) * P(A)
𝑃(𝐴)

Por lo tanto, al ser las probabilidades conjuntas iguales podemos decir

P(A/B) * P(B) = P(B/A) * P(A)

Calderon Jonathan Página 25
 𝑃(𝐴)∗𝑃(𝐵/𝐴)
P (A/B) =
𝑃(𝐵)

Hay que tener en cuenta, en el caso de haber varios eventos, que la

formula puede ser rescrita como:

𝑃(𝐴)∗𝑃(𝐵/𝐴)
1) P (A/B) =
𝑃(𝐵∩𝐴1)+𝑃(𝐵∩𝐴2)+𝑃(𝐵∩𝐴𝑖 )

𝑃(𝐴)∗𝑃(𝐵/𝐴)
2) P (A/B) =
𝑃(𝐵/𝐴1)∗𝑃(𝐴1)+𝑃(𝐵/𝐴2)∗𝑃(𝐴2)+𝑃(𝐵/𝐴𝑖 )∗𝑃(𝐴𝑖)

En el punto 1 podemos decir que toda probabilidad marginal en este caso

la de P (B) es la suma de sus probabilidades conjuntas P (B ∩ A) y en el
punto 2 haciendo un despeje de la probabilidad condicional P (B / A)
podemos obtener que la probabilidad conjunta P (B ∩ A) = P (B / A) * P (A)

Unidad 5: Variables Aleatorias y Distribuciones de

Probabilidad

Variable Aleatoria

Función real valorada, definida sobre los eventos elementales de un

espacio probabilístico, donde cada evento le corresponde un valor que
asume la variable. Esta busca representar el conjunto de valores posibles
de un espacio probabilístico mediante un nuevo conjunto numérico para
así poder presentar probabilidades de presentación de los valores
posibles.

Las podemos clasificar en variables aleatorias discretas o continuas.

Calderon Jonathan Página 26
Formas de representación

• Distribución de probabilidad (Función de cuantía): Muestra todos

los valores posibles que puede asumir una variable aleatoria con sus
correspondientes probabilidades. Lo que nos conlleva a decir que la
función cuantía “P (Y = Xi) = P (Xi)” siempre va a sumir un valor
numérico, que va a ser mayor a cero y que la sumatoria de todos
ellos es igual a 1.

• Distribución de probabilidad acumulada: Utilizada cuando es

necesario saber cuál es la probabilidad de que la variable aleatoria
discreta asuma un valor menor o igual a un número determinado.
Mediante la fórmula F(X) = P(X ≤ xi) = ∑𝑥𝑖 <𝑋 P(Xi)

Características:
o Es una función monótona creciente
o Los valores que puede asumir la función están entre 0 y 1
o La probabilidad de que la variable asuma un valor menor a 0
es igual a 0
o La probabilidad de que la variable asuma valores menores o
iguales a todos los valores posibles va a ser igual a 1
o Dado dos números enteros positivos A y B tales que A < B, la
P(A ≤ X ≤ B) = P(B ≤ X) – P (X < A) = P (B ≤ X) – P(A ≤ A - 1)
o Dado una variable aleatoria X y un numero entero positivo A,
la P(A ≤ X) = 1 – P(X < A) = 1 – P(X ≤ A - 1)

• Función de densidad de probabilidad

Esta función trabaja con variables aleatorias continuas que van a
representar la probabilidad para un intervalo de valores [a, b] y no
un valor puntual. La cual es de la siguiente manera

𝑏
P(a ≤ X ≤ b) = ∫𝑎 𝑓𝑥 ∗ 𝑑𝑥
O
𝑎
P(x ≤ a) = ∫−∞ 𝑓𝑥 ∗ 𝑑𝑥

Calderon Jonathan Página 27

 Características:
o P[x = a] = 0
∞
o ∫−∞ 𝑓𝑥 ∗ 𝑑𝑥 = 1
o 𝑃 (a ≤ X ≤ b) = 𝐹 (𝑏) − 𝐹(𝑎)
o 𝑃 (𝑥 ≥ 𝑎 ) = 1 − 𝐹(𝑎)

Parámetros en la distribución de probabilidad

Estos son calculados en base a los valores posibles que una variable puede
asumir y se utilizan para caracterizar un fenómeno

Esperanza Matemática: Es la media aritmética de las variables aleatorias,

es decir es la suma de los productos de todos los posibles valores de la
variable por sus respectivas probabilidades representada por la letra (Mu)
o E (variable aleatoria)

Formula
𝑁
V. aleatoria Discreta
𝐸 (𝑥) = ∑ 𝑥𝑖 ∗ 𝑃(𝑥𝑖)
𝑖=1
∞
V. aleatoria Continua
𝐸 (𝑥) = ∫ 𝑥 ∗ 𝑓(𝑥) ∗ 𝑑𝑥
−∞

Propiedades

1) Dada una variable aleatoria X, una función de ella G(x) es también

una variable aleatoria. Es decir en discreta y continua seria

𝐸[𝐺 (𝑥)] = ∑ 𝐺(𝑥) ∗ 𝑓(𝑥)

𝑥
∞
𝐸[𝐺 (𝑥)] = ∫ 𝐺(𝑥) ∗ 𝑓 (𝑥) ∗ 𝑑𝑥
−∞

Calderon Jonathan Página 28

 2) La esperanza matemática de una constante es la constante misma
3) E(c*X) = c * E(X)
4) E(c ± X) = c ± E(X)
5) E(X ± Y) = E(X) ± E(Y)
6) E(X * Y) = E(X) * E(Y)

Varianza: Permite conocer la concentración de los resultados alrededor de

la esperanza

Formula
𝑁
V. aleatoria Discreta
𝑉 (𝑥) = ∑ 𝑥𝑖² ∗ 𝑃(𝑥𝑖) − (𝐸 (𝑥))²
𝑖=1
∞
V. aleatoria Continua
𝐸 (𝑥) = ∫ 𝑥² ∗ 𝑓(𝑥) ∗ 𝑑𝑥 − (𝐸 (𝑥))²
−∞

Propiedades

1) V(X) ≥ 0
2) V(c) = 0
3) V(c * X) = c² * V(X)
4) V(c ± X) = V(X)
5) V(X ± Y) = V(X) ± V(Y) Solo cuando X e Y sean independientes

Desviación Estándar: Es la raíz cuadrada de la varianza al igual que en las

medidas de dispersión.

Momento en las distribuciones de probabilidades

Los “momentos” reflejan el grado de asimetría y el grado de agudeza de

una función de probabilidad con respecto a la media o esperanza. Estos se
dividen en dos que son “Momentos naturales de orden k” y “Momentos
centrado de orden k”

Momentos naturales de orden K: Tienen como objetivo calcular la

esperanza de las variables aleatorias

Calderon Jonathan Página 29

 Momentos Naturales de orden K
𝑁
V. aleatoria Discreta
𝐸 (𝑥 𝑘 ) = ∑ 𝑥𝑖𝐾 ∗ 𝑃(𝑥𝑖)
𝑖=1
∞
V. aleatoria Continua
𝐸 (𝑥 𝑘 ) = ∫ 𝑥 𝑘 ∗ 𝑓 (𝑥) ∗ 𝑑𝑥
−∞

Momentos centrados de orden k: Cuando tienen un orden par miden

dispersión y cuando tiene un orden impar miden asimetrías.

Momentos centrados de orden K

V. aleatoria Discreta 𝑚𝑘 = 𝐸 (𝑥 𝑘 ) = [𝐸 (𝑥𝑖 − 𝐸(𝑋))]𝐾

∞
V. aleatoria Continua
𝑚𝑘 = 𝐸 (𝑥 𝑘 ) = ∫ [𝑥𝑖 − 𝐸 (𝑋)]𝑘 ∗ 𝑓 (𝑥) ∗ 𝑑𝑥
−∞

Para el caso de la variable discreta según qué valor tome K representara

distintas cosas

• K = 2: Representa la varianza
• K = 3: Utilizada para determinar si una distribución es simétrica o
asimétrica. Entonces:
o 𝐸(𝑥 3 ) = 0: Simetría alrededor de la esperanza
o 𝐸(𝑥 3 ) > 0: Asimétrica hacia la derecha
o 𝐸(𝑥 3 ) < 0: Asimétrica hacia la izquierda

• K = 4: Representa la curtosis, agudeza o puntiagudez. Entonces:

o 𝐸(𝑥 4 ) = 0: Mesocurtica
o 𝐸(𝑥 4 ) > 0: Leptocurtica
o 𝐸(𝑥 4 ) < 0: Platicurtica.

Calderon Jonathan Página 30

Unidad 6: Modelos especiales de probabilidad de
variables aleatorias discretas
Los modelos probabilísticos nos permite predecir la conducta de futuras
repeticiones de un experimento.

• Modelo bipuntual o de Bernoulli: Modelo aplicable a variables

aleatorias que pueden asumir dos valores (Éxito o fallo) los cuales
tienen una de ellas la probabilidad “P” que es la probabilidad de
éxito y la otra “Q” que es la probabilidad de fracaso que es igual a 1-
P dado que esta es el complemento de “P”.

Función de cuantía
𝑃(𝑋 = 𝑥𝑖) = 𝑃 𝑋 ∗ (1 − 𝑃)1−𝑋

Si hacemos valor 0 a X obtendremos que “Q” y si hacemos valer 1

a X obtendremos “P”.

Parámetros
1
Esperanza
𝐸 (𝑥) = ∑ 𝑥 ∗ 𝑃(𝑥)
𝑥=0
1
Varianza
𝑉 (𝑥) = ∑ 𝑥² ∗ 𝑃(𝑥) − (𝐸 (𝑥))²
𝑥=0
Desviación Ds = √𝑃𝑄
estándar

Demostraciones:
La media es una variable aleatoria bipuntual es igual a la
probabilidad de éxito

𝐸 (𝑥) = ∑1𝑖=0 𝑥 ∗ 𝑃(𝑥) = 0*Q + 1*P = P

La varianza es igual a la probabilidad de un éxito multiplicada por la

de un fallo

Calderon Jonathan Página 31

 𝑉 (𝑥) = ∑1𝑥=0 𝑥² ∗ 𝑃(𝑥𝑖) − (𝐸 (𝑥))²= (0²*Q+1²*P) – P² = P – P² =
P*Q

Este modelo no posee tabla alguna ya que la prueba es realizada

una sola vez.

• Modelo Binomial: En caso de tener n pruebas todas realizadas bajo

las mismas condiciones e independientes entre sí y cada uno de
ellas adopta el modelo bipuntual es decir que en cada prueba solo
se presentan dos valores posibles mutuamente excluyentes y
colectivamente exhaustivos podemos hacer uso del modelo
binomial que será la distribución del numero de Éxitos X.

𝒙 ≈ 𝑩(𝒏, 𝑷)

Además todas las pruebas deben tener igual probabilidad de éxito y

fallo, es decir permanecer constantes. Para ello es necesario tener
en cuenta el tipo de muestreo a realizar y el tamaño de la población

Población infinita: En cualquier tipo de muestre la probabilidad se

va a mantener constante

Población finita: En caso de ser un muestreo con reposición la

probabilidad se mantendrá constante, pero en caso contrario la
muestra deberá ser menor al 5% de la población para así hacer
imperceptible la variación.

Funciones
Función de Cuantía P(x = xi, n, P) = 𝐶𝑛𝑥 ∗ 𝑃 𝑥 ∗ 𝑄𝑛−𝑥

Función Acumulada P(x ≤ xi, n, P) = ∑𝑥𝑖 𝑥 𝑥

𝑥=0 𝐶𝑛 ∗ 𝑃 ∗ 𝑄
𝑛−𝑥

Calderon Jonathan Página 32

 Parámetros
Esperanza E(x) = n*P
Varianza V(x) = n * P * Q
Desviación estándar Ds(X) = √𝑛 ∗ 𝑃 ∗ 𝑄

• Modelo Hipergeometrico: En caso de que se nos encontremos con

un muestreo sin reposición de una población finita siendo n > 5 %
habrá que hacer uso de este modelo ya que encontraremos
dependencia estadística entre las pruebas.

Funciones
Función de cuantía 𝑪𝒙𝑿 ∗ 𝑪𝒏−𝒙
𝑵−𝑿
𝑷(𝑿 = 𝒙, 𝑵, 𝑿, 𝒏) = 𝒏
𝑪𝑵
Función acumulada 𝑪𝑿 ∗ 𝑪𝒏−𝒙
𝒙
𝑵−𝑿
𝑷(𝑿 ≤ 𝒙, 𝑵, 𝑿, 𝒏) = ∑ 𝒏
𝑪𝑵

Este modelo hace uso de la estadística clásica la cual se caracteriza

por obtener las probabilidades a razón de los casos favorables y lo
casos posibles (C.F/C.P).
Los casos favorables en este caso se pueden escribir de esta manera
𝐶𝑋𝑥 ∗ 𝐶𝑁−𝑋 𝑛−𝑥

Los casos posibles se pueden escribir de esta manera

𝐶𝑁𝑛

Llegando a conformar las funciones utilizadas para este método.

Parámetros
Esperanza E(x) = n*P siendo P = X/N
Varianza V(x) = n*P*Q siendo Q = (1-(X/N))
Desviación estándar Ds(x) = √𝒏 ∗ 𝑷 ∗ 𝑸

Calderon Jonathan Página 33

 Cabe aclarar de que cada uno de estos parámetros puede ser
afectado por el factor de corrección de poblaciones finitas siendo
𝑁−𝑛
este
𝑁−1
, que cuando N -> ∞ tiende a ser 1.

• Modelo de proporción: Este modelo permite expresar la proporción

de éxitos en vez de un número de éxitos variando su cálculo
dependiendo del comportamiento de la variable aleatoria, es decir
sea Binomial o Hipergeometrica.
El cálculo proporcional variara en cualquiera de los dos casos siendo
para la binomial p(con sombrero) = x/n y para la hipergeometrica P
= x/n.

Las funciones de cuantía y acumulación también están sujetas a su

modelo, siendo las funciones de este modelo iguales.

Parámetros para el caso Binomial

Esperanza

𝑥 1 1
E (Psombrero)= 𝐸 (𝑛) = ∗ 𝐸(𝑥) = ∗ 𝑛∗𝑃 = 𝑷
𝑛 𝑛

Varianza
𝑥 1 1 𝑷∗(𝟏−𝑷)
V(Psombrero)= 𝑉 ( ) = ∗ 𝑉 (𝑥 ) = ∗𝑛∗𝑃∗𝑄 =
𝑛 𝑛2 𝑛2 𝒏

Desviación Estándar
𝑷∗(𝟏−𝑷)
Ds(Psombrero) = √ 𝒏

Calderon Jonathan Página 34

 Parametros para el caso HiperGeometrico

Esperanza

𝑥 1 1
E (Psombrero)= 𝐸 ( ) = ∗ 𝐸(𝑥) = ∗ 𝑛∗𝑃 = 𝑷
𝑛 𝑛 𝑛

Varianza con factor de corrección

𝑥 1 1 𝑷∗(𝟏−𝑷)
V(Psombrero)= 𝑉 ( ) = ∗ 𝑉 (𝑥 ) = ∗𝑛∗𝑃∗𝑄 = ∗
𝑛 𝑛2 𝑛2 𝒏
𝑵−𝒏
𝑵−𝟏

Desviación Estándar con factor de corrección

𝑷∗(𝟏−𝑷) 𝑵−𝒏
Ds(Psombrero) = √ 𝒏
∗ 𝑵−𝟏

Recordemos que el factor de corrección es agregado por el hecho

de que la muestra pertenece a una población finita

• Modelo de Poisson: Modelo que proporciona la probabilidad de que

ocurra un determinado número de veces “n” en un intervalo de
tiempo, longitud, area, etc.

Funciones
Función de cuantía 𝑒 −λ ∗ λx
P(x=xi,µ = λ) =
𝑥!
Función acumulada 𝑒−λ∗ λx
P(x≤xi,µ = λ) =∑𝑋𝑖
𝑋=0 𝑥!

Siendo λ = n * P número promedio de éxitos en cierto tiempo y

espacio. Esta conjuntamente con la variable x designa al número de
éxitos en una muestra de tamaño n.
Calderon Jonathan Página 35
 Parámetros
Esperanza E(x) = n*P = λ
Varianza V(x) = n*P = λ
Desviación estándar Ds(x) = √𝑛 ∗ 𝑃 = λ

Si realizamos un grafico de simetría la variable nos presentaría

generalmente asimetría positiva, pero si el tamaño de la muestra
aumenta esta tiende a la Simetría.

• Modelo uniforme discreto: Aplicable a un experimento con N

resultados mutuamente excluyentes e igualmente probables. Es
decir la probabilidad es una constante para todos los resultados de
la prueba. Dando así lugar a su función de cuantia como
P(x = xi) = 1/N

Unidad 7: Modelos especiales de probabilidad de

variables aleatorias continuas
Los modelos probabilísticos nos permite predecir la conducta de futuras
repeticiones de un experimento.

• Modelo Uniforme Continuo: Una variable aleatoria continua cuyo

valor solo puede encontrarse en un intervalo (a, b) tiene una
distribución uniforme si su función de densidad es constante en
dicho intervalo

Funciones
Función de densidad 1
f(x) = 𝑏−𝑎 𝑎 ≤ 𝑥 ≤ 𝑏

Función acumulada 𝑥−𝑎

f(x) = 𝑎≤𝑥 ≤𝑏
𝑏−𝑎

Calderon Jonathan Página 36

 Parámetros
Esperanza 𝑎+𝑏
E(x) =
2
Varianza (𝑏−𝑎)²
V(x) =
12
Desviación estándar (𝑏−𝑎)²
Ds(x) = √
12

Desarrollo de la función densidad

Supongamos una constante k y el intervalo (a,b).

Se sabe que una función de densidad f(x) es igual a 1 cuando

tenemos la integral desde -∞ a ∞, es decir.

∞
∫ 𝑓 (𝑥) ∗ 𝑑 (𝑥) = 1
−∞

Ahora integramos a la constante k entre los limites (a,b)

𝑏
∫ 𝑘 ∗ 𝑑𝑥 = 𝑘 ∗ (𝑏 − 𝑎)
𝑎

Dividimos ambos miembros por “k * (b - a)”

𝑏
𝑘 𝑘 ∗ (𝑏 − 𝑎)
∫ ∗ 𝑑𝑥 =
𝑎 𝑘 ∗ (𝑏 − 𝑎) 𝑘 ∗ (𝑏 − 𝑎)

Dando por resultado

𝑏
1
∫ ∗ 𝑑𝑥 = 1
𝑎 (𝑏 − 𝑎)

1
Lo cual indica que la función” f(x) = “es una función de
(𝑏−𝑎)
densidad constante.

Calderon Jonathan Página 37

 Desarrollo de la función de acumulación

𝑥
1 𝑥−𝑎
∫ ∗ 𝑑𝑥 =
𝑎 (𝑏 − 𝑎) 𝑏−𝑎

La cual dará 0 cuando x ≤ a y 1 cuando x ≥ b

• Modelo exponencial: Modelo que busca responder el tiempo o

espacio que puede haber entre la ocurrencia entre hechos o el
tiempo o espacio que es necesario que transcurra para que se
presente un hecho.
Se suele decir que el modelo exponencial es el reverso del modelo
de poisson ya que este se encarga del número de éxitos la
exponencial busca el tiempo entre esos éxitos o el tiempo hasta que
suceda uno de ellos.

Funciones
Función de densidad
t(x) = 𝜆 − 𝑒 −λx

Función acumulada
t(x) = P(x ≤ xi) = 1 − 𝑒 −λx

Parámetros
Esperanza 1
E(x) = β =
𝜆
Varianza 1
V(x) = β² =
𝜆²

Desviación estándar 1
Ds(x) = β =
𝜆

Calderon Jonathan Página 38

 • Modelo Normal: Teoría que sirve para explicar algunas variables
aleatorias la relación entre los intervalos de sus valores y sus
respectivas probabilidades la cual es muy útil para aproximar los
modelos binomial, poisson, hipergeometrica cuando el tamaño de
la muestra es grande.
Característica
El comportamiento muestral de un estadígrafo es independiente de
cómo se comporte la población, para un n > 30.

• Modelo Normal General: Sea una variable aleatoria continua x

diremos que tiene una distribución aproximadamente normal con
media µ y desviación estándar σ, es decir X ~ N(µ,σ) si su función de
densidad es

1 −
(𝑥−µ)²
𝑓(𝑥 ) = 𝑒 2σ²
σ√2π
A tener en cuenta:
o Toda el área bajo la curva es igual a 1
o La curva es asintótica con el eje de las x
o El área determinada por un intervalo debajo de la curva y por
encima de las x es la probabilidad del mismo.
o El dominio de f(x) es infinito
o f(x) solo depende de µ y σ
o µ Es el factor de traslación que mueve la grafica
o σ Hace que sea más o menos aplanada la función

La función de acumulación es:

𝑥
𝐹 (𝑥 ) = ∫ 𝑓 (𝑥 ). 𝑑𝑥
−∞

Propiedades:

Calderon Jonathan Página 39

 o Es simetrica con respecto al valor medio
o Es de forma acampanada
o Es de transformación lineal de escala
o Se puede realizar combinaciones lineales de variables
aleatorias

• Modelo Normal Estándar: Sea una variable aleatoria continua x la

cual es estandarizada a una nueva variable Z, se dice que Z ~ N(0,1)
si su función de densidad es

1 −𝑧²
𝑓(𝑧) = 𝑒−2
√2π

La estandarización de la variable se realiza mediante lo siguiente

𝑥− µ 1 µ
𝑍= = 𝑥−
σ σ σ

Demostración de E (Z) = 0

1 µ 1 µ
𝐸( 𝑥− ) = ∗µ− =0
σ σ σ σ

Demostración de V (Z) = 1

1 µ 1 1
( )
𝑉( 𝑥− ) = 𝑉 𝑥 − 0 = ∗ σ² = 1
σ σ σ² σ²

Su función de acumulación es:

𝑍
F (z) = ∫
−∞
𝑓 (𝑧) ∗ 𝑑𝑧

Calderon Jonathan Página 40

 • Regla Empirica de la varianza: Esta regla sirve para darnos la
probabilidad que hay de obtener un valor x de una variable
aleatoria continua en base a la media y la desviación para el caso de
modelos normales.

o Entre la media y la desviación estándar siempre va a ver la

probabilidad del 68%.
o Entre la media y dos veces la desviación estándar la
probabilidad va a ser del 95 %.
o Entre la media y tres veces la desviación estándar la
probabilidad va a ser del 99%.

• Aproximación del Modelo Binomial al Modelo Normal: Supongamos

que el tamaño de la muestra n aumenta de manera considerable (n
≥ 30) por lo cual si viésemos su función notaríamos que tiende a ser
simétrica independientemente del valor de éxito (P) y del valor de
fracaso (Q). En este caso se puede definir a la variable aleatoria
discreta x que se comporta como binomial como una variable
aleatoria continua z estandarizándola de la siguiente manera

𝑥−𝑛∗𝑃
𝑍= ~N(0,1)
√𝑛∗𝑃∗𝑄

Siendo en este caso µ = n*p y σ =√𝒏 ∗ 𝑷 ∗ 𝑸

• Aproximación del modelo de Poisson al modelo Normal: Siguiendo

la misma lógica que la de la aproximación anterior, haremos uso de
el modelo de poisson cuando λ ≥ 21 estandarizándola de la
siguiente manera

𝑥−𝑛∗𝑃
𝑍=
√𝑛 ∗ 𝑃
Calderon Jonathan Página 41
 Siendo en este caso µ = n*p y σ =√𝒏 ∗ 𝑷
• Aproximación del modelo Hipergeometrico al Modelo Normal:

𝑿
𝒙 − 𝒏𝑵
𝒁=
√𝒏 𝑿 ∗ (𝟏 − 𝑿 ) ∗ 𝑵 − 𝒏
𝑵 𝑵 𝑵−𝟏

• Aproximación del Modelo Proporcional al Modelo Normal:

𝑷𝒔𝒐𝒎𝒃 − 𝑷
𝒁=
√𝑷 ∗ 𝑸 ∗ 𝑵 − 𝒏
𝒏 𝑵−𝟏

• Distribuciones de las pequeñas muestras: Suele haber situaciones

en las cuales no contamos con una n grande, por lo tanto no
podemos asegurar que la distribución se comporta como normal.
Para ellos está el uso de las siguientes distribuciones de
probabilidades con n pequeña.

• Grados de Libertad: Es el numero de parámetros a estimar

representado por la operación n-1.

• Chi-Cuadrado(𝑋 2): Se define como la suma de n variables aleatorias

continuas independientes al cuadrado (𝑍𝑖2 ) en donde cada variable
Zi~N(0,1)

𝑥− µ 2
Es decir ∑𝑛𝑖=1 𝑍𝑖2 = ( σ ) = 𝑋(𝑛)
2

Características: Siendo ∅ = 𝑛 − 1
o El campo de variación de esta distribución va desde el 0 hasta
el + ∞

Calderon Jonathan Página 42

 o La función de Chi cuadrado es positivamente asimétrica
o Si ∅ ≥ 30 la función se aproxima a la distribución normal

Parámetros
Esperanza 2
E(𝑋(∅) )=µ

Varianza 2
V(𝑋(∅) ) = 2∅

Desviación estándar Ds(x) = √2∅

• “t” de Student: Esta distribución se define como

𝑍 𝑥−𝑢
𝑡∅ = =
2 σ
√𝑋
∅

Y es aplicada cuando se desconoce la varianza poblacional y el

tamaño de la muestra es pequeño

Características:
o La variable t asume valores de -∞ a ∞.
o Es unimodal y simétrica respecto a 0.
o Es más aplanada que la distribución normal, pues su varianza
es ligeramente superior a 1.

Parámetros
Esperanza E(t) = 0

Varianza ∅
V(t) =
∅−2

Calderon Jonathan Página 43

 Desviación estándar ∅
Ds(t) = √∅−2

Unidad 8: Teoría del Muestreo

La teoría del muestro que corresponde a la inferencia estadística tiene sus
bases en dos aspectos

• Estimación de parámetros de población: Lo cual se logra partiendo

de estimadores muéstrales y calculando la precisión de la
estimación
• Docimasia o Prueba de hipótesis: Se utiliza la muestra para
determinar si un supuesto sobre la población es verdadero o falso,
midiendo los riesgos de cometer un error.

Razones para el muestreo

• Mayor exactitud: Suele suceder que un muestreo sea más exacto

que un censo ya que en el muestreo se observan menores errores
de observación y además los errores de estimación pueden ser
calculados para así determinar un cierto grado de confianza para su
uso.
• Costo: Un muestreo es generalmente menos costoso que un censo.
• Tiempo: Se tarda mucho menos en hacer un muestreo y en tabular
sus datos.

Base teórica del muestreo

Los datos estadísticos poseen dos importantes características que son

• Diversidad: Hace referencia a la cantidad de características dentro

una muestra que poseen los elementos los cuales las pueden tener
en mayor o en menor medida. Aunque las variaciones son limitadas
haciendo posible el muestreo de una cantidad pequeña.

Calderon Jonathan Página 44

 • Regularidad o Uniformidad: Es la tendencia de las características
conmensurable a concentrarse alrededor de una medida de
tendencia central.

A la hora de comenzar a realizar un muestreo es necesario seguir las

etapas de investigación científica por lo cual una vez establecido el
problema a analizar recurrimos a diseñar las muestras que comprende:

o Plan de Muestreo
o Elección del estimador a utilizar

Procedimientos para la selección de Muestras

Para seleccionar una muestra representativa es necesario considerar dos

criterios:

o Fiabilidad: Este criterio es dado por la varianza del estadígrafo

mientras mayor sea la varianza menos fiable va a ser la muestra.
o Efectividad: Está ligado al costo que implica realiza el muestreo, un
diseño de muestreo es más efectivo que otro solo si este resulta
más barato pero tiene la misma calidad.

Tipos de procedimientos

Muestreo no probabilístico: Las unidades de la población que integran la

muestra son seleccionadas en base al criterio del investigador lo cual
implica que no haya aleatoriedad y por ende no se pueda hacer inferencia
sobre la población de la cual fue extraída. Dentro del muestreo no
probabilístico encontramos:

• Muestro de Criterio: El investigado selecciona las unidades que van

a componer la muestra.

• Muestreo de la muestra disponible: La muestra queda constituida

por una parte de la población que se encuentra convenientemente

Calderon Jonathan Página 45

 disponible, es decir se compone de la parte que es más fácil de
tomar.

• Muestreo por cuotas: Caso particular del muestreo de criterio en el

cual el investigador establece pasos explícitos para obtener una
muestra que sea similar a la población objetivo, ejerciendo
controles sobre algunas características de sus elementos. A partir de
un listado de la población se estiman el tamaño de la muestra.

Muestro probabilístico: Las unidades son seleccionadas en base a lo

propuesto por la teoría de probabilidades permitiéndonos así conocer el
error de muestreo, la evaluación en términos de probabilidad y la
precisión del estimador, además este tipo de muestro nos permite realizar
inferencias sobre la población dentro del cual podemos encontrar:

• Muestreo Aleatorio simple: Procedimiento en el cual se seleccionan

n unidades de una población de tamaño N de tal manera que cada
una de las muestras del mismo tamaño tengan las mismas
probabilidades de ser seleccionadas. En caso de ser un muestreo
con reemplazo la probabilidad de cada muestra será 1⁄𝑁 𝑛 y de ser
sin reposición la probabilidad de cada muestra será 1⁄𝐶𝑁𝑛 . Este tipo
de muestro debe ser usado en poblaciones pequeñas y homogéneas
en donde se pueda identificar todos los elementos de la población
(Colectivamente exhaustivo)

• Muestreo Aleatorio Estratificado: En casos de la población no ser

homogénea en relación a la característica bajo estudio se crean los
denominados “estratos” que son subconjuntos de la población que
nos pueden brindar información si se quiere con distinta precisión.
El procedimiento para realizar este tipo de muestro es:

o Subdividir la población de cantidad N en estratos, es decir

N = ∑𝑁
𝑖=1 𝑁𝑖

Calderon Jonathan Página 46

 o De cada estrato obtener una muestra aleatoria simple ni,
siendo la muestra total la suma de todos ellos, es decir n =
∑𝑛𝑖=1 𝑛𝑖

o Obtener los estadísticos de interés.

Es posible realizar una estratificación doble, que es cuando a los

estratos se los divide en subestratos. Ahora, con respecto al
tratamiento de cada estrato hay que tener en cuenta que los
elementos dentro de cada uno deben ser los más homogéneos
posibles para así conseguir buenos valores, pero los estratos entre sí
deben ser lo más heterogéneos posibles.
Con respecto al tamaño de la muestra que se la denomina afijación
hay tres formas de obtenerla:

o Afijación Igual: Donde todas las muestras son iguales, este

tipo de afijación es aplicable cuando los estratos tienen igual
participación en la población y sus desviaciones son parecidas

𝑛
𝑛𝑖 =
𝑟

Siendo n el tamaño de la muestra deseada y r la cantidad de

estratos.

o Afijación Proporcional: Cada “ni” posee en la muestra la

misma proporción que cada “Ni “posee en la población, este
tipo de afijación es aplicable cuando los estratos difieren en
su participación en la población y sus desviaciones son
parecidas.

𝑁𝑖
𝑛𝑖 = ( ) 𝑛
𝑁

Calderon Jonathan Página 47

 o Afijación Optima o de Neyman: Este tipo de afijación es la
mejor que hay ya que maximiza la precisión del estimador de
la muestra utilizando en la ecuación la desviación estándar de
cada estrato, este tipo de afijaciones es aplicable cuando los
estratos difieren entre sí o son iguales y sus desviaciones son
disimiles.

𝑁𝑖∗σ𝑖
𝑛𝑖 = ( )∗𝑛
∑ 𝑁𝑖∗σ𝑖

• Muestreo sistemático: Se selecciona un elemento de la población

cada k elementos, después de haber ordenado los elementos de la
misma de una manera específica. El punto de partida se selecciona
al azar de entre los primeros k valores. El valor de k que significa
“razón de muestreo” está representado por la siguiente fórmula:

𝑁
𝑘=
𝑛

Este tipo de muestro es más eficaz que el muestreo aleatorio simple

si los elementos en la población se asemejan más entre sí.
El hecho de necesitar que la población sea ordenada en base a un
criterio presenta una desventaja si la población es demasiada
extensa.

• Muestreo por Conglomerados: Consiste en tomar pequeños grupos

de la población que se denominan conglomerados, dentro de los
cuales debe haber heterogeneidad pero entre conglomerados debe
haber homogeneidad. Una vez realizado los mismos se toma de
cada uno de ellos elementos al azar para así constituir una muestra
global. La toma de elementos para la muestra se divide en rondas, si
hubo varias rondas se dice que el muestreo es de etapas múltiples.

Calderon Jonathan Página 48

 La ventaja es la reducción de costos a la hora de hacer el muestreo,
el problema es que el grado de la varianza es muy alto lo cual se
puede compensar aumentando el tamaño de la muestra.

Distribuciones en el muestreo

Antes que nada hay que recordar que los muestreos pueden ser con
reposición o sin teniendo cada uno sus respectivas características:

Muestro con reposición

Cantidad de elementos en el 𝑁𝑛
espacio probabilístico
Probabilidad de cada evento 1/𝑁 𝑛
elemental

Muestreo sin reposición

Cantidad de elementos en el 𝐶𝑁𝑛
espacio probabilístico
Probabilidad de cada evento 1/𝐶𝑁𝑛
elemental

Una vez aclarado eso podemos decir que hay tres tipos de distribuciones
que son:

• Media Muestral(X con rayita arriba): Es el promedio de

observaciones

∑𝑛𝑖=1 𝑥𝑖
𝑛

La cantidad de medias muéstrales será la cantidad total del espacio

probabilístico que se ve afectado por el tipo de muestreo realizado.
Tengamos en cuenta que la media muestral es una constante para
Calderon Jonathan Página 49
 una muestra, pero en el conjunto de muestras posibles la media
muestral se vuelve una variable aleatoria pues no se sabe que
muestra ha de presentarse.

El símbolo de la media muestral es una x con una raya arriba, por

comodidad la nombro xr

Al ser la media muestral una variable aleatoria podemos calcular su

esperanza, varianza y desviación estándar.

o Esperanza de la media muestral: Esta medida debe ser igual a

la media poblacional tanto como si el muestreo se realizo con
reposición o sin reposición. Su fórmula es:

𝐸(𝑥𝑟) = ∑ 𝑥𝑟𝑖 ∗ 𝑃(𝑥𝑟𝑖 )

𝑥=0

O en caso de contar una tabla de distribución de

frecuencia absoluta

∑𝑛𝑖=1 𝑥𝑟𝑖 ∗ 𝑛𝑖
𝐸(𝑥𝑟) =
𝑁 𝑛 𝑜 𝐶𝑁𝑛

Siendo ni la frecuencia absoluta de cada media

muestral y el denominador dependerá de si el
muestreo es con reposición o sin reposición.

o Varianza de la media muestral: Esta es proporcional a la

varianza poblacional y mientras mayor sea la muestra menos
variabilidad tendrá la media muestral

σ²(𝑥𝑟) = ∑ 𝑥𝑟𝑖 ² ∗ 𝑃(𝑥𝑟𝑖 ) − [𝐸(𝑥𝑟)]²

𝑥=0

Calderon Jonathan Página 50

 O en caso de contar una tabla de distribución de
frecuencia absoluta

∑𝑛𝑖=1 𝑥𝑟𝑖 ² ∗ 𝑛𝑖
σ2 (𝑥𝑟) = − [𝐸(𝑥𝑟)]²
𝑁𝑛 𝑜 𝐶𝑛𝑁

Siendo ni la frecuencia absoluta de cada media

muestral y el denominador dependerá de si el
muestreo es con reposición o sin reposición.

La relación que guarda la varianza de la media muestral

con la varianza población es la siguiente:

Muestreo con σ2 (𝑋)

reposición σ2 (𝑥𝑟) =
𝑛
2(
Muestreo sin σ 𝑋) 𝑁−𝑛
reposición σ2 (𝑥𝑟) = ∗
𝑛 𝑁−1

Siendo σ2 (𝑋) la varianza población y 𝑁−1 el factor de

𝑁−𝑛

correcciones finitas

o Desviación estándar: Se calcula como la raíz cuadrada

de la varianza

σ(𝑥𝑟) = √σ2 (𝑥𝑟)

Recordemos que la varianza está sujeta a si el

muestreo es con reposición o sin reposición.
La relación que guarda la desviación estándar de la
media muestral con la varianza población es la
siguiente:

Calderon Jonathan Página 51

 Muestreo con σ(𝑋)
reposición σ(𝑥𝑟) =
√𝑛
Muestreo sin σ(𝑋) 𝑁−𝑛
reposición σ(𝑥𝑟) = ∗
√𝑛 𝑁−1

Cabe aclarar que el factor de corrección de poblaciones finitas es

justamente para poblaciones finitas, en caso de ser infinita la población no
es necesario aplicarlo por más que el muestreo haya sido realizado sin
reponer

• Proporción Muestral (P sombrero o p): Esta se define como la razón de

la cantidad de éxitos en n pruebas sobre el tamaño de la muestra.
Es decir: 𝑝 = 𝑥⁄𝑛
La proporción muestral también va a ser una variable aleatoria y por
ende podemos calcular su esperanza, varianza y desviación.

o Esperanza de la proporción muestral: Siempre es igual

a la proporción poblacional independientemente de si
el muestreo fue con o sin reposición. Se define como

𝐸 (𝑝) = ∑ 𝑝𝑖 ∗ 𝑃(𝑝𝑖 )
𝑖=1

O en caso de contar una tabla de distribución de

frecuencia absoluta

∑𝑛𝑖=1 𝑝𝑖 ∗ 𝑛𝑖
𝐸 (𝑝) =
𝑁 𝑛 𝑜 𝐶𝑁𝑛

Siendo ni la frecuencia absoluta de cada media

muestral y el denominador dependerá de si el
muestreo es con reposición o sin reposición.

Calderon Jonathan Página 52

 o Varianza de la proporción muestral: Se define como

σ2 (𝑝) = ∑𝑛𝑖=1 𝑝𝑖 ² ∗ 𝑃(𝑝𝑖 ) − [𝐸(𝑝)]²

O en caso de contar una tabla de distribución de
frecuencia absoluta

∑𝑛𝑖=1 𝑝𝑖 ² ∗ 𝑛𝑖
𝐸 (𝑝) = − [𝐸(𝑝)]²
𝑁 𝑛 𝑜 𝐶𝑁𝑛

Siendo ni la frecuencia absoluta de cada media

muestral y el denominador dependerá de si el
muestreo es con reposición o sin reposición.

Con respecto a las relaciones que este guarda con la

varianza poblacional es

Muestreo con P(1 − P)

reposición σ²(𝑝) =
𝑛
Muestreo sin P(1 − P) 𝑁 − 𝑛
reposición σ²(𝑝) = ∗
𝑛 𝑁−1

Siendo P la proporción poblacional.

o Desviación estándar de la proporción Muestral: Es la

raíz cuadrada de la varianza de “p” es decir

σ(𝑝) = √σ2 (𝑝)

Con respecto a las relaciones que este guarda con la

desviación estándar poblacional es

Muestreo con
reposición P(1 − P)
σ(𝑝) = √
𝑛

Calderon Jonathan Página 53

 Muestreo sin
reposición P(1 − P) 𝑁 − 𝑛
σ(𝑝) = √ ∗
𝑛 𝑁−1

El factor de corrección para poblaciones finitas recibe el mismo trato que

en la media muestral.

• Varianza muestral corregida(s²sombrero): Indicara como toda varianza

el grado de dispersión o concentración de las observaciones
muéstrales respecto a su valor central y se define como

∑𝑛𝑖=1(𝑥 − 𝑥𝑟)²
𝑠²𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜 =
𝑛−1

La relación que establece la varianza muestral con la varianza

poblacion es

𝑛
𝑠²𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜 = 𝑆²
𝑛−1
Se puede calcular la desviación estándar muestral también siendo
esta la raíz cuadrada de la varianza muestral corregida

𝑠𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜 = √𝑠²𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜

Esta al igual que sus predecesoras es también una variable aleatoria

con la diferencia de que solo podemos calcular la esperanza

o Esperanza: Siempre es igual a la varianza poblacional

independientemente de si el muestreo se realizo con o
sin reposición. Se define como

Calderon Jonathan Página 54

 𝑛

𝐸 (𝑠 2 𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜 ) = ∑ 𝑠 2 𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜.𝑖 ∗ 𝑃(𝑠 2 𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜.𝑖 )

𝑖=1

O en caso de contar una tabla de distribución de

frecuencia absoluta

2
∑𝑛𝑖=1 𝑠 2 𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜.𝑖 ∗ 𝑛𝑖
𝐸 (𝑠 𝑠𝑜𝑚𝑏𝑟𝑒𝑟𝑜 ) =
𝑁 𝑛 𝑜 𝐶𝑁𝑛

• Teorema central de limite: Cualquiera sea la distribución de la

población en la medida que posea una varianza finita, la variable
𝑥𝑟−µ
aleatoria Z = ~N(0,1) a medida que n crezca indefinidamente.
√𝑥𝑟
En general la normalidad de una distribución para la media muestral
es el denominado teorema central del límite y establece que:

o Cuando la población es grande y está distribuida

normalmente la media muestral también será normal.
o Cuando la población no está distribuida normalmente,
la distribución de medias muéstrales se aproximara a
una distribución normal si la muestra n es grande (n ≥
30).
o Si la distribución normal de las medias muestrales
tienen la media igual al valor esperado de la muestra
E(xr) y la desviación estándar entonces teóricamente
estos pueden ser calculados por la media poblacional
(µ = E(xr)) y la desviación estándar poblacional
σ(xr)
(σ(X) = )
√n

Calderon Jonathan Página 55

 Unidad 9: Estimación Estadística
Como se vio en la unidad anterior a veces no se puede trabajar con la
población por x limitaciones por lo cual se hace necesario el uso de
estimadores. El método para obtener el valor o mejor dicho hacer la
estimación recibe el nombre de estimador mientras que el resultado
obtenido se llama estimación del parámetro. A partir de estos conceptos
llamaremos entonces

Ø Al parámetro a estimar

Øsombrero Al estimador que por razones cómodas solo para este resumen se
llamara Øs el cual será función de las observaciones muéstrales y por esto
implica que va a ser una variable aleatoria. Por otro lado un estimador es
un estimador puntual de una característica de la población si proporciona
un solo número como estimación y por otro lado está la estimación por
intervalos en donde sitúa al parámetro entre dos valores para una
confianza dada

Las propiedades de los buenos estimadores puntuales son:

• Insesgabilidad: Es cuando la esperanza del estimador es igual al

parámetro a estimar, es decir :
E (Øs) = Ø.
Si no son iguales ambos valores la diferencia entre ellos se
denomina sesgo dando pie al sesgo positivo E (Øs) > Ø y al negativo
E (Øs) < Ø. Un caso particular de esta es cuando la mediana
muestral es igual a la media poblacional, eso solo sucede cuando la
distribución de la población es normal

• Eficiencia: Esta propiedad se refiere a la variabilidad de los

estimadores, dado por la varianza que nos da un grado de confianza
sobre los mismos. Es decir supongamos que tenemos dos
estimadores Ø1 y Ø2. Independientemente de si uno presenta un
sesgo o no siempre se preferirá el que tenga menos varianza. Hay
un método para elegir estimadores llamado Eficiencia relativa que
es la razón entre la varianza de ambos estimadores

Calderon Jonathan Página 56

 • Consistencia: Un estimador es consistente si a medida que el
tamaño de la muestra se aproxima al tamaño de la población (n →
N) si el estimador se aproxima al parámetro a estimar (Øs → Ø).

• Suficiencia: Es un estimador que utiliza toda la información posible

de la muestra

La estimación puntual tiene el problema de que no puede otorgar

precisión de la estimación obtenida como así puede darla la estimación
por intervalos

Error, riesgo y tamaño de la muestra

Supongamos un parámetro a estimar Ø con un estimador Øs, el cual al

tomar una muestra asume un valor particular Øs0 dando pie a la
estimación puntal que se utilizara para estimar a Ø. Entonces el error de
muestreo “e” es la diferencia entre (Øs0 – Ø)

e = (Øs0 - Ø)

Ahora para medir el riesgo de cometer un error mayor que “e” seria

Pr[(Øs0- Ø) > e]
Øs0− Ø
Pero antes hay que normalizar la variable particular, es decir z = σ(Øs)

La probabilidad anteriormente mencionada nos da el nivel de confianza

con respecto a la distribución de valores con los que estamos trabajando.

• Relación entre error, riesgo y tamaño de la muestra: A la hora de

ver las relaciones es necesario tener presenta que siempre se parte

Calderon Jonathan Página 57

 Øs0− Ø
de la función de la tipificación de una variable, es decir z = y
√σ(Øs)
que el riesgo es función inversa de z.

o Riesgo:
𝑒 ∗ √𝑛
𝑍=
σ

Si incrementamos el error, Z se incrementa y el riesgo

disminuye.
Si incrementamos el tamaño de la muestra, Z se incrementa y
el riesgo también disminuye.
Si incrementamos la desviación, Z disminuye y el riesgo
aumenta.

o Error: Despejando “e” de la ecuación anterior

𝑍∗ σ
𝑒=
√𝑛
Mientras mayor sea la desviación, mayor será el error
Si se incrementa n el error será más pequeño
Si incrementamos el riesgo disminuye z y disminuye el error

o Tamaño de la muestra: Despejando “n”

𝑧² ∗ σ²
𝑛=
𝑒²

Si incrementamos el riesgo, z disminuye y por ende n también

Si incrementamos la varianza, n aumenta
Si incrementamos el error menor tamaño de la muestra.

Estimación por intervalos

Calderon Jonathan Página 58

Consiste en obtener un cierto intervalo aleatorio a partir de la estimación
puntal considerando un cierto error en la estimación y un determinado
grado de confianza de que el intervalo construido contiene el parámetro
que deseamos estimar. Los elementos que intervienen para este tipo de
estimación son:

Ø Parámetro a estimar
Øs Estimador
K(Ø, Øs) Distribución de probabilidades
tabulada y conocida
n Observaciones muéstrales
K1,k2 Coeficientes de confianza o puntos
críticos
1-α Nivel de confianza
L1, L2 Limites del intervalo de confianza
(L1 < Ø < L2)

Intervalo de confianza para estimar (μ)

Se hace uso de la distribución normal y la de “t” de studen de la siguiente

manera

Poblaciones normales Poblaciones no normales

σ² conocida con Distribución σ² conocida con Por TCL Normal
un “n” normal un n ≥ 30
cualquiera
σ² Desconocida σ² Desconocida
n < 30 “t” de student n < 30
n ≥ 30 Por TCL Normal n ≥ 30 Por TCL Normal

Caso 1: σ² conocida con un “n” cualquiera o n ≥ 30

Ø=μ

Øs= xr

Calderon Jonathan Página 59

 𝑥𝑟 − 𝜇
K(Øs, Ø) = σ ~ N(0,1)
√n

Con lo anterior procedemos a armar el intervalo de confianza

1 – α = Pr [𝑧1≤ 𝑥𝑟 − 𝜇 ≤ 𝑍 ]
σ 2
√n

Despeje μ el nivel de confianza va a quedar como

σ σ
1 – α = Pr [𝑥𝑟 − 𝑧2∗ ≤ μ ≤ 𝑥𝑟 + 𝑧1∗ ]
√n √n

Ese enunciado asegura que si se toman muchas muestras de tamaño n, (1

– α) % de ellas serán correctas.

En caso de ser el muestreo realizado sin reposición se tendrá que aplicar el

factor de corrección de población finita en cada uno de los errores de
σ
estimación “e = 𝑧2∗ ”
√n

Caso2: σ² desconocida con un n < 30

Ø=μ

Øs = xr
𝑥𝑟 − 𝜇
K (Øs, Ø) = σ ~ 𝑡𝑛−1
√n

Con lo anterior procedemos a armar el nivel de confianza

𝑥𝑟 − 𝜇
1 – α = Pr(t1 ≤ σ ≤ t2)
√n

Calderon Jonathan Página 60

Despeje μ el nivel de confianza va a quedar como
σ σ
1 – α = Pr(xr – t2 ∗ n ≤ μ ≤ xr + t1 * )
√ √n

En caso de ser el muestreo realizado sin reposición se tendrá que aplicar el

factor de corrección de población finita en cada uno de los errores de
σ
estimación “e = 𝑧2∗ ”
√n

Determinación del tamaño de la muestra en la estimación de µ

Se parte de la normalización de la variable aleatoria “xr”, es decir:

𝑥𝑟− µ
Z= σ
√n

Despejando n obtenemos que

𝑧²∗ σ²
n≥
𝑒²

Como se ve se necesita conocer de ante mano la desviación estándar, el

error de muestreo permitid, y el nivel de confianza que se determina a
partir de z.

Intervalo de confianza para estimar proporción poblacional “P”

Se usa la distribución normal en donde

Ø=P

Øs = p

K(Ø, Øs) ~ N(0,1)

Establecemos el nivel de confianza

Calderon Jonathan Página 61

 𝑝−𝑃
1 – α = Pr [z1 ≤ ≤ z2]
𝑝(1−𝑝)
√
𝑛

Despejando P obtenemos que

𝑝(1−𝑝) 𝑝(1−𝑝)
1 – α = Pr [p – z2*√ ≤ P ≤ p + z1* √ ]
𝑛 𝑛

Si multiplicásemos los limites por n obtendríamos convertiríamos la

ecuación del nivel de confianza es la estimación del nivel de confianza
para µ.

La determinación para el nivel de confianza de la proporción poblacional,

requiere que se tome una gran cantidad de elementos para la muestra.

Determinación del tamaño de la muestra en la estimación de P

Partiendo de la normalización de la variable aleatoria p

𝑝−𝑃
𝑍=
√𝑃(1 − 𝑃)
𝑛

Despejamos n y obtenemos que:

𝑧²∗𝑃(1−𝑃)
n= (𝑝−𝑃)²

Se suele utilizar a P = 0,50 para así poder dar un tamaño lo mayor posible
para la muestra.

Invervalo de confianza para estimar la varianza poblacional

De una poblacion normal con un n < 30 se usa “Chi cuadrado”(x²) en

donde

Ø = σ²

Øs = Ssomb²(Ss²)

Calderon Jonathan Página 62

 𝑆𝑠²(𝑛−1)
K(Øs, Ø) = ~ Chi cuadrado (n-1)
σ²

Armamos el intervalo de confianza

𝑆𝑠²(𝑛−1)
1-α = Pr[x1² ≤ ≤ x2²]
σ²

Despejando la varianza poblacional obtendremos

𝑆𝑠²(𝑛−1) 𝑆𝑠²(𝑛−1)
1 – α = Pr[ ≤ σ²≤ ]
𝑥2² 𝑥1²

Unidad 10: Contraste, Docima o Verificación de

hipótesis.
También llamada test de hipótesis, es un procedimiento de la inferencia
estadística para la toma de decisiones.

Decisión Estadística

Es una decisión que se toma respecto a la población en base a evidencias

proporcionadas por la muestra. Para ello se forman conjeturas sobre
algunas características de una distribución población llamada Hipótesis
Estadística.

Hipótesis Estadística

Suposiciones que se establecen con respecto al valor de un parámetro en

base a valores dados por la muestra, estas pueden ser:

• Hipótesis Nula (𝐻0 ): Indica que no se presentan cambios en la

población.

• Hipótesis Alternativa (𝐻1 ): Indica cambios o efectos que se

presentaron en la población.

Calderon Jonathan Página 63

Concepto de Docima

Experimento aleatorio que se realizar para decidir sobra la veracidad

sobre la hipótesis nula, es decir decidir si lo que establece la hipótesis nula
es cierto o falso dando paso al rechazo o no de la misma. Se maneja de la
siguiente manera

𝐻0 : Ø = Ø0

𝐻1 : Ø ≠ Ø0

Esto va de la mano con una probabilidad “α” llamado nivel de significancia

que representa la probabilidad de rechazar la hipótesis nula cuando esta
es verdadera, es decir α = Pr [𝐻0 𝑠𝑒𝑎 𝑟𝑒𝑐ℎ𝑎𝑧𝑎𝑑𝑎/ 𝐻0 𝑠𝑒𝑎 𝑐𝑖𝑒𝑟𝑡𝑎]. Todo
esto se realiza mediante estimaciones puntuales dentro de un intervalo de
confianza con sus respectivos puntos críticos.

Errores y sus probabilidades

A la hora de rechazar o aceptar una hipótesis nula se puede cometer los

siguientes errores:

• Error tipo 1: 𝐻0 𝑠𝑒𝑎 𝑟𝑒𝑐ℎ𝑎𝑧𝑎𝑑𝑎/ 𝐻0 𝑠𝑒𝑎 𝑐𝑖𝑒𝑟𝑡𝑎 y la probabilidad de

este es igual a α.
• Error tipo 2: 𝐻0 𝑛𝑜 𝑠𝑒 𝑟𝑒𝑐ℎ𝑎𝑧𝑒/ 𝐻0 𝑠𝑒𝑎 𝑓𝑎𝑙𝑠𝑎 y la probabilidad de
este es igual β.

Tanto α y β varían en sentido inverso y no se puede disminuir una sin

aumentar la otra. La única manera de hacer disminuir las probabilidades
de ambos a la vez es aumentar el tamaño de la muestra.

Análogamente “1 – α” representaría la zona de aceptación para la

hipótesis nula y”1 – β” representaría, por así decirlo, la decisión correcta
en donde se rechaza la hipótesis nula siendo esta falsa.

Calderon Jonathan Página 64

Tipos de docimas

Dado un parámetro población X y un valor particular 𝑋0 en el cual se

verifica la hipótesis nula, es decir 𝐻0 : X = X0 , se pueden plantear

• Docimas de hipótesis compuestas o inexactas: Es cuando se

contrasta un valor contra un conjunto de valores, esta se divide en
Docimas Bilaterales y Docimas laterales izquierdas o derecha.

• Docimas de hipótesis simples o exactas: Cuando se contrasta un

valor para la hipótesis nula contra un valor para la hipótesis alterna,
esta se divida en Docimas laterales izquierdas o derechas.

Docimas bilaterales (≠): Las hipótesis son puestas de la siguiente manera

𝐻0 : Ø = Ø0

𝐻1 : Ø ≠ Ø0

Considerando un estimador insesgado con distribución normal, podemos

decir que:

1 – α = Pr[ Øs1 ≤ Øs ≤ Øs2/H0 sea cierta]

α = Pr[Øs < Øs1] + Pr[Øs > Øs2]

β = Pr[Øs1≤ Øs≤ Øs2/H0 sea falsa ]

1 – β = Pr[Øs < Øs1]+ Pr[Øs > Øs2]

Docimas compuetas Laterales (<,>):

• Derecha (>): Las hipótesis son puestas de la siguiente manera

𝐻0 : Ø = Ø0

𝐻1 : Ø > Ø0
Considerando ahora solo un punto crítico (Øs*]) podemos decir que:
1-α = Pr[Øs ≤ Øs*/H0 es cierta]

Calderon Jonathan Página 65

 α = Pr[Øs > Øs*]
β = Pr[Øs ≤ Øs*/H0 sea falsa]
1-β = Pr[Øs > Øs*]

• Izquierda:
𝐻0 : Ø = Ø0
𝐻1 : Ø < Ø0

Considerado ahora un solo punto crítico (Øs*) podemos decir que:

1-α = Pr[Øs ≥ Øs*/ H0 sea cierta]

α = Pr[Øs < Øs*]
β = Pr[Øs ≥ Øs* /H0 sea falsa]
1-β= Pr[Øs < Øs*]

Docimas simples laterales: Opera de la misma manera que las Docimas

laterales compuestas solo que la forma de expresar las hipótesis es de la
siguiente manera

𝐻0 : Ø = Ø0
𝐻1 : Ø = Ø1

Siendo Ø1 un valor que se encuentre a la izquierda o derecha de el valor

de la hipótesis nula

Docimas para la media poblacional (µ)

Se trabaja con poblaciones normales y no normales en las cuales

podremos usar solamente la distribución de t de “student” y la
distribución normal.

Pasos para docimar: Los pasos son los mismos que la de la unidad anterior
solo que ahora se agregan las hipótesis, es decir

1. Identificar el parámetro a docimar (Ø)

2. Seleccionar un estimador (Øs)

Calderon Jonathan Página 66

 3. Determinar el estadístico K(Øs, Ø)
4. Calcular los puntos críticos K*
5. Plantear Hipótesis
6. Calcular las probabilidades involucradas

Se realiza el desarrollo para todos los tipos de docima.

Caso1: Varianza poblacional conocida con muestra de cualquier tamaño o

con n ≥ 30 (Para poblaciones no normales)

D. Simple Izquierda Derecha

Parámetro Ø=µ Ø=µ
poblacional, Øs = xr Øs = xr
su estadístico K(xr,µ)~ N(0,1) K(xr,µ)~ N(0,1)
y si
distribución
Planteo las 𝐻0 : µ = 𝜇0 𝐻0 : µ = 𝜇0
hipótesis 𝐻1 : µ = 𝜇1 En donde 𝜇1 < 𝜇0 𝐻1 : µ = 𝜇1 En donde 𝜇1 > 𝜇0
𝜎 𝜎
Calculo de xr* = 𝜇0 - 𝑍1−∝ ∗ xr* = 𝜇0 + 𝑍1−∝ ∗
√𝑛 √𝑛
puntos
críticos
Toma de xr ≥ xr* Acepto 𝐻0 xr ≤ xr* Acepto 𝐻0
decisión xr < xr* Rechazo 𝐻0 xr > xr* Rechazo 𝐻0

Como se dijo anteriormente hay dos tipos de errores cada uno con su
cálculo de probabilidad, para la media poblacional es de la siguiente
manera

• Derecha:
1-α = Pr [xr ≤ xr*/𝐻0 sea cierta]
α= Pr [xr > xr*]

β=Pr [xr≤ xr#/𝐻0 sea falsa]

1-β=Pr [xr > xr#]

• Izquierda:
1-α = Pr [xr ≥ xr*/𝐻0 sea cierta]

Calderon Jonathan Página 67

 α= Pr [xr < xr*]

β= Pr [xr ≥ xr#/𝐻0 sea falsa]

1-β= Pr [xr < xr#]

𝑥𝑟∗ −𝜇1
Siendo xr# = 𝜎 para ambos casos.
⁄
√𝑛

D. Izquierda Derecha
Compuesta
Parámetro Ø=µ Ø=µ
poblacional, Øs = xr Øs = xr
su estadístico K(xr,µ)~ N(0,1) K(xr,µ)~ N(0,1)
y si
distribución
Planteo las 𝐻0 : µ = 𝜇0 𝐻0 : µ = 𝜇0
hipótesis 𝐻1 : µ < 𝜇0 𝐻1 : µ > 𝜇0
𝜎 𝜎
Calculo de xr* = 𝜇0 - 𝑍1−∝ ∗ xr* = 𝜇0 + 𝑍1−∝ ∗
√𝑛 √𝑛
puntos
críticos
Toma de xr ≥ xr* Acepto 𝐻0 xr ≤ xr* Acepto 𝐻0
decisión xr < xr* Rechazo 𝐻0 xr > xr* Rechazo 𝐻0

El cálculo se sus probabilidades es igual al de la Docima simple

Docima compuesta bilateral

1. Parámetro poblacional, estadístico y distribución:

Ø=µ
Øs = xr
K (xr,µ)~ N(0,1)

2. Planteo de hipótesis
𝐻0 : µ = 𝜇0
𝐻1 : µ ≠ 𝜇0

Calderon Jonathan Página 68

 3. Calculo de puntos críticos
𝜎
𝑥𝑟1∗ = 𝜇0 − 𝑧1−∝ ∗
2 √𝑛

𝜎
𝑥𝑟2∗ = 𝜇0 + 𝑧1−∝ ∗
2 √𝑛

Recuerde que al ser bilateral hay un intervalo definido por dos

puntos a diferencia de los laterales que se encuentran definido con
un punto y ± ∞.
4. Toma de decisiones
𝑥𝑟1∗ ≤ 𝑥𝑟 ≤ 𝑥𝑟2∗ −→ 𝐴𝑐𝑒𝑝𝑡𝑜 𝐻0

𝑥𝑟 < 𝑥𝑟1∗ ∧ 𝑥𝑟 > 𝑥𝑟2∗ −→ 𝑅𝑒𝑐ℎ𝑎𝑧𝑜 𝐻0

5. Cálculo de probabilidades

1−∝ = Pr[𝑥𝑟1∗ ≤ 𝑥𝑟 ≤ 𝑥𝑟2∗ / 𝐻0 𝑠𝑒𝑎 𝑐𝑖𝑒𝑟𝑡𝑎 ]

∝= Pr[𝑥𝑟 < 𝑥𝑟1∗ ] + Pr[𝑥𝑟 > 𝑥𝑟2∗ ]

𝛽 = Pr[[𝑥𝑟1∗ ≤ 𝑥𝑟 ≤ 𝑥𝑟2∗ / 𝐻0 𝑠𝑒𝑎 𝑓𝑎𝑙𝑠𝑎]

1 − 𝛽 = Pr[𝑥𝑟 < 𝑥𝑟1∗ ] + Pr[𝑥𝑟 > 𝑥𝑟2∗ ]

Caso2: Varianza poblacional desconocida con un n < 30

Seguimos los mismos pasos anteriores pero la distribución del estadístico

𝑥𝑟−𝜇
K (xr,µ) = 𝜎 ~ 𝑡𝑛−1
√𝑛

Docima para la proporción poblacional (P)

Calderon Jonathan Página 69

Se procederá a dar la proporción poblacional en cada uno de los tipos de
docima, en donde cada uno de ellos hace uso de la distribución normal y
se siguen los pasos que se describieron en la media poblacional.

D. simple Izquierda Derecha

Parámetro Ø=P Ø=P
poblacional, Øs = p Øs = p
su estadístico K(p,P)~ N(0,1) K(p,P)~ N(0,1)
y si
distribución
Planteo las 𝐻0 : P = 𝑃0 𝐻0 : P = 𝑃0
hipótesis 𝐻1 : P = 𝑃1 en donde 𝑃1 < 𝐻1 : P = 𝑃1 en donde 𝑃1 >
𝑃0 𝑃0
Calculo de 𝑃0 (1− 𝑃0 ) 𝑃0 (1− 𝑃0 )
puntos p* = 𝑝0 - 𝑍1−∝ ∗ √ p* = 𝑝0 + 𝑍1−∝ ∗ √
𝑛 𝑛
críticos
Toma de p ≥ p* Acepto 𝐻0 p ≤ p* Acepto 𝐻0
decisión p < p* Rechazo 𝐻0 p > p* Rechazo 𝐻0

Cálculo de probabilidades

• Derecha:
1 − 𝛼 = Pr[𝑝 ≤ 𝑝∗ / 𝐻0 𝑠𝑒𝑎 𝑐𝑖𝑒𝑟𝑡𝑎]

𝛼 = Pr[𝑝 > 𝑝∗ ]

𝛽 = Pr[𝑝 ≤ 𝑝# / 𝐻0 𝑠𝑒𝑎 𝑓𝑎𝑙𝑠𝑎]

1 − 𝛽 = Pr[𝑝 > 𝑝# ]

• Izquierda:
1 − 𝛼 = Pr[𝑝 ≥ 𝑝∗ / 𝐻0 𝑠𝑒𝑎 𝑐𝑖𝑒𝑟𝑡𝑎]

𝛼 = Pr[𝑝 < 𝑝∗ ]

Calderon Jonathan Página 70

 𝛽 = Pr[𝑝 ≥ 𝑝# / 𝐻0 𝑠𝑒𝑎 𝑓𝑎𝑙𝑠𝑎]

1 − 𝛽 = Pr[𝑝 < 𝑝# ]

# 𝑝∗ −𝑃1
Siendo 𝑝 =
𝑃 (1−𝑃1)
√ 1
𝑛

D. simple Izquierda Derecha

Parámetro Ø=P Ø=P
poblacional, Øs = p Øs = p
su estadístico K(p,P)~ N(0,1) K(p,P)~ N(0,1)
y si
distribución
Planteo las 𝐻0 : P = 𝑃0 𝐻0 : P = 𝑃0
hipótesis 𝐻1 : P < 𝑃0 𝐻1 : P > 𝑃0
Calculo de 𝑃0 (1− 𝑃0 ) 𝑃0 (1− 𝑃0 )
puntos p* = 𝑝0 - 𝑍1−∝ ∗ √ p* = 𝑝0 + 𝑍1−∝ ∗ √
𝑛 𝑛
críticos
Toma de p ≥ p* Acepto 𝐻0 p ≤ p* Acepto 𝐻0
decisión p < p* Rechazo 𝐻0 p > p* Rechazo 𝐻0

El cálculo de probabilidades es exactamente igual que el de las Docimas

simples

Docima compuesta bilateral

1. Parámetro, estimador y estadístico

Ø=P
Øs = p
𝑝−𝑃
K (Øs,Ø) = ~ N(0,1)
𝑃(1−𝑃)
√
𝑛

2. Planteo de hipótesis
𝐻0 : P = 𝑃0
𝐻1 : P ≠ 𝑃0

Calderon Jonathan Página 71

 3. Calculo de puntos críticos

𝑃0 (1 − 𝑃0 )
𝑝1∗ = 𝑝0 − 𝑍1−𝛼 ∗ √
2 𝑛

𝑃0 (1 − 𝑃0 )
𝑝1∗ = 𝑝0 + 𝑍1−𝛼 ∗ √
2 𝑛

4. Toma de decisión
𝑝1∗ ≤ 𝑝 ≤ 𝑝2∗ −→ 𝐴𝑐𝑒𝑝𝑡𝑜 𝐻0

𝑝 < 𝑝1∗ ∧ 𝑥𝑟 > 𝑝2∗ −→ 𝑅𝑒𝑐ℎ𝑎𝑧𝑜 𝐻0

5. Cálculo de probabilidades

1 − 𝛼 = Pr[𝑝1∗ ≤ 𝑝 ≤ 𝑝2∗ / 𝐻0 𝑠𝑒𝑎 𝑐𝑖𝑒𝑟𝑡𝑎]

𝛼 = Pr[𝑝 < 𝑝1∗ ] + Pr[𝑝 > 𝑝2∗ ]

𝛽 = Pr[𝑝1# ≤ 𝑝 ≤ 𝑝2# / 𝐻0 𝑠𝑒𝑎 𝑓𝑎𝑙𝑠𝑎]

1 − 𝛽 = Pr[𝑝 < 𝑝1# ] + Pr[𝑝 > 𝑝2# ]

Siendo
𝑝1∗ −𝑃1
𝑝1# =
𝑃 (1−𝑃1)
√ 1
𝑛

𝑝2∗ − 𝑃1
𝑝2# =
√𝑃1 (1 − 𝑃1 )
𝑛

Calderon Jonathan Página 72

Curva operatoria (OC) y Curva de potencia
Esto va ligado con el concepto de α y β, solo aplicable a Docimas
compuestas que como ya se dijo exponen al parámetro a un conjunto de
valores teniendo en mente esto definiremos entonces

• Curva potencia: Es la que relaciona todos los valores posibles del

parámetro con la probabilidad de rechazar 𝐻0 para un determinado
nivel de significación α
• Curva operatoria (OC): Es la que relaciona todos los valores posibles
del parámetro con la probabilidad de aceptar 𝐻0 para un
determinado nivel de significación α

Calderon Jonathan Página 73