Cheatography
https://cheatography.com
Abarca los temas de lenguajes formales y autómatas, máquinas de Turing y computabilidad a través de la decibilidad.
This is a draft cheat sheet. It is a work in progress and is not finished yet.
Lenguajes
|
Definición: Un lenguaje sobre el alfabeto A es un subconjunto de las cadenas sobre
A (L ⊆ A*).
|
|
Concatenación: Dados dos lenguajes L1 y L2 definidos sobre el alfabeto A:
L1L2={u1u2 | u1∈L1 y u2∈L2}
Propiedades:
LØ = ØL = Ø
{ε}L = L{ε} = L
L1(L2L3) = (L1L2)L3
|
|
Operaciones: Unión:
L1 ∪ L2 = {x | x ∈ L1 o x ∈ L2}
Intersección:
L1 ∩ L2 = {x | x ∈ L1 y x ∈ L2}
Diferencia:
L1 - L2 = {x | x ∈ L1 y x ∉ L2}
|
|
Clausuras: Kleene: L* = ∪ Li con i ≥ 0
Positiva: L+ = ∪ Li con i ≥ 1
|
|
|
Gramáticas formales
|
Definición formal: Cúadrupla (V, T, P, S) donde:
V -> Símbolos no terminales
T -> Símbolos terminales
P -> Reglas de producción (α -> β)
S -> Símbolo inicial o de partida
|
|
Jerarquía de Chomsky (tipos): Tipo 0: Estructura de frase
Al menos un no terminal a la izquierda
A -> aABC | abC
cB -> BC
bB -> bb
bC -> b
Tipo 1: Dependientes de contexto
Un no terminal da lugar a una serie de símbolos cuando está en un contexto determinado
S -> aSBC | aBC
CB -> BC
aB -> ab
bB -> bb
bC -> bc
cC -> cc
TIpo 2: Libres de contexto
A -> α
S -> aSb | ab
Tipo 3: Regulares
A -> uB o A-> u
A -> B1 | 1
B -> A0
|
|
Limpieza de Gramáticas: Elimina producciones y símbolos inútiles:
No derivables en símbolo terminal y no alcanzables desde símbolo inicial.
Eliminar producciones nulas:
A -> ε
Eliminar producciones unitarias:
A -> B
|
|
|
|
