Metonymie.com :: Apuntes » 2008 » September
Bloque de Colores

Macros en C

Icono de Post September 21 2008 :: c ::

Los Macros (asi como los includes) se manejan en el preprocesador de C que es un paso anterior separado de la compilación. Y permiten basicamente la definición de un termino que será remplazando siempre en el momento de la compilación por la expresión que se defina. El ejemplo típico es la definición de constantes, ej:


#define MAX_SIZE 1000

Macros con Variables

También pueden usarse Macros con variables, ej:


#include <stdio.h>
#define max(A, B) ((A) > (B) ? (A):(B))
int main() {
	int x = 20;
	int y = 10;
	int z;

	//Gets transformed to z = ((x + y) > (y - 10) ? (x + y):(y - 10));
	z = max(x + y, x - 10);
	//prints 30
	printf("%dn", z);

	//Gets transformed to z = ((++x) > (++y) ? (++x):(++y);
	z = max( ++x, ++y);
	// ++ is doubly evaluated
	//So x and y are doubly incremented
	//prints 22
	printf("%dn", z);

}

Nota: Hay que tener cuidado con los efectos secundarios que se pueden causar ver ejemplo de ++x

Cuidado con comerse los parentesis y los efectos secundarios que se pueden causar


#include <stdio.h>
#define square(x) x * x
#define square_works(x) (x) * (x);

int main() {
	int x = 20;
	int y = 10;
	int z;

	//Gets transformed to z = x + y * x + y
	//And because of precedence order is z = x + (y * x) + y
	z = square(x + y);
	//prints 230
	printf("%dn", z);

	//Gets transformed to z = (x + y) * (x + y)
	z = square_works(x + y);
	//prints 900
	printf("%dn", z);

}

Para desdefinir un Macro se puede usar undef y se puede usar ( también para includes o defines ) estructuras condicionales con if, ej:


#if SYSTEM_BITS == 64
	#define MAX_SIZE = 2^63
#elif
	#define MAX_SIZE = 2^31
#endif

Referencias

The C Programming Language, Segunda Edición; Kernighan, Ritchie; Prentice Hall Hispanoamerica, 1991

Alcance de Variables en C

Icono de Post September 20 2008 :: c ::

Este post es similar en temática a mis posts de OOP y Javascript Global Variables Weirdness salvo que sobre C.

Variables Automáticas

Se utilizan dentro del contexto de un bloque de código. Se inicializan y destruyen cuando termina el código de ese bloque. El típico ejemplo es las variables dentro de una función.


int main() {
	double i;
	.......
	my_function();
	....
}
int my_function() {
	int i = 15;
	......
}

En este ejemplo, la variable i de la función my_function es independiente de la i de la función main.

Variables Globales

Son accesibles y compartidas por todas las funciones definidas dentro de un archivo. Ej:


#include <stdio.h>
int i = 0;
int main() {
	printf("%d ", i);
	i++;
	my_function();
	printf("%d ", i);
}
int my_function() {
	printf("%d ", i);
	i = 15;
}

Imprime


0 1 15

Variables Externas

Si se quiere utilizar una variable global definida en un archivo externo, es necesario declararla usando extern . Ej:

Archivo vars-1.c


int i = 15;

Archivo vars-2.c


#include <stdio.h>
extern int i; 

int main() {
	printf("%d ", i);
	i++;
	printf("%d ", i);
	return 1;
}

Nota: Para compilar múltiples archivos ver Compiling multiple source files. En este caso se uso: gcc -Wall vars-1.c vars-2.c -o "vars"

Se podría haber usado la variable dentro de un bloque de código, por ejemplo una función, para lo que es necesario hacer un archivo de header:

Archivo vars.h

void my_function();

Archivo vars-1.c


int i = 15;
char ch = 'a';

Archivo vars-2.c


#include <stdio.h>
#include "vars.h"
extern int i; 

int main() {
	printf("%d ", i);
	i++;
	printf("%d ", i);
	my_function();
	return 1;
}
void my_function(){
	extern char ch;
	printf("%c ", ch);
}

El archivo de header solamente tiene el prototipo de la función.

Variables Estáticas

Hace que una variable global limita su alcance al archivo en el que esta declarada. Por otro lado usada, dentro de una función, mantiene su valor en las diferentes llamadas a la función. El ejemplo típico es una función recursiva:


#include <stdio.h>
void my_function( int a );
int main() {
	my_function(0);
	printf("n");
	my_function( 10 );
}
void my_function( int a ) {
	static int i;
	int b = 10;
	i += a;
	printf("| %d - %d |t", i);
	i++;
	b++;
	if( i < 5 ) my_function( 0 );
}

Devuelve:


| 0 - 10 |	| 1 - 10 |	| 2 - 10 |	| 3 - 10 |	| 4 - 10 |
| 15 - 10 |

Nota: Las variables estáticas se inicializan en 0.

Nota: Cada vez que se llama a una función sus variables no estáticas se inicializan de cero , incluso cuando se llama a esta función recursivamente ( se crea un espacio de memoria nuevo para guardar sus variables automáticas para cada invocación de la función ). Esto se ejemplifica claramente por el comportamiento de la variable b.

Algunas conclusiones

Fue muy interesante ver esto, sobre todo al especular sobre como desarrollar un programa a gran escala sobre C. Por ejemplo, se podría considerar a un archivo con sus funciones definidas y sus variables globales propias ( no accesibles para otros archivos ) como un proto-objeto donde sus variables globales son sus atributos y sus funciones son sus métodos. Ahora, como la única forma de acceder a una variable de otro archivo-proto-objeto es a través de extern, se vuelve hyper evidente lo complicado que se transforma desarrollar arquitecturas complejas lidiando con esto. Repentinamente el paradigma OOP se transforma en MARAVILLOSO después de pensar un poco en esto!!!!

Algunos agregados más

Existe la opción register al declarar una variable para guardarla directamente en los registros de la maquina si va a ser muy utilizada.

Se puede declarar un array de la siguiente forma!!


int primos[] = { 2 , 3 , 5 , 7, 11 , 13 }

Referencias

The C Programming Language, Segunda Edición; Kernighan, Ritchie; Prentice Hall Hispanoamerica, 1991

Autor: Emiliano Martínez Luque.

Comments Off on Alcance de Variables en C

Operadores Bitwise ( a nivel del Bit ) en C

Icono de Post September 12 2008 :: Apuntes, c ::

Una de las cosas nuevas que aprendí en los primeros capítulos de K & R, es la explicación de operaciones Bitwise. Lo cierto es que si bien sabia que existían como nunca había tenido la necesidad de utilizarlas, nunca les preste atención. Este es un pequeño resumen por si las necesito a futuro.

Operaciones & , | , ~ y ^

& ( conjunción Lógica o multiplicación Booleana a nivel del bit )
Sean a, b dos cadenas de bits del mismo tamaño ( por ejemplo integer ). La operación a & b realiza una operación de Conjunción Lógica sobre cada uno de los bits de ambas cadenas, devolviendo una nueva cadena de bits de tamaño equivalente a a,b con un 1 en la posición donde tanto a como b tenian un 1 y un 0 en cualquier otro caso. Ej:

a     = 10010101 
b     = 00110100
a & b = 00010100
| ( disyunción Lógica o suma Booleana a nivel del bit )
La operación a | b devuelve un 1 en la posición donde a o b ( o ambos ) tienen un 1 y un 0 cuando ambas tienen cero. Ej:

a     = 10010101 
b     = 00110100
a | b = 10110101
~ ( negación Lógica a nivel del bit )
Sea a una cadena de bits. La operación ~a invierte los 1s y 0s de a. Ej:


a  = 10010101 
~a = 01101010
^ ( Disyunción exclusiva Lógica a nivel del bit )
La operación a ^ b devuelve un 1 en la posición donde a o b ( pero no ambos ) tienen un 1 y un 0 cuando ambas tienen 0 o ambas tienen 1. Ej:

a     = 10010101 
b     = 00110100
a ^ b = 10100001

Operaciones << y >>

Operación <<
Sea a una cadena de bits, n un entero, a << n, devuelve la misma cádena movida n bits a la izquierda ( perdiendose los primeros n bits de la cadena ) y reemplazando las n posiciones a la derecha por 0. Ej:

a      = 10010101 
a << 2 = 01010100
Operación >>
Sea a una cadena de bits, n un entero, a >> n, devuelve la misma cadena movida n bits a la derecha ( perdiéndose los últimos n bits de la cadena ) y reemplazando las n posiciones a la izquierda por 0. Ej:

a      = 10010101 
a >> 3 = 00010010

Algunos Usos y Ejemplos

Multiplicación por 2n

Por propiedades de los números binarios, se cumple que agregando n 0s a la derecha es equivalente a multiplicar este mismo número por 2n. Ej:


int function multiplicar_por_exponente_de_2( int a, int power ) {
	return a << power;
}

Nota: Hay que cuidar el overflow de los datos considerando el tamaño de ints en nuestro sistema. Pero este no es un post sobre implementaciones de C.

Cociente de dividir por 2n


int function cociente_de_exponente_de_2( int a, int power ) {
	return a >> power;
}

Nota: Desde ya que esta función devuelve el cociente pero no el resto.

Cociente y resto de dividir por 2n


unsigned int a, cociente, resto;
a = 757;
cociente = a >> 3;
resto =  (~((~0) << 3)) & a

Nota: ~0 devuelve un int del tamaño del sistema con todos sus bits pasados a 1, al moverlo 3 posiciones a la izquierda se tiene todos 1s salvo los 3 últimos bits, al negar esto se obtiene todos 0s salvo los 3 últimos bits que nos sirven para obtener los valores que son el resto de la división.

Representación en cadena binaria de un número


void show_as_binary( int a, char str[]) {
	int x, size;
	size = (int)sizeof(b) * 8;
	for(x=0; x<size; x++) {

		//This is necesary for a%2 might return -1 if a < 0. 
		str[x] = '0' + ((a%2) < 0 ? 1: (a%2) );
		a = a >> 1;
	}
	reverse(str);
}

Representación en Octal de un número


void show_as_octal( int a, char str[]) {
	int x, size;
	size = (int)sizeof(b) * 8;
	for(x=0; x<size && a!=0; x++) {
		str[ x ] = '0' + (a%8);
		a = a >> 3;
	}
	str[ x ] = '0';
	reverse(str, (x+1));	

} 

Uso de un int para múltiples flags

Es una práctica común en Unix usar ints para pasar múltiples flags a funciones. Supongamos que necesito 4 flags distintos para una función o para lo que sea. Lo que puedo hacer es lo siguiente:


#define FLAG_A 1;
#define FLAG_B 2;
#define FLAG_C 4;
#define FLAG_D 8;

//Llamar a la función con FLAG_A y FLAG_D
call_function( FLAG_A | FLAG_D );

//Comparar si una variable tiene FLAG_B seteado
if( ( a & FLAG_B ) == FLAG_B ) { ...

//Comparar si una variable no tiene FLAG_C seteado
if( ( ( a | FLAG_C ) != a ) { ... 

Lo interesante de esto es que al abstraernos de los ints y pensarlos como cadenas de bits, se pueden hacer operaciones de algebra de boole, donde cada bit toma un valor verdadero o falso, que nos sirve para evaluar colecciones de flags como colecciones de proposiciones booleanas. Ahorrándonos así de pasar un valor como argumento a la función para cada una. Ej:


//Comparar contra FLAG_A, FLAG_B y no FLAG_D
if ( ( ( a & (FLAG_A | FLAG_B) ) == ( FLAG_A | FLAG_B ) ) && ( ( a | FLAG_D ) != a ) ) { ...

Un ejemplo concreto es el uso de los permisos de archivos en linux.

chmod toma un valor en octal que puede representarse así:



0012 = 18 = x

0102 = 28 = w

1002 = 48 = r

De donde surgen sus relativas combinaciones, por ej:



0112 = 38 = wx

1102 = 68 = rw

1112 = 78 = rwx

Bonús. Ejercicios 2.6, 2.7 y 2.8 de K & R

Ej 2.6

Escriba una función setbits( x,p,n,y ) que regresa x con los n bits que principian en la posición p iguales a los n bits más a la derecha de y, dejando los otros bits sin cambio.


//Ej 2.6
unsigned setbits(unsigned x, int p, int n, int y) {
	unsigned t, z;
	if(y < n) { 
		perror("Error");
	} else {
		//All 0s except for the space that starts at y and has size n
		t = ~(~0<<n)<<(y-n);
		//Get the value of x in this position
		t = x & t;
		//move the distance that p has from y
		t = t << (p-y);
		//Set that same space to 0s in x, starting on p and with size n
		z = ~(~0<<n)<<(p-n);		
		x = x & (~ z);
		//merge them
		t = x | t;
	}
	return t;
}

Ej 2.7

Escriba una función invert( x,p,n ) que regresa x con los n bits que principian en la posición p invertidos, dejando los otros sin cambio.


//Ej 2.7
unsigned invert(unsigned x, int p, int n) {
	unsigned t, z;
	//All 0s except for the space that starts at p and has size n
	t = ~(~0<<n)<<(p-n);
	//Get the inverted value of x in this position
	z = (~x & t);
	//merge them (first clean up x in the space that starts at p and has size n then merge with z)
	t = (~t & x) | z;
	return t;
}

Ej 2.8

Escriba una función rightrot( x,n ) que regresa x rotado a la derecha n posiciones de bits.


//Ej 2.8
unsigned rightrot( unsigned a, int n) {
	unsigned t, mascara, x;
	t = 0;
	mascara = 1;
	for(x=0; x<n; x++) {
		t = t << 1;
		t = t | (mascara & a);
		a = a >> 1;
	}
	return t;
}

Autor: Emiliano Martínez Luque.

Comments Off on Operadores Bitwise ( a nivel del Bit ) en C

Ejercicio 4.7 de THRTLMP

Icono de Post September 10 2008 :: Lógica, Teoría de Conjuntos ::

Se nos pide demostrar que siendo A un conjunto de conjuntos, el conjunto { x ∈ A | x ∉ x } ∉ A. Es interesante y por eso lo blogueo porque es una aplicación de la paradoja de Russell.

Demostración

Llamemos B al conjunto { x ∈ A | x ∉ x }. Supongamos que B ∈ A y consideremos a B con respecto a si mismo desde la relación ∈, o bien B ∈ B o bien B∉ B.

Supongamos que B ∈ B entonces por la propia definición de B, B ∉ B, lo cual es una contradicción. Ahora si B ∉ B también por la definición de B sigue que B ∈ B, lo cual también es una contradicción.

Dado que nuestra premisa original nos lleva siempre a una contradicción, debe ser falsa, por consiguiente B ∉ A.

Es interesante también como este ejercicio sirve de introducción a los tipos y clases de Haskell.

Autor: Emiliano Martínez Luque.

Comments Off on Ejercicio 4.7 de THRTLMP

Teoría de Conjuntos ( Definiciones y Formulas Básicas )

Icono de Post September 10 2008 :: Apuntes, Teoría de Conjuntos ::

Definiciones

Conjunto: Colección de Objetos. A, B, C..
Elemento: Objeto dentro de un conjunto. a, b, c.
Representación por extensión.
A = {a, b, c, d}
Representación por comprensión.
A = {x | x < 10 ∧ x > -100}
A = {x | Φ(x) }
∈ pertenece a, es elemento de

∪ Union
A ∪ B = {x | x ∈ A ∨ x ∈ B}
∩ Intersección
A ∩ B = {x | x ∈ A ∧ x ∈ B}
Ac Complemento
Ac = {x | x ∉ A}

Equivalencias Basicas

Doble negación
A = (Ac)c

Idempotencia
A ∪ A = A
A ∩ A = A

De morgan
(A ∪ B)c = (Ac ∪ Bc)
(A ∩ B)c = (Ac ∩ Bc)

Conmutativa
(A ∪ B) = (B ∪ A)
(A ∩ B) = (B ∩ A)

Asociativa
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributiva
A ∩ (B ∪ C) = (A ∪ B) ∩ (A ∪ C)
A ∪ (B ∩ C) = (A ∩ B) ∪ (A ∩ C)

Absorción
A ∩ (A ∪ B) = A
A ∪ (A ∩ B) = A

Universo, Conjunto Vacio

U Universo
∅ Conjunto Vacio

c = U
Uc = ∅

Dominancia
U ∪ A = U
∅ ∩ A = ∅

Identidad
U ∩ A = A
∅ ∪ A = A

Ley del medio excluido
A ∪ Ac = U

Contradicción
A ∩ Ac = ∅

Inclusión, Inclusión estricta, Equivalencia, Resta, Diferencia simetrica

Definiciones

⊆ Inclusión
A ⊆ B = {x | x ∈ A => x ∈ B}
⊂ Inclusión Estricta
A ⊂ B <=> ∀x (x ∈ A => x ∈ B) ∧ ∃y (y ∈ B ∧ y ∉ A)
= Equivalencia
A = B <=> A ⊆ B ∧ B ⊆ A
– Resta
A – B = {x | x ∈ A ∧ x ∉ B}
Δ Diferencia Simetrica
A Δ B = {x | x ∈ A ∨ x ∈ B ∧ ¬ (x ∈ A ∧ x ∈ B) } = A ∪ B -(A ∩ B)

A, B son Disjuntos <=> A ∩ B = ∅

Ac = U – A

Conjunto de Partes y Familias de Conjuntos

Definiciónes

P(A) Conjunto de Partes
X ∈ P(A) <=> X ⊆ A
P(A) = {X | X ⊆ A}

Nota: ∀A( {∅} ∈ P(A) )

F, G Se usan para representar Familias de Conjuntos o o Colecciones de Conjuntos
∪F = ∀x ( ∃y ( y ∈ F ∧ x ∈ y ) )
∩F = ∀x ( ∀y ( y ∈ F -> x ∈ y ) )

Referencias

The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006

Autor: Emiliano Martínez Luque.

Comments Off on Teoría de Conjuntos ( Definiciones y Formulas Básicas )

Loops Elegantes

Icono de Post September 6 2008 :: c ::

Estoy en este momento estudiando The C Programming Language, más que nada como repaso de la sintaxis de C. Los ejercicios, aunque parecen básicos, son muy interesantes como problemas de programación.

En uno de los ejercicios se nos pide hacer una función reverse que tome una cadena y la devuelva invertida. Mi solución rapida fue:


void reverse(char line[], int n) {
	int temp, i, j, t ;
	if( (n/2) == ((n+1)/2) ) {
		t = -1 ;
	} else {
		t = 0 ;
	} 

	j = (n/2) ;
	for(i=0 ; i < j ; i++) {
		temp = line[i] ;
		line[i] = line[ (j*2)-i+t ] ;
		line[ (j*2)-i+t ] = temp ;
	}
	line[ n ] = '' ;
}

Pero en el cápitulo 3 dan la forma de codificarlo de los autores:


void reverse( char s[] ) {
	int c, i, j;
	for( i = 0, j = strlen(s)-1 ; i < j ; i++, j-- ) {
		c = s[i] ;
		s[i] = s[j] ;
		s[j] = c ;
	}
}

Me encanto como esta estructurado el loop, por el simple hecho de que no tengo la costumbre de hacer una doble inicialización y mucho menos un incremento y un decremento simultáneos en la tercera expresión del for. El código es super elegante y ahorra el problema y el exceso de código que tuve que poner en mi versión por si el tamaño de la cadena era impar o par.

Por que no es buena práctica usar breaks en un loop.

Además me di cuenta de lo siguiente, es una frase hecha que no es buena práctica usar breaks en un loop, el tema es que en realidad generalmente no es necesario ( salvo en casos especiales donde se necesita ejecutar algunas lineas de código antes de evaluar la condición del break ). Supongamos el siguiente codigo:


for( x=0 ; x < n ; x++) {
	......
	.....
	if( condicion_de_break ) break ;
}

Se puede resolver más elegantemente de la siguiente forma:


for( x=0 ; x < n && !condicion_de_break ; x++) {
	......
	.....
}

Autor: Emiliano Martínez Luque.

Comments Off on Loops Elegantes

Una Demostración con Incognitas

Icono de Post September 6 2008 :: Lógica ::

Esta demostración maravillosa que esta en el ejercicio 3.7.9 del libro How to Prove It: A Structured Approach, que la transcribo directamente porque es fantástica.

Teorema: Existen 2 números Irracionales a,b tales que ab es racional.

Demostración: O ( 2 ) 2 es racional o es irracional.

Caso 1: Si es racional, ya se probo lo que queríamos probar porque 2 es irracional y tomamos a=b= 2 .

Caso 2: Si es irracional entonces sea a = ( 2 ) 2 y b = 2 . Entonces podemos formar el numero ( ( 2 ) 2 ) 2 = ( 2 ) 2 . 2 = ( 2 ) 2 = 2 . Como 2 es irracional, ( 2 ) 2 es irracional por asumción de caso y 2 es racional, el Teorema queda demostrado.

Lo maravilloso es que llegamos a una demostración rigurosa del teorema sin necesidad de saber si   ( 2 ) 2 es irracional o no. Simplemente por exhaustación de casos el teorema queda demostrado.
Nota: es irracional, lo que igual no quita lo maravilloso de la demostración y lo impecable de su lógica.

Autor: Emiliano Martínez Luque.

Comments Off on Una Demostración con Incognitas

Alfabetos, Lenguajes y Gramáticas (Definiciones Básicas)

Icono de Post September 6 2008 :: Apuntes, Lenguajes Formales ::

Alfabetos

Σ : alfabeto, Conjunto finito, no vacio de símbolos.

Cadena: sucesión de símbolos concatenados.

Σ1 = Σ

Σn+1 = { xy / x ∈ Σ, y ∈ Σn } ; donde x, y son cadenas formadas por símbolos de Σ.
Aclaración: en este caso x representa una cadena formada por un solo símbolo de Σ.

Ejs:
Σ = {a,b,c} => Σ2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc }
aab ∈ Σ
3

Cardinalidad de un Alfabeto

| Σ | = 3  => | Σ2| = 32

Generalizando:

| Σ | = t  => | Σn| = tn

Cadena Vacia

λ: Cadena o palabra vacia. Elemento neutro para la concatenación de cadenas.

Importante: ∀Σ:  Σ0= { λ }

Conjunto infinito de todas las cadenas que pueden formarse con un alfabeto

Σ* = n = 0 Σ n   
| Σ | = ∞

Cadenas y Concatenación

Se puede definir una cadena W sobre el alfabeto Σ como: W = x1x2…..xn ; xi ∈ Σ

Longitud de una cadena

|| w || = n

Concatenación

Sean:
X = x1x2…..xn ; xi ∈ Σ
Y = y
1y2…..ym ; yi ∈ Σ
=>
XY = x
1x2…..xny1y2…..ym; ∧ XY ∈ Σn + m

Propiedades de la Concatenación

1. Cerrada sobre si misma (Ley de Composición Interna)
Σ* -> Σ* : Σ*

2. Asociativa
X(YZ) = (XY)Z

3. No Conmutativa
XY ≠ YX

Longitud de una Concatenación

|| XY || = || X || + || Y ||; ∀ X, Y ∈ Σ*

Potencias de una cadena

∀ X ∈ Σ*:
X
0 = λ
X
1 = X
X
2 = XX
X
n = XXn – 1
|| X
n|| = n . || X ||

Prefijos, Sufijos

sea W ∈ Σ* ∧ W = XY entonces X es prefijo de W, Y es sufijo de W.
Si adémas:
Y ≠ λ => X es prefijo propio de W
X ≠ λ => Y es prefijo propio de W  

Subcadenas

sea W ∈ Σ* ∧ W = XZY entonces Z es subcadena de W.

Lenguajes

Sea Σ ≠ φ, L ⊆ Σ* es un lenguaje sobre Σ

Importante: φ ⊂ Σ . φ es un lenguaje, llamado lenguaje Vacio.

Gramática

G = (V, T, S, P) es una gramática donde:
V  es un Alfabeto
T ⊂ V, son los elementos terminales
S ⊂ V, es el Start Symbol. O Simbolo de Comienzo.
P, son las reglas de Producción.

Lenguaje generado por una gramática

Todas las cadenas de elementos pertenecientes a T, que pueden formarse a partir de las reglas de Producción P. Se lo suele representar com L( G ) .

Ejemplos

1) L = { 1111n0n / n ∈ N}. Lenguaje formado por todas las cadenas con prefijo 111 y luego una suseción de 10.


G = ( V,T,S0,P )
V = {1,0,S}
T = {1,0}
S
0 = S
P:
S -> S10

S -> 111S

2) L = Lenguaje formado por todas las cadenas con prefijo 111 y luego  al menos un 1 o un 0 y luego una sucesión de 1s y 0s en cualquier orden. = {1110, 1111, 11101, 11100, 11110, 11111, …. }

G = ( V,T,S0,P )
V = {1,0,S,A,B}
T = {1,0}
S
0 = S
P:

AB -> BA
BA -> AB
A -> 0
B -> 1
S -> SA
S -> SB
S -> 111S

3) L = Lenguaje que tiene la misma cantidad de 0s y 1s. = { λ, 01, 10, 0011, 0110, 1100, 0101, 1010, …. }

G = ( V,T,S0,P )
V = {1,0,S, A, B}
T = {1,0}
S
0 = S
P:

AB -> BA
BA -> AB
A -> 0
B -> 1
S -> SAB
S -> λ

Referencias

Apuntes de Clase de Algebra y Matemática Discreta cursada en el segundo cuatrimestre de 2007 en la Universidad de Palermo dictada por Marcela Wilder.
Algebra Y Matenática Discreta, Gabriela Esperón, Marcela Wilder, UP, 2007.

Autor: Emiliano Martínez Luque.

Comments Off on Alfabetos, Lenguajes y Gramáticas (Definiciones Básicas)