Unidad 2 Flashcards
(29 cards)
Alfabeto
Cualquier conjunto finito y no vacío de símbolos. Se usarán en adelante para denotarlos, las letras griegas mayúsculas con o sin subíndices.
Alfabetos segun la teoria de conjuntos
- Dos alfabetos son iguales si y solo si tienen exactamente los mismos símbolos, sin considerar el orden de presentación de los mismos o las repeticiones que pudieran mostrarse.
- Si todos los símbolos de un alfabeto Ω1 están también en otro alfabeto Ω2, se dice que el primero está incluido en el segundo y se lo denota Ω1 ⊆ Ω2 también se dice que Ω1 es un subconjunto de Ω2. Si además, el segundo alfabeto posee al menos un
símbolo que el primero no tiene, estrictamente incluido en el segundo, denotándose en este caso Ω1 ⊂ Ω2 - El cardinal de un alfabeto dado Ω, denotado |Ω|, es la cantidad de símbolos que el mismo
posee.
Palabra, cadena, tira o string
Una palabra definida sobre un alfabeto E es cualquier secuencia finita de símbolos de E, escritos uno a continuación del otro.
potenciación de símbolos de un alfabeto y se lo define recursivamente de la siguiente forma
Longitud de una 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
Como se anticipó, se denota con λ (lambda) a la palabra vacía, palabra que no tiene símbolos y
cuyo largo es cero: |λ| = 0.
Partes de una palabra
si dos palabras pueden concatenarse y se puede separar en simbolos y subpalabras.
w = axb
Sufijos y prefijos
Operaciones con alfabetos
como conjuntos que son:
- unirse Σ1∪Σ2={todos los símbolos comunes y no comunes de ambos alfabetos}
- intersectarse Σ1∩Σ2={todos los símbolos comunes a ambos alfabetos}
- restarse Σ1−Σ2={todos los símbolos del primer alfabeto que no estén en el segundo}
- complementarse Σ1 (en este caso, deberemos definir el universal contra el cual complementar).
concatenación de Σ1 y Σ2, denotada Σ1°Σ2 o simplemente Σ1Σ2, es el conjunto de palabras formadas por la concatenación de cada símbolo de Σ1 con cada uno de Σ2, en ese orden.
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: L ⊆ Σ*
Operaciones con lenguajes
Si L1 y L2 son lenguajes definidos sobre el alfabeto Σ, entonces también lo son:
- unión L1UL2
- intersección L1nL2
- resta L1−L2
- concatenación L1°L2
- complemento L1
Descripción de lenguajes
el concepto más general y simple de lenguaje como un conjunto de palabras. Como todo conjunto, un lenguaje puede definirse o determinarse:
- Por extensión o enumeración, indicando una por una todas las palabras que son elementos del mismo.
- Por comprensió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 BNF2 de la siguiente forma:
α := β y la leeremos alfa produce beta o también alfa puede reescribirse como
beta.
Gramática formal Chomsky
Una gramática formal G es una cuádrupla (ΣT, ΣN, S, P), en la cual sus cuatro componentes
representan:
- ΣT es el alfabeto de los símbolos que formarán las cadenas del lenguaje y es denominado alfabeto de símbolos terminales
- ΣN conjunto de variables o símbolos auxiliares llamado alfabeto de símbolos no terminales
- S∈ΣN 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.
forma de Backus-Naur
- Una producción se escribe como un símbolo no terminal A en el lado izquierdo encerrado entre corchetes angulares, el símbolo de producción y una cadena de terminales y no terminales de cualquier largo como lado derecho:
<a>:= β
2. En caso de existir varias producciones con el mismo lado izquierdo <a>:= β1, <a>:= β2,…, <a>:= βn y distintos lados derechos, se las escribe todas juntas utilizando la barra vertical como separador:
<a>:= β1 | β2 | … | βn</a></a></a></a></a>
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 puedan derivarse desde el axioma S
utilizando las reglas de producción de P.
Equivalencia de gramáticas
Digamos por ahora que dos gramáticas G1=(ΣT1, ΣN1, S1, P1) y G2=(ΣT2, ΣN2, S2, P2) son equivalentes si y solo si generan exactamente el mismo lenguaje.
Gramáticas Tipo 0 (Lenguajes Recursivamente Enumerables)
- Son las más generales y pueden describir cualquier lenguaje que pueda ser reconocido por una Máquina de Turing.
- Sus reglas pueden tener cualquier forma:
Donde α y β son cadenas de símbolos.α→β - No existen restricciones sobre la forma de las reglas de producción.
- Las producciones pueden contener cualquier cadena de terminales y no terminales tanto en
lado izquierdo como en el lado derecho, con al menos un símbolo no terminal en el lado izquierdo
Gramáticas Tipo 1 (Sensibles al Contexto)
- Sus reglas de producción tienen la forma:
Donde A es un símbolo no terminal, y γ es una cadena no vacía.
αAβ→αγβ - El tamaño de la parte derecha (γ) siempre debe ser mayor o igual que la parte izquierda.
- Pueden ser reconocidas por una Máquina de Turing con espacio acotado.
- son lenguajes que permiten el reemplazo contextual de símbolos no terminales.
Gramáticas Tipo 2 (Libres de Contexto)
S := λ ó A := α A∈ΣN, α∈(ΣTUΣN)^+
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, y de allí el nombre del lenguaje.
Gramáticas Tipo 3 (Regulares)
un solo No Terminal del lado izquierdo y en su lado derecho tienen un terminal solo o un terminal y un no terminal, siendo estas regulares por izquierda o regulares por derecha
Aplicaciones de las Gramáticas Formales
- Compiladores: Los lenguajes de programación se definen con gramáticas tipo 2 (libres de contexto).
- Procesamiento de Lenguaje Natural: Se usan para modelar estructuras sintácticas del lenguaje humano.
- Expresiones Regulares: Basadas en gramáticas regulares (tipo 3), se usan en búsqueda y manipulación de texto.
- Inteligencia Artificial: Modelado de lenguaje y generación de texto.
Lenguajes regulares
Los lenguajes regulares admiten la siguiente definición recursiva:
a) Cualquier lenguaje finito (con un número natural de cadenas) L₁ definido sobre algún alfabeto Σ, es regular.
b) Si L₁ y L₂ son lenguajes regulares, entonces también lo son su unión L₁ ∪ L₂ y su concatenación L₁·L₂.
c) Si L₁ es un lenguaje regular, entonces su estrella de Kleene L₁*, también es un lenguaje regular.
d) Solo son lenguajes regulares, los construidos con a), b) y c).
Gramática limpia
es una gramática formal que no contiene símbolos o producciones innecesarias, es decir, todos sus símbolos y reglas contribuyen efectivamente a generar alguna cadena del lenguaje.
Una gramática se considera limpia cuando cumple con estas dos condiciones:
No tiene símbolos no generadores: Todos los símbolos no terminales pueden derivar (de forma directa o indirecta) una cadena de terminales.
No tiene símbolos no alcanzables: Todos los símbolos no terminales pueden ser alcanzados desde el símbolo inicial mediante una secuencia de derivaciones.
Gramática bien formada
Una gramática bien formada es una gramática formal G=(N,Σ,P,S) que cumple con las siguientes condiciones:
Estructura formal válida:
N: conjunto finito de no terminales.
Σ: conjunto finito de terminales, disjunto de N.
P: conjunto finito de producciones de la forma A→α, con A∈N y α∈(N∪Σ) ∗.
S∈N: símbolo inicial.
Producciones coherentes:
Todas las producciones están correctamente formuladas.
Solo se utilizan símbolos que pertenecen a N∪Σ.
Sin símbolos inútiles (gramática limpia):
Todo símbolo no terminal debe ser:
Generador: puede derivar (directa o indirectamente) a una cadena de terminales.
Alcanzable: puede derivarse desde el símbolo inicial 𝑆.
Árbol de derivación
forma pictórica de representar una derivación: el árbol de derivación o árbol de análisis sintáctico de la cadena.
Al derivar una cadena de un lenguaje generado por una gramática, siempre debe iniciarse el proceso partiendo del axioma, aplicando al mismo una producción que lo tenga como lado izquierdo.
