AUTOMATA

 LENGUAJE FORMAL

1. Introducción

2. Cadena

     2.1. Alfabeto

     2.2. Símbolo

3. Lenguaje

4. Tipos de Lenguajes

5. Teoría de Autómata y Lenguaje Formal

1.INTRODUCCION:

 En matemáticas, lógica y ciencias de la computación, un lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificados. Al conjunto de los símbolos primitivos se le llama el alfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se lo llama la gramática formal (o sintaxis). A una cadena de símbolos formada de acuerdo a la gramática se la llama una fórmula bien formada (o palabra) del lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas. A diferencia de lo que ocurre con el alfabeto (que debe ser un conjunto finito) y con cada fórmula bien formada (que debe tener una longitud también finita), un lenguaje formal puede estar compuesto por un número infinito de fórmulas bien formadas.

Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba , abab, ababba, etc.; y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.

Para algunos lenguajes formales existe una semántica formal que puede interpretar y dar significado a las fórmulas bien formadas del lenguaje. Sin embargo, una semántica formal no es condición necesaria para definir un lenguaje formal, y eso es una diferencia esencial con los lenguajes naturales.

2. CADENA:

Una cadena es una secuencia finita de símbolos de un determinado alfabeto.Ejemplo:

 Tomando en cuenta los alfabetos o vocabularios definidos anteriormente, podemos decir que:

• abcb es una cadena del alfabeto V2

• a+2*b es una cadena del alfabeto V2

• 000111 es una cadena del alfabeto V3

• If a>b then b=a; es una cadena del alfabeto V4

2.1 ALFABETO:

 Un alfabeto es un conjunto finito no vacío de símbolos y se denota como .

Un vocabulario o alfabeto es un conjunto finito de símbolos, no vacío. Para definir que un símbolo a pertenece a un alfabeto V, se utiliza la siguiente notación aÃŽV.

     Los alfabetos se definen por enumeración de los símbolos que contienen, podemos ver los siguientes ejemplos:

• V1={A,B,C,D,E,F,…..,X,Y,Z}

• V2={a,b,c,d,0,1,2,3,4,*,#,+}

• V3={0,1}

• V4={if, then, begin, end, else, a,b,;,=,>}

• También se pueden definir las tablas ASCII y EBCDIC como los alfabetos de distintos ordenadores.

2.2 SIMBOLO:

Un "símbolo" es una entidad abstracta. Las letras y los dígitos son ejemplos de símbolos usados con frecuencia. Una cadena (o palabra) es una secuencia finita de símbolos yuxtapuestos. Por ejemplo, a, b y c son símbolos y casa es una cadena.

3. LENGUAJE:

Un conjunto de palabras, formado por símbolos en un alfabeto dado. Puede ser infinito

4. TIPOS DE LENGUAJES:

Podemos encontrar varios tipos de Lenguajes:
Lenguaje Declarativos. - Son los más parecidos al castellano o ingles en su potencia expresiva y funcionalidad y están ene le nivel más alto respecto a los otros. Son fundamentalmente lenguaje de órdenes, denominados por sentencias que expresan “Lo que hay que hacer” en vez de “Como hacerlo”

 Lenguaje de Alto Nivel. - Son los mas utilizados como lenguaje de programación, Aunque no son fundamentalmente declarativos, estos lenguajes permiten que los algoritmos se expresen en un nivel y estilo de escritura fácilmente legible y comprensible por otros programadores. Además, los lenguajes de alto nivel suelen tener la característica de “Transpirabilidad”.

Lenguajes Ensamblador. Y Lenguaje Maquina.- Cada tipo de maquina tiene su propio lenguajes de maquina distinto y su lenguaje ensamblador asociado. El lenguaje ensamblador es simplemente una representación simbólica del lenguaje maquina asociado, lo cual permite una programación menos tediosa que con el anterior.
Lenguaje natural (castellano)
Nosotros estamos relacionados con el concepto tradicional de gramática que, de esta forma intuitiva, podemos considerar un conjunto de reglas el cual nos indican que es correcto y que no lo es del, lenguaje natural. Con este fin podemos acércanos a la definición más clara y formal de la lengua castellana.

5. TEORÍA DE AUTÓMATAS Y LENGUAJE FORMAL:

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.

Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta función de transición dice al autómata a qué estado cambiar dados unos determinados estado y símbolo.

6. VÍDEO: