Autómatas formales

Autómatas y Lenguajes Formales 1. Lenguajes Formales
Dr. Ricardo Pérez Aguila Universidad Tecnológica de la Mixteca

1.1 Conceptos Básicos
Definición:
Un alfabeto es un conjunto finito no vacío de símbolos. Se le denota por Σ.

Definición:
Un lenguaje L sobre un alfabeto Σ es un conjunto de cadenas finitas formadas por elementos de Σ. Las cadenas en un lenguaje son llamadas tambiénsentencias.
Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Ejemplo:
Sea Σ = {0,1} Dos lenguajes sobre Σ podrían ser:
L1 = {0, 01, 110} L2 = {c: c es una cadena con n 0’s y n 1’s, n ≥ 1} = {01, 0011, 010101, 0000011111, …}

De hecho:
Card(L1) = 3 Card(L2) = ∞
Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Definición:
Sean σ= x1x2x3…xn y τ = y1y2y3…ym cadenas. La concatenación de σ y τ, denotada por στ, es la cadena στ = x1x2x3…xny1y2y3…ym

Ejemplo:
Sean σ = 01011 y τ = 001 entonces
στ = 01011001 τσ = 00101011

Propiedad: στ ≠ τσ
Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Definición:
Sea x un símbolo. xn denota a la cadena

xxx...x
n

Ejemplo:
α5 = ααααα
Dr.Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Definición:
La longitud de una cadena σ es el número de símbolos que forman a σ.

Ejemplo:
La longitud de la cadena σ = abc3628 es 7.
Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos

Definición:
La cadena vacía es aquella cuya longitud es cero (no tiene símbolos) y se le denota porλ.

Dr. Ricardo Pérez Aguila

Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Propiedad:
Sea σ una cadena. Entonces: σλ = λσ = σ Sea x un símbolo. Entonces: x0 = λ
Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Definición:
Sea Σ un alfabeto.
El lenguaje formado por todas las posibles cadenas con símbolos tomados de Σ, incluyendo a la cadenavacía, se le denota por Σ*. El lenguaje formado por todas las posibles cadenas con símbolos tomados de Σ, excluyendo a la cadena vacía, se le denota por Σ+.

Dr. Ricardo Pérez Aguila

Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Definición:
Una gramática G se compone de cuatro objetos:
1) Un alfabeto Σ cuyos elementos son llamados símbolos terminales. El lenguaje de la gramática soncadenas formadas por símbolos en Σ. 2) Un conjunto finito no vacío de símbolos N tal que N ∩ Σ = ∅. Los elementos de N son llamados símbolos no terminales o variables. 3) Un símbolo S ∈ N será llamado símbolo inicial.
Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
4) Un conjunto P cuyos elementos serán llamados producciones, reglas de producción o reglas desustitución. Una producción es una expresión de la forma A → x1x2…xn tal que A es un símbolo no terminal y x1x2…xn es una cadena finita de terminales o no terminales, es decir, xi ∈ Σ ∪ N, i = 1, 2, …, n. También se aceptan producciones de la forma A→λ Una gramática G es entonces denotada como G = {Σ, N, S, P} Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Ejemplo:Sea G1 = {Σ, N, S, P} la gramática dada por:
Σ = {a, b, c} N = {S, A, B, C} Símbolo inicial: S P se forma por las producciones:
S → AaB S→B A → aB A→a B → bC C → ac C→λ Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Definición:
Sea G = {Σ, N, S, P} una gramática. Una sentencia de G es cualquier cadena x1x2…xn de símbolos tal que xi ∈ Σ ∪ N, i = 1, 2, …, n.Una sentencia puede ser también la cadena vacía.

Ejemplo:
Las siguientes son sentencias de la gramática G1:
AaB, λ, AABBcc, etc.
Dr. Ricardo Pérez Aguila Autómatas y Lenguajes Formales

1.1 Conceptos Básicos
Definición:
Sea G = {Σ, N, S, P} una gramática. Sea σ una sentencia de la forma σ = γ1Aγ2 donde γ1 y γ2 son también sentencias y A es un símbolo no terminal. Supóngase que la...