Tp De Sintaxis

Sintaxis y semántica de los lenguajes.

Resolución:

2.1)
α = 01 ; β = 21 ; γ = 011 ; Σ = { 01, 1, 2 };

a) αβ = 0121; αβγ = 0121011; α3 = 010101; γ2 = 011011;(βγ)2= 2101121011;
b) long = 4; 3; 6; 6; 10;
c) (αβ)-1 =1210; (αβγ)-1 = 1101210; (α3)-1 = 101010; (γ2)-1 = 110110; (βγ2)-1 = 1101211012;

2.2)
Σ = { x, y, z }
L0 = {}
L1 = {x, y,z}
L2 = {xy, xz, xx, yx, yz, yy, zx, zy, zz}
L3 = {xxx, xxy, xxz, xyx, xyy, xyz, xzx, xzy, yxx, yx, …} = {Todas las palabras de longitud menor igual que tres de ‘x’,’y’ y ‘z’ incluida la palabrasvacía y sus unisimbólicos}

a) Para una longitud de palabra Wn la cantidad de cadenas que se pueden formar son 3n.
b) Para una longitud ‘n’ con ‘m’ símbolos se pueden formar mn palabras de esalongitud. Además las longitudes inferiores mn-1.
c) {x, y,z, xy, xz, yx, yz, zx, zy} Esas serían las palabras generables con la restricción de no repetir símbolos. En Total 9.

2.3) L = { xx, λ }.L n para n = 0,1,2,3. Obtener diámetro de Ln para cualquier ‘n’.

L0 = {};
L1 = {xx, λ};
L2 = {xx, xxxx, λ };
L3 = {xx, xxxx, xxxxxx};

a) La cantidad de elementos de ‘L’ para cualquier‘n’ es igual a ‘n+1’.
b) Los elementos de L son las concatenaciones de ‘x’ de longitud par menor e igual que 6 y la palabra vacía.

2.4) W = W-1 (W)n = (W-1)n Es palíndromo para todo ‘n’.2.5)
L1 = {a, ab};
L2 = {a, ba, λ};
L3 = {a, b, λ };
L4 = {ab, ba };
L5 = { aa, bb};
L1* = {λ, a, ab, aab, aba, abaa, abab, aaab, ababab, …}
L1* = {Todas las combinaciones de ‘a’y ‘b’ que no tienen dos ‘b’ consecutivas y que comienzan con ‘a’. Incluso la unisimbolica de ‘a’ y la palabra λ}.

L2+ = {a, ba, λ, aba, baa, aaba, baaa, baba, abaaa, ababa …}
L2+ = {Lascombinaciones de ‘a’ y ‘b’ que no poseen dos ‘b’ consecutivas. Incluso la unisimbolica ‘a’ y la palabra λ}

L1* ∩ L2+ = L2+

L23 = {a, ba, λ}.{a, ba, λ}.{a, ba, λ} = {a, ba, λ, aa, aba, baa,...