Skip to content
This repository was archived by the owner on Oct 17, 2025. It is now read-only.

helcsnewsxd/formal-languages-and-computability-subject

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

72 Commits
clases
clases
 
 
final
final
 
 
.gitignore
.gitignore
 
 
LICENSE
LICENSE
 
 
README.md
README.md
 
 

Repository files navigation

Note

This repository contains theoretical notes and practical exercises from the Formal Languages and Computability course of the Computer Science degree at FAMAF – Universidad Nacional de Córdoba.

All materials are in Spanish, as they were created for academic use and course submission.

Lenguajes Formales y Computabilidad

Edición 2024

Repositorio que contiene todo el material correspondiente a la materia de Lenguajes Formales y Computabilidad de 4to año de la Licenciatura en Ciencias de la Computación de FAMAF.

Equipo Docente

  • Teóricos: Diego Vaggione
  • Prácticos: Martín Vilela y Mariana Badano

Material de Estudio

Guías y Resúmenes

Unidad Tema Material Resumen
1 Notación + Conceptos básicos + Funciones/Conjuntos $\Sigma$-mixtos + Notación $\lambda$ Guía 1 MD y PDF
2 Infinituplas + Órdenes totales + Orden natural sobre $\Sigma^*$ Guía 2 MD y PDF
3 Procedimientos efectivos + Funciones/Conjuntos $\Sigma$-efectivamente computables + Conjuntos $\Sigma$-efectivamente enumerables Guía 3 MD y PDF
4 Paradigma de Turing (Máquina de Turing + Funciones $\Sigma$-Turing computables) Guía 4 MD y PDF
5 Paradigma de Godel (Funciones/Conjuntos $\Sigma$-recursiva y recursivas primitivas) Guía 5 MD y PDF
6 Sumatoria, productoria, concatenatoria, cuantificación acotada de predicados y minimización de funciones $\Sigma$-recursivas + Conjuntos $\Sigma$-recursivamente enumerables + Independencia del alfabeto Guía 6 MD y PDF
7 Paradigma imperativo de Neumann: El lenguaje $S^{\Sigma}$ (Funciones/Conjuntos $\Sigma$-computables + Conjuntos $\Sigma$-enumerables + Macros) Guía 7 MD y PDF
8 Comparación entre paradigmas + Tesis de Church Guía 8 MD y PDF
9 Resultados básicos de computabilidad Guía 9 MD y PDF

Lista de Combos (Examen Final - Parte Teórica)

Definiciones y convenciones notacionales

Combo Tema Material
1 Conjunto $\Sigma$-r, $\langle s_1,s_2,..\rangle$, función $\Sigma$-mixta, "familia $\Sigma$-indexada de funciones", $R(f,\mathcal{G})$ LyX y PDF
2 $d\overset{n}{\vdash}d'$, $L(M)$, $H(M)$, "función de tipo $(n,m,s)$ ", $(x)$, $(x)_i$ LyX y PDF
3 Conjunto $\Sigma$-r.e., $s^\leq$, $*^\leq$, $\#^\leq$ LyX y PDF
4 Función $\Sigma$-efectivamente computable y procedimiento efectivo que la computa LyX y PDF
5 Conjunto $\Sigma$-efectivamente computable y procedimiento efectivo que decide la pertenencia LyX y PDF
6 Conjunto $\Sigma$-efectivamente enumerable y procedimiento efectivo que lo enumera LyX y PDF
7 Función $\Sigma$-Turing computable y máquina que la computa LyX y PDF
8 $M(P)$, $Lt$, conjunto rectangular, conjunto de tipo $(n,m)$ LyX y PDF
9 " $I$ es instrucción de $S^\Sigma$ ", $\mathcal{P}$ es programa de $S^\Sigma$, $I_i^\mathcal{P}$, $n(\mathcal{P})$, $Bas$ LyX y PDF
10 (Relativo a $S^\Sigma$) "Estado", "descripción instantánea", $S_\mathcal{P}$, "estado obtenido luego de $t$ pasos", " $\mathcal{P}$ se detiene luego de $t$ pasos" LyX y PDF
11 $\Psi_\mathcal{P}^{n,m,\#}$, función $\Sigma$-computable y programa que la computa, $M^\leq(P)$ LyX y PDF
12 Conjunto $\Sigma$-computable, conjunto $\Sigma$-enumerable y programa que lo enumera LyX y PDF
13 $i^{n,m}$, $E_{\#}^{n,m}$, $E_*^{n,m}$, $E_{\#j}^{n,m}$, $E_{*j}^{n,m}$, $Halt^{n,m}$, $T^{n,m}$, $AutoHalt^\Sigma$ y los conjuntos $A$ y $N$ LyX y PDF
14 Notación lambda LyX y PDF
15 Macro de asignación LyX y PDF
16 Macro IF LyX y PDF

Teoremas

Combo Tema Material
1 Caracterización de conjuntos p.r., Neumann vence a Godel LyX y PDF
2 Lema de división por casos para funciones p.r., Caracterización básica de conjuntos enumerables LyX y PDF
3 Godel vence a Neumann, Caracterización de conjuntos efectivamente computables LyX y PDF
4 Caracterización básica de conjuntos enumerables, Lema de la sumatoria LyX y PDF
5 Lema de intersección de conjuntos $\Sigma$-efectivamente enumerables, Lema de cuantificación acotada LyX y PDF
6 Efectivamente computable implica efectivamente enumerable, Caracterización de conjuntos r.e. LyX y PDF
7 Lema de minimización acotada, función con clausura LyX y PDF
8 $AutoHalt^\Sigma$ no $\Sigma$-r., $AutoHalt^\Sigma$ no $\Sigma$-efectivamente computable, $A$ $\Sigma$-r.e. y no $\Sigma$-r. y $N$ no $\Sigma$-r.e., Neumann vence a Godel LyX y PDF
9 Lema de división por casos para funciones recursivas, $Halt^{n,m}$ es $(\Sigma\cup\Sigma_p)$-p.r., $T^{n,m}$ es $(\Sigma\cup\Sigma_p)$-r. LyX y PDF

About

Exercises and theory notes - Formal Languages and Computability course - Computer Science @ FAMAF (UNC)

Topics

turing-machines formal-languages theory-of-computation computability-theory famaf university-subject

Resources

Readme

License

MIT license
Activity

Stars

1 star

Watchers

1 watching

Forks

0 forks
Report repository